A 2-4 tree is a rooted tree with the following properties:
Adding a leaf to a 2-4 tree is easy (see Figure 9.2). If we want to add a leaf as the child of some node on the second-last level, we simply make a child of . This certainly maintains the height property, but could violate the degree property; if had 4 children prior to adding , then now has 5 children. In this case, we split into two nodes, and ', having 2 and 3 children, respectively. But now ' has no parent, so we recursively make ' a child of 's parent. Again, this may cause 's parent to have too many children in which case we split it. This process goes on until we reach a node that has fewer than 4 children, or until we split the root, , into two nodes and . In the latter case, we make a new root that has and as children. This simultaneously increases the depth of all leaves and so maintains the height property.
|
Since the height of the 2-4 tree is never more than , the process of adding a leaf finishes after at most steps.
Removing a leaf from a 2-4 tree is a little more tricky (see Figure 9.3). To remove a leaf from its parent , we just remove it. If had only two children prior to the removal of , then is left with only one child and violates the degree property.
|
To correct this, we look at 's sibling, . The node is sure to exist since 's parent has at least 2 children. If has 3 or 4 children, then we take one of these children from and give it to . Now has 2 children and has 2 or 3 children and we are done.
On the other hand, if has only two children, then we merge and into a single node, , that has 3 children. Next we recursively remove from the parent of . This process ends when we reach a node, , where or its sibling has more than 2 children; or we reach the root. In the latter case, if the root is left with only 1 child, then we delete the root and make its child the new root. Again, this simultaneously decreases the height of every leaf and therefore maintains the height property.
Again, since the height of the tree is never more than , the process of removing a leaf finishes after at most steps.
opendatastructures.org