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.
Finding Minimum Key and Predecessor in B-Tree
-
02-06-2022 - |
سؤال
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.
المحلول 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
#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.
}
لا تنتمي إلى StackOverflow