Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 10 Prof. Erik Demaine Introduction to Algorithms Day 18 L10.2? 2001 by Charles E. Leiserson Balanced search trees Balanced search tree: A search-tree data structure for which a height of O(lg n) is guaranteed when implementing a dynamic set of n items. Examples: ? AVL trees ? 2-3 trees ? 2-3-4 trees ? B-trees ? Red-black trees Introduction to Algorithms Day 18 L10.3? 2001 by Charles E. Leiserson Red-black trees This data structure requires an extra one- bit color field in each node. Red-black properties: 1. Every node is either red or black. 2. The root and leaves (NIL’s) are black. 3. If a node is red, then its parent is black. 4. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x). Introduction to Algorithms Day 18 L10.4? 2001 by Charles E. Leiserson Example of a red-black tree h = 4 8 8 11 11 10 10 18 18 26 26 22 22 3 3 7 7 NIL NIL NIL NIL NIL NIL NIL NIL NIL Introduction to Algorithms Day 18 L10.5? 2001 by Charles E. Leiserson Example of a red-black tree 8 8 11 11 10 10 18 18 26 26 22 22 3 3 7 7 NIL NIL NIL NIL NIL NIL NIL NIL NIL 1. Every node is either red or black. Introduction to Algorithms Day 18 L10.6? 2001 by Charles E. Leiserson Example of a red-black tree 8 8 11 11 10 10 18 18 26 26 22 22 3 3 7 7 NIL NIL NIL NIL NIL NIL NIL NIL NIL 2. The root and leaves (NIL’s) are black. Introduction to Algorithms Day 18 L10.7? 2001 by Charles E. Leiserson Example of a red-black tree 8 8 11 11 10 10 18 18 26 26 22 22 3 3 7 7 NIL NIL NIL NIL NIL NIL NIL NIL NIL 3. If a node is red, then its parent is black. Introduction to Algorithms Day 18 L10.8? 2001 by Charles E. Leiserson Example of a red-black tree 4. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x). 8 8 11 11 10 10 18 18 26 26 22 22 3 3 7 7 NIL NIL NIL NIL NIL NIL NIL NIL NIL bh = 2 bh = 1 bh = 1 bh = 2 bh = 0 Introduction to Algorithms Day 18 L10.9? 2001 by Charles E. Leiserson Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) INTUITION: ? Merge red nodes into their black parents. Introduction to Algorithms Day 18 L10.10? 2001 by Charles E. Leiserson Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) INTUITION: ? Merge red nodes into their black parents. Introduction to Algorithms Day 18 L10.11? 2001 by Charles E. Leiserson Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) INTUITION: ? Merge red nodes into their black parents. Introduction to Algorithms Day 18 L10.12? 2001 by Charles E. Leiserson Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) INTUITION: ? Merge red nodes into their black parents. Introduction to Algorithms Day 18 L10.13? 2001 by Charles E. Leiserson Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) INTUITION: ? Merge red nodes into their black parents. Introduction to Algorithms Day 18 L10.14? 2001 by Charles E. Leiserson Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) ? This process produces a tree in which each node has 2, 3, or 4 children. ? The 2-3-4 tree has uniform depth h′ of leaves. INTUITION: ? Merge red nodes into their black parents. h′ Introduction to Algorithms Day 18 L10.15? 2001 by Charles E. Leiserson Proof (continued) h′ h ? We have h′≥h/2, since at most half the leaves on any path are red. ? The number of leaves in each tree is n + 1 ? n + 1 ≥ 2 h' ? lg(n + 1) ≥ h' ≥ h/2 ? h ≤ 2 lg(n + 1). Introduction to Algorithms Day 18 L10.16? 2001 by Charles E. Leiserson Query operations Corollary. The queries SEARCH, MIN, MAX, SUCCESSOR, and PREDECESSOR all run in O(lg n) time on a red-black tree with n nodes. Introduction to Algorithms Day 18 L10.17? 2001 by Charles E. Leiserson Modifying operations The operations INSERT and DELETE cause modifications to the red-black tree: ? the operation itself, ? color changes, ? restructuring the links of the tree via “rotations”. Introduction to Algorithms Day 18 L10.18? 2001 by Charles E. Leiserson Rotations A B α β β γ γ RIGHT-ROTATE(B) B A γ γ β β α LEFT-ROTATE(A) Rotations maintain the inorder ordering of keys: ? a ∈α, b ∈β, c ∈γ ? a ≤ A ≤ b ≤ B ≤ c. A rotation can be performed in O(1) time. Introduction to Algorithms Day 18 L10.19? 2001 by Charles E. Leiserson Insertion into a red-black tree 8 8 10 10 18 18 26 26 22 22 7 7 Example: 3 3 11 11 IDEA: Insert x in tree. Color x red. Only red- black property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Introduction to Algorithms Day 18 L10.20? 2001 by Charles E. Leiserson Insertion into a red-black tree 8 8 11 11 10 10 18 18 26 26 22 22 7 7 15 15 Example: ? Insert x =15. ? Recolor, moving the violation up the tree. 3 3 IDEA: Insert x in tree. Color x red. Only red- black property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Introduction to Algorithms Day 18 L10.21? 2001 by Charles E. Leiserson Insertion into a red-black tree 8 8 11 11 10 10 18 18 26 26 22 22 7 7 15 15 Example: ? Insert x =15. ? Recolor, moving the violation up the tree. ? RIGHT-ROTATE(18). 3 3 IDEA: Insert x in tree. Color x red. Only red- black property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Introduction to Algorithms Day 18 L10.22? 2001 by Charles E. Leiserson Insertion into a red-black tree 8 8 11 11 10 10 18 18 26 26 22 22 7 7 15 15 Example: ? Insert x =15. ? Recolor, moving the violation up the tree. ? RIGHT-ROTATE(18). ? LEFT-ROTATE(7) and recolor. 3 3 IDEA: Insert x in tree. Color x red. Only red- black property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Introduction to Algorithms Day 18 L10.23? 2001 by Charles E. Leiserson Insertion into a red-black tree IDEA: Insert x in tree. Color x red. Only red- black property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. 8 8 11 11 10 10 18 18 26 26 22 22 7 7 15 15 Example: ? Insert x =15. ? Recolor, moving the violation up the tree. ? RIGHT-ROTATE(18). ? LEFT-ROTATE(7) and recolor. 3 3 Introduction to Algorithms Day 18 L10.24? 2001 by Charles E. Leiserson Pseudocode RB-INSERT(T, x) TREE-INSERT(T, x) color[x] ← RED ? only RB property 3 can be violated while x ≠ root[T] and color[p[x]] = RED do if p[x] = left[p[p[x]] then y ← right[p[p[x]] ? y = aunt/uncle of x if color[y] = RED then ?Case 1? else if x = right[p[x]] then ?Case 2? ? Case 2 falls into Case 3 ?Case 3? else ?“then” clause with “left” and “right” swapped? color[root[T]] ← BLACK Introduction to Algorithms Day 18 L10.25? 2001 by Charles E. Leiserson Graphical notation Let denote a subtree with a black root. All ’s have the same black-height. Introduction to Algorithms Day 18 L10.26? 2001 by Charles E. Leiserson Case 1 B B C C D D A A x y (Or, children of A are swapped.) B B C C D D A A new x Push C’s black onto A and D, and recurse, since C’s parent may be red. Recolor Introduction to Algorithms Day 18 L10.27? 2001 by Charles E. Leiserson Case 2 B B C C A A x y LEFT-ROTATE(A) A A C C B B x y Transform to Case 3. Introduction to Algorithms Day 18 L10.28? 2001 by Charles E. Leiserson Case 3 A A C C B B x y RIGHT-ROTATE(C) A A B B C C Done! No more violations of RB property 3 are possible. Introduction to Algorithms Day 18 L10.29? 2001 by Charles E. Leiserson Analysis ? Go up the tree performing Case 1, which only recolors nodes. ? If Case 2 or Case 3 occurs, perform 1 or 2 rotations, and terminate. Running time: O(lg n) with O(1) rotations. RB-DELETE — same asymptotic running time and number of rotations as RB-INSERT (see textbook).