What is a 2-3-4 Tree?
A 2-3-4 Tree is a multiway search tree. It’s a self-balancing tree; it’s always perfectly balanced with every leaf node at equal distance from the root node.
Other than the leaf node, every node can be one of three types:
-
2-Node has two child nodes and one data element
-
3-Node has three child nodes and two data elements
-
4-Node has four child nodes and three data elements
Structure of a 2-Node
Like a binary search tree, when a node only contains one data element the left subtree of that node (parent node) will contain nodes with data elements valued less than the parent node’s data elements, while the right subtree will contain nodes with data elements valued greater than the parent node’s data elements. Nodes having the same value as their parent node can be inserted in either the left or the right subtree.
Structure of a 3-Node
When a node contains two data elements, the left data element is less than the right data element.
The leftmost subtree of a node containing two data elements, we will call the parent node, will contain nodes with data elements less than the parent node’s lesser valued data element.
The rightmost subtree of the parent node will contain nodes with data elements greater than the parent node’s greater valued data element.
As a node with two data elements can have three child nodes, the middle subtree of the parent node will have nodes with data elements greater than the lesser element of the parent node, but lesser than the greater element of the parent node.
Structure of a 4-Node
When a node contains three data elements, the values of those data elements are sorted from least to greatest (left to right). The structure of a 4-Node is similar to that of a 3-Node with the addition of an extra data element hence, resulting in the possibility of 4 subtrees.
Insertion
When inserting a new data element in a 2-3-4 Tree, always remember that new elements are inserted only in leaf nodes.
Simple Insertion: After the appropriate leaf node is located, we must check the number of data elements it contains. If the leaf node contains less than 3 data elements, we will do a simple insertion.