2-3-4 tree

2-3-4 tree is a not-binary search tree data structure, a simplified form of the B-tree. 2-3-4 trees are B-trees of order 4. Same as all B-trees, they are able to search, insert and delete in O(log n) time. They are also known as 2-4 trees. Search, insertion and deletion inside these data structures is well described in[1]

The demonstration of the 2-4-3 tree. Bottom area provides some built-in documentation. Click on the node to get its value into input field (for search or deletion). Nodes can also be moved with the mouse.

Nodes

Each internal node in the tree has between two and four children and also stores items that are key-value pairs. Items inside the node are ordered by the key. Children of the node are attached "between" its items. They could also be attached before the first or after last item in the node but to describe algorithms simpler, the node is supplemented by the two "pseudo items" that stand at the boundaries of its key sequence, storing no data. They allow to define that any child is attached on the boundary of some two items. All external nodes have the same depth.

Search

Search starts from the root. If the required key is not in the current tree node, it is necessary to determine which way (into which child) to follow continuing the search. For this, it is enough to find the two keys in the node sequence between those the search key falls. The child that is "attached" between these two keys is the child to follow. If there is no child at this position, the tree does not contain the given search key.

Insertion

Determine the target node by searching with the key of the item we add. If this node has less than three items, just add the new item to it. If not, the target must be splitted after addition, replacing it by the two nodes. The first of these nodes gets the first two keys, the second gets the last key and next to last key is "sent up the tree", adding it to the parent of the original (now splitted) node. If then the parent node overflows, it must be splitted as well.

Deletion

Deletion in 2-3-4 tree is the most complex operation. First, it is necessary to find the item to be deleted, using the search algorithm described above. Then, the item being deleted must be migrated into the bottom of the tree, swapping it (if required) with the item which precedes it in in-order traversal. After that the item can be deleted but if there are not enough items in the node, underflow occurs. In the case of underflow,a part of the tree must be newly rebuilt (rules that define how to do this efficiently cover various special cases).

Properties of 2-3-4 Trees

A 2-3-4 Tree is a search tree that is either empty or satisfies the following 4 properties[2]:

  1. Each node can store up till three values, with optional children attached between the values (as ordered by the key).
  2. Each internal node has two, three and four children only.
  3. The height of all the leaves/external nodes is the same (O (log n) ).
  4. Let Lchild and Mchild denote the children of a 2-Node. Let Lkey be the only element present in this node. All elements in the sub 2-3-4 Tree with root Lchild have key less than Lkey, while all elements in the sub 2-3-4 Tree with root Mchild have key greater than Lkey.
  5. Let Lchild, Mchild and Rchild denote the children of a 3-Node. Let Lkey and Rkey be the two elements in this node. Then, Lkey < Rkey, all keys in the sub 2-3-4 Tree with root Lchild are less than Lkey, all keys in the sub 2-3-4 Tree with root Mchild are less than Rkey and greater than Lkey, and all keys in the sub 2-3-4 Tree with root Rchild are greater than Rkey.
  6. All external (leaf) nodes of a 2-3-4 tree are at the same depth.

2-3-4 trees are isometry of red-black trees: for every 2-3-4 tree, there exists at least one red-black tree with data elements in the same order. Also, tree operations may be viewed as equivalent. 2-3-4 are easier to understand, but red-black trees may be easier to implement in most of the programming languages.

References

  1. 1 Grama, A (2004) (2,4) Trees. CS251: Data Structures Lecture Notes. Dept of Computer Science, Purdue University (recommended).
  2. 2 Bondhugula, U.K (website, also provides applet)


Licensing note

Unlike majority of the material in this site, this article is available under GPL and not under Creative Commons license (see more).