*** Welcome to piglix ***

2–3–4 tree


In computer science, a 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that is commonly used to implement dictionaries. The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:

2-node

3-node

4-node

2–3–4 trees are B-trees of order 4; like B-trees in general, they can search, insert and delete in O(log n) time. One property of a 2–3–4 tree is that all external nodes are at the same depth.

2–3–4 trees are an isometry of red–black trees, meaning that they are equivalent data structures. In other words, for every 2–3–4 tree, there exists at least one red–black tree with data elements in the same order. Moreover, insertion and deletion operations on 2–3–4 trees that cause node expansions, splits and merges are equivalent to the color-flipping and rotations in red–black trees. Introductions to red–black trees usually introduce 2–3–4 trees first, because they are conceptually simpler. 2–3–4 trees, however, can be difficult to implement in most programming languages because of the large number of special cases involved in operations on the tree. Red–black trees are simpler to implement, so tend to be used instead.

To insert a value, we start at the root of the 2–3–4 tree:-

To insert the value "25" into this 2–3–4 tree:

Consider just leaving the element there, marking it “deleted,” possibly to be re-used for a future insertion.

To remove a value from the 2–3–4 tree:

Make the following adjustments when a 2-node – except the root node – is encountered on the way to the leaf we want to remove:

Once the sought value is reached, it can now be placed at the removed entry's location without a problem because we have ensured that the leaf node has more than 1 key.

Deletion in a 2–3–4 tree is O(log n), assuming transfer and fusion run in constant time ( O(1) ).


...
Wikipedia

...