1CISC320, F05, Lec9, Liao 1CISC 320 Introduction to AlgorithmsFall 2005Lecture 9Red-Black Trees CISC320, F05, Lec9, Liao2Binary Search Trees (BST)key[x]: key stored at x.left[x]: pointer to left child of x.right[x]: pointer to right child of x.p[x]: pointer to parent node of x.binary-search-tree property:for every node x: key[y] ≤ key[x] ≤ key[z]where y is any node in the left subtree of x, and z is any node in the right subtree of x.e.g., two valid BSTs for the keys 2, 3, 4, 5, 7, 8.532 4782375 84CISC320, F05, Lec9, Liao3Inorder-tree-walk(x)1. if x ≠ nil2. then inorder-tree-walk(left[x]);3. print key[x];4. inorder-tree-walk(right[x]);It prints all elements in monotonically increasing order, in Θ(n) time.BST SearchSearch(T, k)1. x = root[T];2. if x = nil or k = key[x]3. then return x;4. if k < key[x]5. then return Search(left[x], k)6. else return Search(right[x], k);CISC320, F05, Lec9, Liao4Time: O(h), where h is the tree height.  for a balanced binary tree, h = lg(n) worst-case: h = n.532 478532478CISC320, F05, Lec9, Liao5 Rotation Note: 1. inorder key ordering is unchanged after rotation: a, x, b, y, c2. rotation takes O(1) time. xyyxabcLeft rotate Right rotate abcCISC320, F05, Lec9, Liao6532 4782354 78Left rotate2CISC320, F05, Lec9, Liao7 Left-rotate(T,x)1. y ← right[x]2. right[x] ← left[y]3. if left[y] ≠ nil4. then p[left[y]] ← x5. p[y] ← p[x]6. if p[x] = nil7. then root[T] ← y8. else if x = left[p[x]]9. then left[p[x]] ← y10. else right[p[x]] ← y11. left[y] ← x12. p[x] ← yyxabcLeft rotatexyabcCISC320, F05, Lec9, Liao8Is there a mechanism to automatically rotate whenever the tree is significantly unbalanced? CISC320, F05, Lec9, Liao9Red- Black Trees1. Red-black tree is a binary search tree. Every node is either red or black.2. Root is always black3. Every leaf (nil) must be black4. If a node is red, then both children are black5. All paths from any node x to a descendant leaf have same number of black nodes.Definition: black-height of a node x is the number of black nodes (excluding x) on any path from x to a descendant leaf.CISC320, F05, Lec9, Liao10 A red-black treeIntuition: if a red-black tree contains black nodes only, the tree is perfectly balanced, i.e., it is a complete binary tree. Presence of red nodes corrupts the balance, but not much, because of the restrictions imposed on red nodes. 15531612153121515CISC320, F05, Lec9, Liao11Theorem: A red-black tree with n internal nodes has height at most 2 lg(n+1).proof: a) for any node x, its black-height denoted as bh(x), there are at least 2 bh(x)– 1 internal nodes under x.b) if the root r has height h, then h ≤ 2 bh(r), because at least half of the nodes on any path from r to a leaf must be black. According to a), we have 2 bh(r)–1 ≤ nbh(r) ≤ lg (n+1)h ≤ 2 lg(n+1). QEDCISC320, F05, Lec9, Liao12Therefore, a red-black tree can never be too off- balanced. As a result, searching a key in a red-black tree of n nodes takes O(2 lg(n+1)) time.How about insert and delete? More work is needed for these operations since the red-black tree properties need to be maintained.3CISC320, F05, Lec9, Liao13Insertionstep 1: locate where to insert, via an unsuccessful search. O(lg n)step 2: insert. O(1)new node is assigned red color. why?- any new node potentially can unbalance the tree- if red node gets a red child, RBT is broken. This alerts us to prevent from continuouslyadding nodes at a branch.step 3: check if red-black- tree properties are damaged. If yes, fix it by rotations. O(?) CISC320, F05, Lec9, Liao14RB-Insert(T, z)1. y ← nil[T]2. x ← root[T]3. while x ≠ nil[T]4. do y ← x5. if key[z] < key[x]6. then x ← left[x]7. else x ← right[x]8. p[z] ← y9. If y = nil[T]10. then root[T] ← z11. else if key[z] < key[y]12. then left[y] ← z13. else right[y] ← z14. left[z] ← nil[T]15. right[z] ← nil[T]16. Color[z] ← RED17. RB-Insert-Fixup(T, z)CISC320, F05, Lec9, Liao15Case 1: red uncleBACabcDdeBACabcDde1. Why C must be black? Because otherwise B and C already broke RBT.2. Why C has to be red after B and D are changed to black? To maintain the black height for any node above C, say E. 3. If C is not root, its color change may propagate the problem up.if C is the root, we only need to recolor it as black.Ezynew zCISC320, F05, Lec9, Liao16Case 1: red uncle BACabcDdeBACabcDdzynew zeCISC320, F05, Lec9, Liao17Case 2: right child, black uncleBACabcdABCabcd1. Does this left rotation at node B make the tree more balanced? Not yet.zzyyCISC320, F05, Lec9, Liao18Case 3: left child, black uncle BACabcdA CBabcdNote: 1. The right rotation at node C makes the tree more balanced2. will not propagate further up.zz4CISC320, F05, Lec9, Liao191523161210613201111475481515231612106132011114754815721548151620111415157216201111454815Case 1Case 3Case 2zzzzyyyCISC320, F05, Lec9, Liao20 Case 4,5 and 6 are just mirror symmetric to cases 1, 2, and 3 respectively, and can be similarly handled. CISC320, F05, Lec9, Liao21RB-Insert-Fixup(T, z)1. while color[p[z]] = RED2. do if p[z] = left[p[p[z]]]3. then y ← right[p[p[z]]]4. if color[y] = RED5. then color[p[z]] ← BLACK6. color[y] ← BLACK7. color[p[p[z]]] ← RED8. z ← p[p[z]]9. else if z = right[p[z]]10. then z ← p[z]11. LEFT-ROTATE(T, z)12. color[p[z]] ← BLACK13. color[p[p[z]]] ← RED14. RIGHT-ROTATE(T, p[p[z]])15. else ( same as then clause with “right” and “left” exchanged)16. Color[root[T]] ← BLACKCISC320, F05, Lec9, Liao22Time analysis for insertionRB-Insert-Fixup either removes a red edge by constant time (cases 2, and 3) or propagates red edge one level up (never down), at most to the root, which is the worst case. As a red-black tree of n internal nodes can not be higher than O(lg n), RB-Insert-Fixup runs in O(lg n) time. Therefore, the total time isT(n) = O(lg n) + O(lg n) = O(lg