DOC PREVIEW
UMD CMSC 132 - Advanced Tree Data Structures

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 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 11 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 11 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 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Advanced Tree Data StructuresNelson Padua-PerezChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewBinary treesBalanceRotationMulti-way treesSearchInsert2Tree BalanceDegenerateWorst caseSearch in O(n) timeBalancedAverage caseSearch in O( log(n) ) timeDegenerate binary treeBalanced binary treeTree BalanceQuestionCan we keep tree (mostly) balanced?Self-balancing binary search treesAVL treesRed-black treesApproachSelect invariant (that keeps tree balanced)Fix tree after each insertion / deletion Maintain invariant using rotationsProvides operations with O( log(n) ) worst case3AVL TreesPropertiesBinary search treeHeights of children for node differ by at most 1 Example 884417 7832 5048 6224112311Heights of children shown in redAVL TreesHistoryDiscovered in 1962 by two Russian mathematicians, Adelson-Velskii & LandisAlgorithm1. Find / insert / delete as a binary search tree2. After each insertion / deletiona) If height of children differ by more than 1b) Rotate children until subtrees are balancedc) Repeat check for parent (until root reached)4Red-black TreesPropertiesBinary search treeEvery node is red or blackThe root is blackEvery leaf is blackAll children of red nodes are blackFor each leaf, same # of black nodes on path to rootCharacteristicsProperties ensures no leaf is twice as far from root as another leafRed-black TreesExample5Red-black TreesHistoryDiscovered in 1972 by Rudolf BayerAlgorithmInsert / delete may require complicated bookkeeping & rotationsJava collectionsTreeMap, TreeSet use red-black treesTree RotationsChanges shape of treeMove nodes Change edgesTypesSingle rotationLeftRightDouble rotationLeft-rightRight-left6Tree Rotation ExampleSingle right rotation123123Tree Rotation ExampleSingle right rotation123564612354Node 4 attached to new parent7Example – Single RotationsT0T1T3T0T1T2T3single left rotationT2T3T2T1T0T3T2T1T0single right rotation123123123123Example – Double Rotationsright-leftdouble rotationT0T2T1T3T0T2T3T1T3T1T2T0T3T1T0T2left-right double rotation1233322111238Multi-way Search TreesPropertiesGeneralization of binary search treeNode contains 1…k keys (in sorted order)Node contains 2…k+1 childrenKeys in jthchild < jthkey < keys in (j+1)thchildExamples5 122 1785 8 15 331 3 19 219744Types of Multi-way Search Trees2-3 treeInternal nodes have 2 or 3 childrenIndex search trieInternal nodes have up to 26 children (for strings)B-treeT = minimum degree Non-root internal nodes have T-1 to 2T-1 childrenAll leaves have same depthT-1 … 2T-11 2T2…5 122 178ca so9Multi-way Search TreesSearch algorithm1. Compare key x to 1…k keys in node2. If x = some key then return node3. Else if (x < key j) search child j4. Else if (x > all keys) search child k+1ExampleSearch(17)5 121 2 17830 402527 4436Multi-way Search TreesInsert algorithm1. Search key x to find node n2. If ( n not full ) insert x in n3. Else if ( n is full ) a) Split n into two nodesb) Move middle key from n to n’s parentc) Insert x in nd) Recursively split n’s parent(s) if necessary10Multi-way Search TreesInsert Example (for 2-3 tree)Insert( 4 )5 122 1785 122 4 178Multi-way Search TreesInsert Example (for 2-3 tree)Insert( 1 )5 121 2 4 1782 5 1221 17845121 1784Split parentSplit node11B-TreesCharacteristicsHeight of tree is O( logT(n) )Reduces number of nodes accessedWasted space for non-full nodesPopular for large databases1 node = 1 disk blockReduces number of disk blocks


View Full Document

UMD CMSC 132 - Advanced Tree Data Structures

Documents in this Course
Notes

Notes

8 pages

Recursion

Recursion

12 pages

Sorting

Sorting

31 pages

HTML

HTML

7 pages

Trees

Trees

19 pages

HTML

HTML

18 pages

Trees

Trees

19 pages

Honors

Honors

19 pages

Lecture 1

Lecture 1

11 pages

Quiz #3

Quiz #3

2 pages

Hashing

Hashing

21 pages

Load more
Download Advanced Tree Data Structures
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 Advanced Tree Data Structures 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 Advanced Tree Data Structures 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?