Let's say we have a b tree of order 4 and it has 3 levels. All nodes are completely filled. Now if we want to insert a key with maximum value ( than all keys present in the tree). For this, we have to go to the rightmost node at the last level. As this last level is also filled, now how can we proceed further as all the nodes are full. We cant do a split here. So we are left with creating a new node below the rightmost node. But this tree contradicts the balancing property. I want to know the intuition behind self-balancing nature.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ When a B-tree node becomes overfull, it is split into two, and a new entry is inserted into the parent. The only way that the height of a B-tree can increase is if the root node splits. $\endgroup$– Pseudonym ♦Jun 15, 2021 at 4:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
That's not how insertion into a full B-tree works. You can read about this in detail in CLRS chapter 18, section 18.2.
In brief, when you want to insert you start at the root and work your way down to the appropriate leaf node, splitting any full nodes you find on the way. That way when you come to insert the new value you are guaranteed that the parent of the node where you do the insert isn't full. There is a special case when the root is full, when you create a new empty root as a parent to the old root, so that the old root can be split. This is the only time that the tree increases in height, and of course it causes every leaf to increase its depth by 1, maintaining the same-depth property.
-
$\begingroup$ yes , now i understood it. Instead of creating a new child node , a new parent node will be created. So the level of each node will get increased by 1. $\endgroup$ Jun 18, 2021 at 2:57