CMSC 132: Object-Oriented Programming II2-3-4 Tree1CMSC 132 Summer 20172-3-4 TreeSelf-balancing treeevery internal node has either two, three, or four child nodes.• a 2-node has one data element, and if internal has two child nodes;• a 3-node has two data elements, and if internal has three child nodes;• a 4-node has three data elements, and if internal has four child nodes.2-3-4 Tree PropertiesEvery node (leaf or internal) is a 2-node, 3-node or a 4-node, and holds one, two, or three data elements, respectively.All leaves are at the same depth (the bottom level).All data is kept in sorted order.Tree height.• Worst case: lg N [all 2-nodes]• Best case: log4 N = 1/2 lg N [all 4-nodes]• Between 10 and 20 for 1 million nodes.• Between 15 and 30 for 1 billion nodes.Guaranteed logarithmic performance for both search and insert.2-3-4 Tree Insertion1. If the current node is a 4-node:• Remove and save the middle value to get a 3-node.• Split the remaining 3-node up into a pair of 2-nodes (the now missing middle value is handled in the next step).• If this is the root node (which thus has no parent):• the middle value becomes the new root 2-node and the tree height increases by 1. Ascend into the root.• Otherwise, push the middle value up into the parent node. Ascend into the parent node.2. Find the child whose interval contains the value to be inserted.3. If that child is a leaf, insert the value into the child node and finish.• Otherwise, descend into the child and repeat from step 12-3-4 Tree Example: Insertion112 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 4512-3-4 Tree Example1 12 82 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 4512811 12 8 225 6 14 28 17 7 52 16 48 68 3 26 29 53 55 451281Insert 22-3-4 Tree Example1281 21 12 8 225 6 14 28 17 7 52 16 48 68 3 26 29 53 55 451281Insert 22-3-4 Tree Example1 12 8 2256 14 28 17 7 52 16 48 68 3 26 29 53 55 452-3-4 Tree Example1281 2Insert 251 12 8 2256 14 28 17 7 52 16 48 68 3 26 29 53 55 451281 2252-3-4 Tree Example1281 2Insert 251 12 8 225614 28 17 7 52 16 48 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 61281 2251 12 8 225614 28 17 7 52 16 48 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 6128122561281 225128121 12 8 22561428 17 7 52 16 48 68 3 26 29 53 55 45252-3-4 Tree ExampleInsert 146128121 12 8 22561428 17 7 52 16 48 68 3 26 29 53 55 45252-3-4 Tree ExampleInsert 1461281214625128121 12 8 2256142817 7 52 16 48 68 3 26 29 53 55 45252-3-4 Tree ExampleInsert 28614128121 12 8 2256142817 7 52 16 48 68 3 26 29 53 55 45252-3-4 Tree ExampleInsert 286128121462528141 12 8 22561428177 52 16 48 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 171281214625281 12 8 22561428177 52 16 48 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 7128121462528128121462528171 12 8 2256142817752 16 48 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 7128121462528171 12 8 2256142817752 16 48 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 7128121462528171281214625281771 12 8 225614281775216 48 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 521281214625281771 12 8 225614281775216 48 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 5212812146252817712812146252817752128121462528177521 12 8 22561428177521648 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 16128121462528177521 12 8 22561428177521648 68 3 26 29 53 55 452-3-4 Tree ExampleInsert 161281214625281775212812146252817752161 12 8 2256142817752164868 3 26 29 53 55 452-3-4 Tree ExampleInsert 4812812146252817752161 12 8 2256142817752164868 3 26 29 53 55 452-3-4 Tree ExampleInsert 4812812146252817752161281214625281774816521 12 8 22561428177521648683 26 29 53 55 452-3-4 Tree ExampleInsert 681281214625281774816521 12 8 22561428177521648683 26 29 53 55 452-3-4 Tree ExampleInsert 68128121462528177481652128121462528177481652681 12 8 22561428177521648683 2629 53 55 452-3-4 Tree ExampleInsert 3, 26128121462528177481652681 12 8 22561428177521648683 2629 53 55 452-3-4 Tree ExampleInsert 3, 2612812146252817748165268128121462528177481652683261 12 8 22561428177521648683 2629 5355452-3-4 Tree ExampleInsert 551281214625281774816526832653291 12 8 22561428177521648683 2629 5355452-3-4 Tree ExampleInsert 55128121462528177481652683265329128121462528177481652683265329551 12 8 22561428177521648683 2629 5355452-3-4 Tree ExampleInsert 45128121462528177481652683265329551 12 8 22561428177521648683 2629 5355452-3-4 Tree ExampleInsert 451281214625281774816526832653295512812146252817748165268326532955452-3-4 Tree: Delete• Leaf:• Just delete the key• Make sure that a leaf is not empty after deleting a keyDelete 22-3-4 Tree: Delete• Leaf:• When key deletion would create an empty leaf, borrow a key from leaf 's immediate siblings (i.e. to the left and then right).2-3-4 Tree: Delete• Leaf:• If siblings are 2-nodes (no immediate sibling from which to borrow a key), steal a key from our parent by doing the opposite of a split.Delete 62-3-4 Tree: Delete• What if parent is a 2-node (one key)?2-3-4 Tree: Delete• What if parent is a 2-node (one key)?• Steal from siblings (parent’s)• Merge2-3-4 Tree: Delete• What if parent is a 2-node (one key)?• Steal from siblings (parent’s)• Merge2-3-4 Tree: Delete• Internal Node:• Delete the predecessor, and swap it with the node to be deleted.Delete 5: first delete 4, then swap 4 for 5.2-3-4 Tree: Delete• Internal Node:• Delete the predecessor, and swap it with the node to be deleted.• Key to delete may move.Delete 2: first delete 1, then swap 1 for 2.2-3-4 Tree Example: DeleteDelete 3,17,5512812146252817748165268326532955452-3-4 Tree Example: Delete12812146252874816526826532945Delete 1: borrow from siblings (rotate)2-3-4 Tree Example: DeleteDelete 112826142528748165226532945682-3-4 Tree Example: DeleteDelete 52: borrow from sibling12826142528748165226532945682-3-4 Tree Example: DeleteDelete 52: borrow from sibling128261425287451648265329682-3-4 Tree Example: DeleteDelete 48: borrow from parent128261425287451648265329682-3-4 Tree Example: DeleteDelete 48: borrow from parent1282614252874516265329682-3-4 Tree Example: DeleteDelete 2: borrow from parent, and parent128261425287451626532968merge2-3-4 Tree Example: DeleteDelete 2:
View Full Document
Unlocking...