2–3–4 tree
From Wikipedia, the free encyclopedia
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:
- a 2-node has one data element, and if internal has two child nodes;
- a 3-node has two data elements, and if internal has three child nodes;
- a 4-node has three data elements, and if internal has four child nodes;
- 2-node
- 3-node
- 4-node
2–3–4 tree | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | tree | |||||||||||||||||||||||
|
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.