CODEWITHSUNDEEP
algorithmdata-structurestreeb-tree
nujabes
nujabes

Reputation: 901

In b tree data structure, when does height decrease?

In b tree data structure, when does height decrease?

I know when the b tree height is incremented by 1 - When in the root node happens overflow, so when the root node splits, the height of b tree incremented.

However, I want to know when the height of b tree data structure decrease?

Upvotes: 1

Views: 1633

Answers (1)

karastojko
karastojko

Reputation: 1181

When a key in a b-tree T is deleted, there are cases when some of the nodes involved in the deleting operation remain with the number of keys less than tree degree (call it t). In such cases, some of the nodes require merging, so again all nodes of the given B tree have at least t - 1 keys. Obviously, consecutive deleting nodes causes merging nodes, which further causes dropping of the entire node (by moving its keys to another node). When all nodes in a tree level are dropped, tree height decreases.

Upvotes: 2

Related Questions