Finding Minimum Key and Predecessor in B-Tree

algorithm b-tree array-algorithms
user2558869 picture user2558869 · Jul 8, 2013 · Viewed 7.5k times · Source

Explain how to find the minimum key stored in a B-tree and how to find the predecessor of a given key stored in a B-tree.

Answer

SRF picture SRF · Jul 8, 2013

To Find Minimum Key

  • Go to leftmost children recursively until you find NULL

To find the predecessor

  • First find the given element, by recursively traversing the tree top to bottom

  • Then there are two cases

  • If that element have left children, find the largest in that sub-tree rooted at that left children

  • If that element haven't left children, you have to go upward

Related questions

What are the differences between B-tree and B*-tree, except the requirement for fullness?

I know about this question, but it's about B-tree and B+-tree. Sorry, if there's similar for B*-tree, but I couldn't find such. So, what is the difference between these two trees? The wikipedia article about B*-trees is …

Read More
saving Btrees to a disk file and read it

I want to save a Btree(not sure a binary one) in a disk file. and then read it to the memory. some Level-order traversal may be a good way for a binary Btree. but if it is not a …

Read More
What is satellite information in data structures?

Taken from Introduction to Algorithms by Thomas Cormen: "To keep things simple, we assume, as we have for binary search trees and red-black trees, that any “satellite information” associated with a key is stored in the same node as the …

Read More