CS131: 2-3-4 Tree [Draft]

2-3-4 Tree is a perfectly balanced tree (all leafs are on the same level) with O(log n) worst case time for find, insert and remove operations. As the name suggests every node of the tree has 2,3 or 4 children.

Operations

Find

Insert

Find a node with key k. If a node X with key k is found proceed to X's left until a leaf node is found. If a 3 key node is found we move the middle key up to its parent. Parent has at most two keys.

Fig:

Insertion may increase the depth of tree by one level.

Remove

Find the node X with key k to remove If X is a leaf, remove it ans return from function. If X is an internal node search for a leaf node Y with smallest key k' such that k" > k and replace Replace X with Y so that X is removed and Y takes its place.

If we find a one key node on the path of a leaf node we want to remove we continuously do the following 3 steps (except the root node):

1. If X is an one key node that is not root move one key from its adjacent sibling by rotation.

Fig:

1. If there is no adjacent sibling with more than one key take one key down from the parent. Internal nodes always have two or three keys. Moving down one key may trigger further operations if the parent is left with one key (verify).

Fig:

1. If parent is root and there is no adjacent sibling with more than one key (1 and 2 fails) create a 3 key node to form the root. This is called a fusion operation. The tree level is decreased by one level.

Fig:

Remove may decrease the tree by one level.