Introduction to Algorithms 6.046J/18.401J LECTURE 10 Balanced Search Trees • Red-black trees • Height of a red-black tree • Rotations • Insertion Prof. Erik Demaine October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.1Balanced 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. • AVL trees • 2-3 trees Examples: • 2-3-4 trees • B-trees • Red-black trees October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.2Red-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). October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.3Example of a red-black tree h = 4 88 1111101018182626222233 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.4Example of a red-black tree 88 1111101018182626222233 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL 1. Every node is either red or black. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.5Example of a red-black tree 88 1111101018182626222233 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL 2. The root and leaves (NIL’s) are black. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.6Example of a red-black tree 88 1111101018182626222233 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL 3. If a node is red, then its parent is black. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.7Example of a red-black tree 88 1111101018182626222233 77 NIL NIL NIL bh = 2 bh = 1 bh = 1 bh = 2 bh = 0 NIL NIL NIL NIL NIL NIL 4. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x). October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.8Height 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. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.9Height 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. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.10Height 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. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.11Height 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. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.12Height 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. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.13Height 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. h′ • 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. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.14Proof (continued) • 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 ≥ 2h' ⇒ lg(n + 1) ≥ h' ≥ h/2 ⇒ h ≤ 2 lg(n + 1). h′ h October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.15Query 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. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.16Modifying 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”. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.17Rotations AABBααββ γγ RIGHT-ROTATE(B) BBAAγγββ αα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. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.18Insertion 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. Example: 88 101018182626222277 33 1111October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.19Insertion 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. Example: • Insert x =15. • Recolor, moving the 881111101018182626222277151533violation up the tree. October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.20Insertion 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. Example: • Insert x =15. • Recolor, moving the 881111101018182626222277151533violation up the tree. • RIGHT-ROTATE(18). October 19, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.21Insertion into a red-black tree