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
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.
9 7 12 14 15 20 23
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.
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 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).
A 2-3-4 Tree is a search tree that is either empty or satisfies the following 4 properties:
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.
Unlike majority of the material in this site, this article is available under GPL and not under Creative Commons license (see more).