CMSC 132 Object Oriented Programming II 2 3 4 Tree CMSC 132 Summer 2017 1 2 3 4 Tree Self balancing tree every 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 Properties Every 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 Insertion 1 2 3 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 Find the child whose interval contains the value to be inserted If that child is a leaf insert the value into the child node and finish Otherwise descend into the child and repeat from step 1 2 3 4 Tree Example Insertion 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 1 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 1 8 12 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 Insert 2 1 8 12 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 Insert 2 1 8 12 1 2 12 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 1 2 Insert 25 12 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 1 2 8 Insert 25 12 1 2 12 25 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 Insert 6 1 2 12 25 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 8 Insert 6 1 2 12 25 1 2 6 12 25 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 1 2 6 Insert 14 12 25 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 1 2 6 8 Insert 14 12 25 1 2 6 12 14 25 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 Insert 28 8 1 2 6 12 14 25 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 Insert 28 8 14 8 1 2 6 12 14 25 1 2 6 12 25 28 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 Insert 17 8 14 1 2 6 12 25 28 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 14 8 14 1 2 6 12 25 28 Insert 7 1 2 6 12 17 25 28 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 14 1 2 6 12 17 25 28 Insert 7 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 2 8 14 8 14 1 2 6 12 17 25 28 Insert 7 1 6 7 12 17 25 28 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 2 8 14 1 6 7 12 Insert 52 17 25 28 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 2 8 14 1 6 7 12 17 25 28 Insert 52 8 2 2 8 14 25 1 6 7 12 17 28 52 1 6 7 14 25 12 17 28 52 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 2 1 6 14 7 12 Insert 16 25 17 28 52 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 2 1 6 14 7 12 8 25 17 28 52 2 1 Insert 16 6 14 7 12 25 16 17 28 52 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 2 1 6 14 7 Insert 48 12 25 16 17 28 52 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 2 1 6 14 25 7 12 16 17 28 52 8 Insert 48 2 1 6 14 7 12 25 16 17 28 48 52 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45 8 2 1 6 14 7 Insert 68 12 25 16 17 28 48 52 2 3 4 Tree Example 1 12 8 2 25 6 14 28 17 7 52 16 48 68 3 26 29 …
View Full Document
Unlocking...