6.006- Introduction to Algorithms Lecture 4 Prof. Piotr IndykLecture Overview • Review: Binary Search Trees • Importance of being balanced • Balanced BSTs – AVL trees • definition • rotations, insert 1 5 6 7 10 12 7 10 5 1 6 12Binary Search Trees (BSTs) • Each node x has: – key[x] – Pointers: left[x], right[x], p[x] • Property: for any node x: – For all nodes y in the left subtree of x: key[y] ≤ key[x] – For all nodes y in the right subtree of x: key[y] ≥ key[x] 10 12 5 1 6 7 root leaf height = 3The importance of being balanced h = Θ(log n) h = Θ(n) for n nodes: 1 5 6 7 10 12 7 10 5 1 6 12Balanced BST Strategy • Augment every node with some data • Define a local invariant on data • Show (prove) that invariant guarantees Θ(log n) height • Design algorithms to maintain data and the invariantAVL Trees: Definition • Data: for every node, maintain its height (“augmentation”) – Leaves have height 0 – NIL has “height” -1 • Invariant: for every node x, the heights of its left child and right child differ by at most 1 x k k-1 7 10 5 1 6 12 2 0 1 1 0 0 7 10 5 1 6 12 3 1 1 2 0 0 4 0 [Adelson-Velskii and Landis’62]AVL trees have height Θ(log n) • Let nh be the minimum number of nodes of an AVL tree of height h • We have nh ≥ 1+ nh-1 + nh-2 ⇒ nh > 2nh-2 ⇒ nh > 2h/2 ⇒ h < 2 lg nh • The constant “2” can be improved h-1 h-2 h Invariant: for every node x, the heights of its left child and right child differ by at most 1 How can we maintain the invariant ?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. 1 2 3 LEFT-ROTATE(1) 1 2 3Insertions • Insert new node u as in the simple BST – Can create imbalance • Work your way up the tree, restoring the balance • Similar issue/solution when deleting a node h-2 h h-1 u +1Balancing • Let x be the lowest “violating” node – We will fix the subtree of x and move up • Assume the right child of x is deeper than the left child of x (x is “right-heavy”) • Scenarios: – Case 1: Right child y of x is right-heavy – Case 2: Right child y of x is balanced – Case 3: Right child y of x is left-heavy y x C B ACase 1: y is right-heavy y x C B A LEFT-ROTATE(x) k-1 k+1 k k-1 x y A B C k-1 k-1 kCase 2: y is balanced Same as Case 1 y x C B A LEFT-ROTATE(x) k-1 k+1 k k x y A B C k-1 k kCase 3: y is left-heavy Need to do more … y x C B A LEFT-ROTATE(x) k-1 k+1 k-1 k x y A B C k-1 k k-1Rotations 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. 1 2 3 LEFT-ROTATE(1) 1 2 3Case 3: y is left-heavy y x C B A k-1 k+1 k-1 k D z k-1 or k-2 LEFT-ROTATE(x) RIGHT-ROTATE (y) k-1 x z A B D k k-1 y k-1 or k-2 C And we are done!Conclusions • Can maintain balanced BSTs in O(log n) time per insertion • Search etc take O(log n) timeExamples of insert/balancing 654120115029263211φφφ6541201150292621φφφ123Insert(23)x = 29: left-left case654120115026233211φφφ65412011501φφDone Insert(55)29φ322623129φφ65412011502φφ22623129φφx=65: left-right case55155412011501φφ22623129φφ65Done3φBalanced Search Trees … • AVL trees (Adelson-Velsii and Landis 1962) • Red-black trees (see CLRS 13) • Splay trees (Sleator and Tarjan 1985) • Scapegoat trees (Galperin and Rivest 1993) • Treaps (Seidel and Aragon 1996) • ….BST for runway reservation system • R = (37, 41, 46, 49, 56) current landing times • remove t from the set when a plane lands R = (41, 46, 49, 56) • add new t to the set if no other landings are scheduled within < 3 minutes from t • 44 => reject (46 in R) • 53 => ok • delete, insert, conflict checking take O(h), where h is the height of the tree 37 4146 49 56time (mins)nowx x x x49 56 41 37 46 5-1 1 3-1 1 1 53 49 56 41 46 4+1 1+1 2 1 17 10 5 1 6 12 3 1 1 2 0 0 4 0And some people like to do
View Full Document
Unlocking...