New version page

Introduction to Algorithms

Upgrade to remove ads

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

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

Upgrade to remove ads
Unformatted text preview:

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


Download Introduction to Algorithms
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 Introduction to Algorithms 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 Introduction to Algorithms 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?