2-3-4 tree
From Wikipedia, the free encyclopedia
A 2-3-4 tree in computer science is a B-tree of order 4.
Like B-trees in general, 2-3-4 trees are a kind of self-balancing data structure that can be used as a dictionary. They can search, insert and delete in O(log n) time, where n is the number of elements in the tree.
2-3-4 trees are relatively difficult to implement in most programming languages because of the large number of special cases involved in operations on the tree. Red-black trees (see below) are simpler to implement, so they tend to be used instead.
[edit] Background
2-3-4 trees store data as individual items called elements. These are grouped into nodes. Each node is either
- a 2-node, i.e. it contains 1 element and has 2 children, or
- a 3-node, i.e. it contains 2 elements and has 3 children, or
- a 4-node, i.e. it contains 3 elements and has 4 children.
a 2-node
|
a 3-node
|
a 4-node
|
Each child is a (possibly empty) sub 2-3-4 tree. The root node is one which has no parent; it serves as a starting point when walking through the tree because every other node can be reached from it. A leaf node is a node with no children.
As with B-trees, 2-3-4 trees are ordered: each element must be greater than or equal to any others to its left and in its left subtree. Each child then becomes an interval bracketed by the elements to its left and right.
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. The insertion and deletion operations on 2-3-4 trees are also equivalent to color-flipping and rotations in red-black trees. This makes them an important tool for understanding the logic behind red-black trees.
