What is a 2-3-4 Tree? Properties and Applications.
Learn and know What is a 2-3-4 Tree, it’s Properties and Applications.
What is a 2-3-4 Tree?
- 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–3–4 trees are B-trees of order 4.
- Property of a 2–3–4 tree is that all external nodes are at the same depth.
- 2–3–4 trees are isomorphic to red–black trees, meaning that they are equivalent data structures. for every 2–3–4 tree, there exists at least one red–black tree with data elements in the same order.
- 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.
Properties of 2-3-4 Tree
- Every node (leaf or internal) is a 2-node, 3-node or a 4-node, and holds one, two, or three data elements, respectively.
- All leaves are at the same depth (the bottom level).
- All data is kept in sorted order.
Insertion Operation of 2-3-4 Tree
Start at the root of the 2–3–4 tree
- If the current node is a 4-node
- Remove and save the middle value to get a 3-node.
- Split the remaining 3-node up into a pair of 2-nodes (the now missing middle value is handled in the next step).
- If this is the root node (which thus has no parent):
- the middle value becomes the new root 2-node and the tree height increases by 1. Ascend into the root.
- Otherwise, push the middle value up into the parent node. Ascend into the parent node.
- Find the child whose interval contains the value to be inserted.
- If that child is a leaf, insert the value into the child node and finish
- Otherwise, descend into the child and repeat from step 1