ADS_midterm
5-1
分数 16
作者 杨洋
单位 浙江大学

The function FindKey is to check if a given key is in a B+ Tree with its root pointed by root.

Return true if key is in the tree, or false if not. The B+ tree structure is defined as following:

static int order = DEFAULT_ORDER;
typedef struct BpTreeNode BpTreeNode;
struct BpTreeNode {
    BpTreeNode** childrens;  /* Pointers to childrens. This field is not used by leaf nodes. */
    ElementType* keys;
    BpTreeNode* parent;
    bool isLeaf;  /* 1 if this node is a leaf, or 0 if not */
    int numKeys;  /* This field is used to keep track of the number of valid keys. 
    In an internal node, the number of valid pointers is always numKeys + 1. */
};


bool FindKey(BpTreeNode * const root, ElementType key){
    if (root == NULL) {
            return false;
    }
    int i = 0;
    BpTreeNode * node = root;
    while (
8 分
) { i = 0; while (i < node->numKeys) { if (
8 分
) i++; else break; } node = node->childrens[i]; } for(i = 0; i < node->numKeys; i++){ if(node->keys[i] == key) return true; } return false; }