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