0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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$
    – MathCurious
    Jul 28, 2021 at 8:17

0

Reset to default

Your Answer

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