2-3-4 Trees
Explore the structure and properties of 2-3-4 Trees, an advanced variant of 2-3 Trees, to understand how nodes hold up to three keys and four children. Learn the key ordering rules and insertion techniques to enhance your knowledge of trees crucial for coding interviews.
We'll cover the following...
Introduction
2-3-4 is a search tree which is an advanced version of 2-3 Trees. This tree can accommodate more keys and hence more child nodes as compared to 2-3 Trees. Likewise, a 2-3-4 Tree satisfies all the properties covered in 2-3 Trees as well as some additional key features:
-
Each internal node can contain a max. of three keys
-
Each internal node can have a max. of four child nodes
-
In the case of three keys (left, mid, and right) at an internal node, all the keys present at the LeftChild node are smaller than the left key. This can be mathematically expressed as,
...