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 means a tree where every node with children (internal node) has either two children (2-node) and one data element or three children (3-node) and two data elements or four children (4-node) and three data elements.
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.
Contents |
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.
Find the element to be deleted. If the element is not in a leaf node remember its location and continue searching until a leaf, which will contain the element’s successor, is reached. Then swap the leaf element with the one to be deleted, and delete the element node. It is simplest to make adjustments to the tree from the top down, as the element to be deleted is pursued that guarantee that the leaf node found is not a two-node, so that we can delete something from it and leave it there.
The adjustments we make on the way to a leaf are as follows: Assume, without loss of generality, that the child we are about to go to is the leftmost.
If we're at the root
If the root and both children are two-nodes, combine all three elements into the root, making a 4-node and shortening the tree, Otherwise, if the root and left child are two-nodes, the right child isn't a two-node. Perform a left rotation to make the left sibling a 3-node, and move to the left child.
From now on, we can be sure that we're at a node which is not a 2-node.
If the leftmost child is not a 2-node, just move to it. If the adjacent sibling is not a 2-node, perform a left rotation using its leftmost element to make the left child a 3-node. Otherwise, add the leftmost element of the parent and the single element of the sibling to the left node, making it a 4-node, and discard the empty sibling. Go to the left-most child.
Deletion in a 2-3-4 tree is O(log n), assuming transfer and fusion run in constant time ( O(1) ).[1][3]
|