Finding Minimum Key and Predecessor in B-Tree

Question

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 1

You can write recursive function to traverse a B-tree (from the root) via left and right nodes of each parent node. During this you can compare all values and find minimum and its parent node.

Answer 2

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

Answer 3

#define BT_T 3// degree of B-tree
#define INF -32768

//struct of a node of B-tree
struct bnode {
    int num;//number of keys in a bnode
    int leaf; //1 for leaf,0 for not leaf
    int value[2*BT_T -1]; //suppose all the key in B-tree is positive.
    struct bnode *child[2*BT_T];
};

//minimum is the most left leaf's first value.
int find_min(struct bnode *p) {
    if(p==NULL)
        return -1;
    if(!p->leaf)
        find_min(p->child[0]);
    else
        return p->value[0];
}

//a predecessor's candidate of a given key are less than the key.
//the predecessor among the candidate is the largest one of them.
int find_predecessor(struct bnode *node,int val) {
    int i,temp,max = INF;
    for(i=0;i<num-1;i++) {
        if(node->value[i] >= val)
            break;
        if(max > node->value[i]) ｛
            max = ->value[i];
            temp = find_predecessor(node->child[i],val);
    max = (temp>max?temp:max);
        ｝
    }
    return max;
    //when there is no predecess,max is INF.
}