CODEWITHSUNDEEP
algorithmdata-structuresb-tree
pfinferno
pfinferno

Reputation: 1945

Finding successor in a B-Tree

I posted a question earlier about finding a successor in a balanced binary search tree. Now I'm reading up on B-Trees (where nodes can have more than 2 children), and it had me wondering how would I find the successor of a key in a B-Tree? Would it generally be the same as in a regular BST?

Thanks in advance.

Upvotes: 2

Views: 3205

Answers (1)

templatetypedef
templatetypedef

Reputation: 372724

The logic is similar, but needs to be slightly modified to handle the fact that there are multiple children possible.

As before, do a lookup for the value. Then, if there are any values greater than that value in the block, find the smallest of them. If there are any children in the subtree between those values, descend into that subtree and take the minimum value there. Otherwise, take the successor to be the value you found in the first step.

If there are no successors, back up in the tree until there is one. Then, use the above procedure to get the successor.

Hope this helps!

Upvotes: 1

Related Questions