Given a B-Tree that contains the keys $k$ and $2k$, we know the height of the tree will be reduced if we delete the key $k$.

Prove or disprove: The height of the tree will also reduce if we remove $2k$.

Now the solution is that it's true, but the explanation is lacking.. When the height of a B-Tree is reduced it means that the root only has one element and both it's children have the minimum amount of keys, but what's the connection between keys $k$ and $2k$? Why can't they be on opposite sides of the level of the leaves and for example when we remove $k$ we get an underflow and when we remove $2k$ we don't? I feel like I'm missing an important property of B-Trees and I just can't move on from it..

  • $\begingroup$ I don't understand the question at all. How does the value of the key matter? The height of a B-tree is dependent on the number of keys and the load factor of all its nodes, not any specific values. Obvious example: Consider a B-tree with $m=100$, which contains exactly three keys, $1$, $k$, and $2k$. It will only ever have a height of 1 unless you insert 97 more items. $\endgroup$
    – Pseudonym
    Jul 28, 2021 at 7:48
  • 1
    $\begingroup$ The question is essentially if the height of the tree reduced if we remove a key x, why does the height of the tree necessarily decreases if we remove a key y which is larger than x? $\endgroup$ Jul 28, 2021 at 8:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.