This chapter provides knowledge of red black trees. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Red-Black Trees 3/20/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Red-Black Trees v 6 8 3 4 © 2014 Goodrich, Tamassia, Goldwasser z Red-Black Trees 1 From (2,4) to Red-Black Trees ! A red-black tree is a representation of a (2,4) tree by means of a ! binary tree whose nodes are colored red or black In comparison with its associated (2,4) tree, a red-black tree has same logarithmic time performance simpler implementation with a single node type n n 4 3 4 5 5 3 © 2014 Goodrich, Tamassia, Goldwasser 2 6 7 3 OR Red-Black Trees 6 5 2 7 2 1 Red-Black Trees 3/20/14 Red-Black Trees ! A red-black tree can also be defined as a binary search tree that satisfies the following properties: n n n n Root Property: the root is black External Property: every leaf is black Internal Property: the children of a red node are black Depth Property: all the leaves have the same black depth 9 4 2 15 6 12 21 7 © 2014 Goodrich, Tamassia, Goldwasser Red-Black Trees 3 Height of a Red-Black Tree ! Theorem: A red-black tree storing n items has height O(log n) Proof: n The height of a red-black tree is at most twice the height of its associated (2,4) tree, which is O(log n) ! The search algorithm for a binary search tree is the same as that for a binary search tree ! By the above theorem, searching in a red-black tree takes O(log n) time © 2014 Goodrich, Tamassia, Goldwasser Red-Black Trees 4 2 Red-Black Trees 3/20/14 Insertion ! To insert (k, o), we execute the insertion algorithm for binary search trees and color red the newly inserted node z unless it is the root n n n We preserve the root, external, and depth properties If the parent v of z is black, we also preserve the internal property and we are done Else (v is red ) we have a double red (., a violation of the internal property), which requires a .
