04/02/1404:44:35 127 CS 61B: Lecture 27 Wednesday, April 2, 20142-3-4 TREES===========Last lecture, we learned about the Ordered Dictionary ADT, and we learned onedata structure for implementing it: binary search trees. Today we learna faster one.A 2-3-4 tree is a perfectly balanced tree. It has a big advantage over regularbinary search trees: because the tree is perfectly balanced, find, insert, andremove operations take O(log n) time, even in the worst case.2-3-4 trees are thus named because every node has 2, 3, or 4 children, exceptleaves, which are all at the bottom level of the tree. Each node stores 1, 2,or 3 entries, which determine how other entries are distributed among itschildren’s subtrees.Each internal (non-leaf) node has one more child than entries. For example,a node with keys [20, 40, 50] has four children. Eack key k in the subtreerooted at the first child satisfies k <= 20; at the second child,20 <= k <= 40; at the third child, 40 <= k <= 50; and at the fourth child,k >= 50.WARNING: The algorithms for insertion and deletion I’ll discuss today aredifferent from those discussed by Goodrich and Tamassia. The text presents"bottom-up" 2-3-4 trees, so named because the effects of node splits at thebottom of the tree can work their way back up toward the root. I’ll discuss"top-down" 2-3-4 trees, in which insertion and deletion finish at the leaves.Top-down 2-3-4 trees are usually faster than bottom-up ones, because both treessearch down from the root to the leaves, but only the bottom-up trees sometimesgo back up to the root. Goodrich and Tamassia call 2-3-4 trees "(2, 4) trees".2-3-4 trees are a type of B-tree, which you may learn about someday inconnection with fast disk access for database systems. B-trees on disksusually use the top-down insertion/deletion algorithms, because accessinga disk track is slow, so you’d rather not revisit it multiple times.[1] Entry find(Object k);Finding an entry is straightforward. ==========Start at the root. At each node, +20 40 50+check for the key k; if it’s not /--==========------\present, move down to the /---/ / \ \-----\appropriate child chosen by ---- ---- ---- =======comparing k against the keys. |14| |32| |43| +70 79+Continue until k is found, ---- ---- ---- =======or k is not found at a / \ / \ / \ / | \leaf node. For example, ---- ---- ---- ---- ---- ---- ---------- ==== ----find(74) visits the |10| |18| |25| |33| |42| |47| |57 62 66| +74+ |81|double-lined boxes at right. ---- ---- ---- ---- ---- ---- ---------- ==== ----Incidentally, you can define an inorder traversal on 2-3-4 trees analogous tothat on binary trees, and it visits the keys in sorted order.[2] Entry insert(Object k, Object e);insert(), like find(), walks down the tree in search of the key k. If it findsan entry with key k, it proceeds to that entry’s "left child" and continues.Unlike find(), insert() sometimes modifies ---- -------nodes of the tree as it walks down. |20| |11 20|Specifically, whenever insert() encounters ---- -------a 3-key node, the middle key is ejected, / \ => / | \and is placed in the parent node instead. ========== ---- ---- ---- ----Since the parent was previously treated the +10 11 12+ |30| |10| |12| |30|same way, the parent has at most two keys, ========== ---- ---- ---- ----and always has room for a third. The othertwo keys in the 3-key node are split into two separate 1-key nodes, which aredivided underneath the old middle key (as the figure illustrates).For example, suppose we ---- insert 60 into the tree |40| depicted in [1]. The /------\ first node visited is /---/ \----\ the root, which has three ---- ---- keys; so we kick the |20| |50| middle key (40) upstairs. ---- /------\ Since the root node has / \ / \ no parent, a new node ---- ---- ---- ---------- is created to hold 40 |14| |32| |43| |62 70 79| and becomes the root. ---- ---- ---- ---------- Similarly, 62 is kicked / \ / \ / \ / | | \ upstairs when insert() ---- ---- ---- ---- ---- ---- ------- ---- ---- ----finds the node containing |10| |18| |25| |33| |42| |47| |57 60| |66| |74| |81|it. This ensures us that ---- ---- ---- ---- ---- ---- ------- ---- ---- ----when we arrive at the leaf(labeled 57 in this example), there’s room to add the new key 60.Observe that along the way, we created a new 3-key node "62 70 79". We do notkick its middle key upstairs until the next time it is visited.Again, the reasons why we split every 3-key node we encounter (and move itsmiddle key up one level) are (1) to make sure there’s room for the new key inthe leaf node, and (2) to make sure that above the leaves, there’s room for anykey that gets kicked upstairs. Sometimes, an insertion operation increases theheight of the tree by one by creating a new root.04/02/1404:44:35 227[3] Entry remove(Object k);2-3-4 tree remove() is similar to remove() on binary search trees: you findthe entry you want to remove (having key k). If it’s in a leaf, you remove it.If it’s in an internal node, you replace it with the entry with the next higherkey. That entry is always in a leaf. In either case, you remove an entry froma leaf in the end.Like insert(), remove() changes nodes of the tree as it walks down. Whereasinsert() eliminates 3-key nodes (moving keys up the tree) to make room for newkeys, remove() eliminates 1-key nodes (pulling keys down the tree) so that akey can be removed from a leaf without leaving it empty. There are three ways1-key nodes (except the root) are eliminated.(1) When remove() encounters a 1-key ------- ------- node (except the root), it tries |20 40| |20 50|
View Full Document
Unlocking...