2-4Trees

2-4Trees?

• 2-4Trees are subtype of tree called B-Trees.
  • B-Trees allow the number of data and children to vary in a node or a block.

• 2-4Trees aim to guarantee O(log N) operations by maintaining some sort of balancing schema.

• 2-4 Trees enforce a more strict shape property than any of the trees.

  • Every leaf node must reside on the same level(=Every depths are same.)
• Order property requires that the data stored in a node is done so in ascending order. d1 < d2 < d3

This order property also extends to the children. c1 < d1 < c2 < d2 < c3 < d3 < c4

Adding in (2, 4) Trees

When data is entered in an empty state, the entered data becomes the root. Subsequently, when new data is entered, it is compared to the existing data and sorted in ascending order. If the root node contains three or more elements, it violates the Node property of (2, 4) Trees, which states that each node cannot have more than three elements. This situation is called Overflow, and it triggers a Promotion.

Promotion involves creating a new root node based on predefined rules (promoting the second or third element to the root), and the remaining data is divided as if forming a binary tree based on the Node property. These actions continue until all given inputs have been entered, ultimately resulting in the completion of a (2, 4) Trees structure.

Removing in (2, 4) Trees

• Internet source: 2-4 Trees. Removing and Underflow Retrieved from Edx Data Structures & Algorithm (Accessed on May 15, 2023).