algorithm - 在 B-Tree 中找到最小键和前驱

Question

解释如何找到存储在 B-tree 中的最小键以及如何找到存储在 B-tree 中的给定键的前任。

Answer 1

查找最小键

• 递归到最左边的孩子，直到找到NULL

寻找前任

• 首先通过从上到下递归遍历树来找到给定的元素

• 那么有两种情况

• 如果该元素有左子元素，则在该子树中找到以该左子元素为根的最大元素

• 如果该元素没有留下子元素，则必须向上

Answer 2

您可以编写递归函数通过每个父节点的左右节点遍历 B 树（从根）。在此期间，您可以比较所有值并找到最小值及其父节点。

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