2–3–4 tree | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | tree | |||||||||||||||||||||||
|
In computer science, a 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that can be 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–3–4 trees are B-trees of order 4; [1] 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 closely related to red–black trees by interpreting red links (that is, links to red children) as internal links of 3-nodes and 4-nodes, although this correspondence is not one-to-one. [2] Left-leaning red–black trees restrict red–black trees by forbidding nodes with a single red right child, which yields a one-to-one correspondence between left-leaning red–black trees and 2–3–4 trees.
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:
The simplest possibility to delete an element is to just leave the element there and mark it as "deleted", adapting the previous algorithms so that deleted elements are ignored. Deleted elements can then be re-used by overwriting them when performing an insertion later. However, the drawback of this method is that the size of the tree does not decrease. If a large proportion of the elements of the tree are deleted, then the tree will become much larger than the current size of the stored elements, and the performance of other operations will be adversely affected by the deleted elements.
When this is undesirable, the following algorithm can be followed 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)). [3] [5]
Since 2–3–4 trees are similar in structure to red–black trees, parallel algorithms for red–black trees can be applied to 2–3–4 trees as well.
2–3–4 tree | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | tree | |||||||||||||||||||||||
|
In computer science, a 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that can be 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–3–4 trees are B-trees of order 4; [1] 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 closely related to red–black trees by interpreting red links (that is, links to red children) as internal links of 3-nodes and 4-nodes, although this correspondence is not one-to-one. [2] Left-leaning red–black trees restrict red–black trees by forbidding nodes with a single red right child, which yields a one-to-one correspondence between left-leaning red–black trees and 2–3–4 trees.
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:
The simplest possibility to delete an element is to just leave the element there and mark it as "deleted", adapting the previous algorithms so that deleted elements are ignored. Deleted elements can then be re-used by overwriting them when performing an insertion later. However, the drawback of this method is that the size of the tree does not decrease. If a large proportion of the elements of the tree are deleted, then the tree will become much larger than the current size of the stored elements, and the performance of other operations will be adversely affected by the deleted elements.
When this is undesirable, the following algorithm can be followed 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)). [3] [5]
Since 2–3–4 trees are similar in structure to red–black trees, parallel algorithms for red–black trees can be applied to 2–3–4 trees as well.