1CMSC 132: Object-Oriented Programming IIAdvanced Tree StructuresDepartment of Computer ScienceUniversity of Maryland, College Park2OverviewBinary treesBalanceRotationMulti-way treesSearchInsertIndexed tries3Tree BalanceDegenerateWorst caseSearch in O(n) timeBalancedAverage caseSearch in O( log(n) ) timeDegenerate binary treeBalanced binary tree4Tree 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 case5AVL TreesPropertiesBinary search treeHeights of children for node differ by at most 1 Example 884417 7832 5048 6224112311Heights of children shown in red6AVL 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)7Red-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 leaf8Red-black TreesExample9Red-black TreesHistoryDiscovered in 1972 by Rudolf BayerAlgorithmInsert / delete may require complicated bookkeeping & rotationsJava collectionsTreeMap, TreeSet use red-black trees10Tree RotationsChanges shape of treeMove nodes Change edgesTypesSingle rotationLeftRightDouble rotationLeft-rightRight-left11Tree Rotation ExampleSingle right rotation12312312Tree Rotation ExampleSingle right rotation123564612354Node 4 attached to new parent13Example – Single RotationsT0T1T3T0T1T2T3single left rotationT2T3T2T1T0T3T2T1T0single right rotation12312312312314Example – Double Rotationsright-leftdouble rotationT0T2T1T3T0T2T3T1T3T1T2T0T3T1T0T2left-right double rotation12333221112315Multi-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 1221785 8 15 331 3 19 21974416Types 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-112T2…5 122178caso17Multi-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 402527443618Multi-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 necessary19Multi-way Search TreesInsert Example (for 2-3 tree)Insert( 4 )5 1221785 122 4 17820Multi-way Search TreesInsert Example (for 2-3 tree)Insert( 1 )5 121 2 4 1782 5 1221178451211784Split parentSplit node21B-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 read22Indexed Search Tree (Trie)Special case of treeApplicable when Key C can be decomposed into a sequence of subkeys C1, C2, … CnRedundancy exists between subkeysApproachStore subkey at each nodePath through trie yields full keyExampleHuffman treeC3C1C2C4C323TriesUseful for searching strings String decomposes into sequence of lettersExample“ART”⇒⇒⇒⇒“A” “R” “T”Can be very fastLess overhead than hashingMay reduce memoryExploiting redundancyMay require more memoryExplicitly storing substringsSARTE“ART”24Types of TriesStandardSingle character per nodeCompressedEliminating chains of nodesCompactStores indices into original string(s)SuffixStores all suffixes of string25Standard TriesApproachEach node (except root) is labeled with a characterChildren of node are ordered (alphabetically)Paths from root to leaves yield all input stringsTrie for Morse Code26Standard Trie ExampleFor strings{ a, an, and, any, at }27Standard Trie ExampleFor strings{ bear, bell, bid, bull, buy, sell, stock, stop }aebrllsullye tllockpid28Standard TriesNode structureValue between 1…mReference to m childrenArray or linked listExampleClass Node {Letter value; // Letter V = { V1, V2, … Vm}Node child[ m ];}29Standard TriesEfficiencyUses O(n) space Supports search / insert / delete in O(d××××m) timeForn total size of strings indexed by tried length of the parameter stringm size of the alphabet30Word Matching TrieInsert words into trieEach leaf stores occurrences of word in the text s e e b e a r ? s e l l s t o c k !s e e b u l l ? b u y s t o c k !b i d s t o c k !aah e t h e b e l l ? s t o p !b i d s t o c k !0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2324 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4647 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 6869 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86a r87 88aeblsule te0, 24ocilr6l78d47, 58l30y36l12k17, 40,51, 62p84her69a31Compressed TrieObservationInternal node v of T is redundant if v has one child and is not the rootApproachA chain of redundant nodes can be compressed Replace chain with single node Include concatenation of labels from chainResultInternal nodes have at least 2 childrenSome nodes have multiple characters32Compressed Trieebar llsull yell tock pidaebrllsullye tllockpidExample33Compact TriesCompact representation of a compressed trieApproachFor an array of strings S = S[0], … S[s-1]Store ranges of indices at each nodeInstead of substringRepresent as a triplet of integers (i, j, k)Such that X = s[i][j..k]Example: S[0] = “abcd”, (0,1,2) = “bc”PropertiesUses O(s) space, where s = # of strings in the arrayServes as an auxiliary index structure34Compact RepresentationExamples e eb e a rs e l ls t o c kb u l lb u yb i dh eb e l ls t o p0 1 2 3 4a rS[0] =S[1] =S[2] =S[3] =S[4] =S[5] =S[6] =S[7] =S[8] =S[9] =0 1 2 3 0 1 2 31, 1, 11, 0, 00, 0, 04, 1, 10, 2, 23, 1, 21, 2, 3 8, 2, 36, 1, 24, 2, 3 5, 2, 2 2, 2, 3 3, 3, 4 9,
View Full Document
Unlocking...