# Deletion in B Trees

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..

• 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. Jul 28 at 7:48
• 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? Jul 28 at 8:17