DOC PREVIEW
MIT 6 006 - Lecture Notes

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.006- Introduction to Algorithms Lecture 4 Prof. Patrick JailletLecture Overview • Review: Binary Search Trees • Importance of being balanced • Balanced BSTs – AVL trees • definition • rotations, insert – Other balanced trees 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 = 3BST 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 1The importance of being balanced vs.Perfectly Balanced Pathh = Θ(log n) h = Θ(n) for n nodes:Balanced BST Strategy • Augment every node with some property • Define a local invariant on property • Show (prove) that invariant guarantees Θ(log n) height • Design algorithms to maintain property and the invariantAVL Trees: Definition [Adelson-Velskii and Landis’62] • Property: for every node, store 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 654120115029263211φφφ0 0 0AVL 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 • Better bounds ? h-1 h-2 hRotations 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/Deletions • 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 • 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-1Case 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!Examples 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) •


View Full Document

MIT 6 006 - Lecture Notes

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?