What is a two-three-four tree?
1. What are two-three-four trees?
A two-three-four Tree is a four-order B Tree (Balance Tree). It is a multi-path search Tree, requiring all nodes to have the same depth.
The node can only be one of 2-node, 3-node, or 4-node.
- 2-node: a 1-element node with 2 child nodes
- 3-node: a 2-element node with 3 child nodes
- 3-node: A 3-element node with 4 child nodes
A 2-3-4 tree node has at least one element, which complies with the property of a binary search tree, that is, the parent node is larger than the left child node and smaller than the right child node. However, for a 2-3-4 tree with multiple elements, each element must be larger than its left and the elements in its left child tree
2, two-three-four tree query
The query operation of two-three-four tree is like the ordinary binary search tree, but because the number of node elements is uncertain, it is not convenient to realize in some programming languages. The realization generally uses its equivalent tree, red black tree, that is, to transform into red black tree, and then search
3, 2-3-4 tree generation process
