Introduction to Algorithms 6.046J/18.401J Lecture 9 Prof. Piotr IndykToday • or how to avoid this Balanced search trees, even in the worst case 1 2 3 4 5 6 © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.2Balanced 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 Examples: • 2-3 trees • 2-3-4 trees • B-trees • Red-black trees © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.3Red-black trees BSTs with 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. © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.4Example of a red-black tree 88 1111101018182626222233 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.5Use of red-black trees • What properties would we like to prove about red-black trees ? – They always have O(log n) height –There is an O(log n)–time insertion procedure which preserves the red-black properties • Is it true that, after we add a new element to a tree (as in the previous lecture), we can always recolor the tree to keep it red-black ? © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.6Example of a red-black tree 88 1111101018182626222233 77 7.57.5© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.7Use of red-black trees • What properties would we like to prove about red- black trees ? –They always have O(log n) height – There is an O(log n)–time insertion procedurewhich preserves the red-black properties • Is it true that, after we add a new element to a tree (asin the previous lecture), we can always recolor thetree to keep it red-black ? • NO • After insertions, sometimes we need to juggle nodesaround © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.8Rotations 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. © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.9Rotations can reduce height BA A 1 2 31 LEFT-ROTATE(A) B2 3 γ γ AA BB αα ββ γγ BB AA γγββ αα © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.10Red-black tree wrap-up • Can show how – O(log n) re-colorings –1 rotation can restore red-black properties after an insertion • Instead, we will see 2-3 trees (but will come back to red-black trees at the end) © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.112-3 Trees • The simplest balanced trees on the planet! • Although a little bit more wasteful © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.122-3 Trees • either 2 or 3 • • depth • Leaves are sorted Degree of each node is Keys are in the leaves All leaves have equal 9 1251 6 7 8 6 8 12 12 • Each node x contains maximum key in thesub-tree, denoted x.max © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.13Internal nodes • Internal nodes: –Values: • x.max: maximum key in the sub-tree – Pointers: •left[x] • mid[x] • right[x] : can be null • p[x] : can be null for the root •… • Leaves: – x.max : the key © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.14Height of 2-3 tree • What is the maximum height h of a 2-3 tree with n nodes ? • Alternatively, what is the minimum number of nodes in a 2-3 tree of height h ? • It is 1+2+22+23+…+2h =2h+1-1 • n ≥ 2h+1-1 ⇒ h = O(log n) • Full binary tree is the worst-case example! © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.15Searching • How can we search for a key k ? Search(x,k): • If x=NIL then return NIL • Else if x is a leaf then – If x.max=k then return x – Else return NIL • Else 9 1251 6 7 8 6 8 12 12 – If k ≤ left[x].max then Search(left[x],k) –Else if k ≤ mid[x].max Search(8) then Search(mid[x],k) Search(13) –Else Search(right[x],k) © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.161212Insertion • How to insert x ? • Perform Search for the key of x • Let y be the last internal node • Insert x into y in a sorted order • At the end, update the max values on the path to root 9 1251 6 7 8 6 8 7.55.5 1313Insert(7.5) (continued on the next Insert(13) slide) Insert(5.5) © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.17 131212Insertion, ctd. (continued from the previous slide) • If y has 4 children, then Split(y) x 9 1251 6 7 8 6 8 7.55.5 13 13 y © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.18 13Split • Split y into two nodes y1, y2 • Both are linked to * z=parent(y)• If z has 4 children, split z *If y is a root, then create new parent(y)=new root ba d y c ba d y1 c y2 z z © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.191212Split 9 1251 6 7 8 6 8 5.5 13 13 7.5 13 © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.201212Split 9 1251 6 7 8 5.5 8 5.5 13 13 6 7.5 13 © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.2112Split 9 1251 6 7 8 5.5 8 5.5 13 6 6 13 13 7.5 13 • Insert and Split preserve heights, unless new root is created, in which case all heights are increased by 1 • After Split, all nodes have 2 or 3 children • Everything takes O(log n) time © Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.2212Delete • How to delete x ? • Let y=p(x) • Remove x from y • If y has 1 child: – Remove y 9 1251 6 7 8 5.5