Is it a B+ tree?
分数 6
作者 刘金飞
单位 浙江大学

The teacher wants to write the IsBpT function to check if the trees submitted by students satisfy the definition of the B+ tree of a given order (e.g., order 4) learned in our class. The B+ tree structure is defined as follows:

typedef struct BpTNode BpTNode; 
struct BpTNode { 
    bool isLeaf; /* 1 if this node is a leaf, or 0 if not */
    bool isRoot; /* 1 if this node is the root, or 0 if not */
    BpTNode** children; /* Pointers to children. This field is not used by leaf nodes. */ 
    ElementType* keys;
    int num_children; /* Number of valid children (not NULL) */
    int num_keys; /* Number of valid keys */
};

Fortunately, the students are all brilliant, so the B+ trees they submit guarantee to meet the following properties:

  1. There is a root node, and all leaf nodes are at the same depth;

  2. The key values stored in all leaf nodes are arranged in strictly ascending order from left to right.

Your task is to complete the function IsBpT as follows so that the teacher can determine whether a tree submitted by a student meets the other properties required by the definition of the B+ tree of a given order. Return true if the tree is a B+ tree, or false if not.

bool IsBpT(BpTNode* node, int order) {
    if (node->isLeaf == 1) { /* this is a leaf node */
        if (node->isRoot == 1) { /* this tree has only one node */
            if (node->num_keys < 1 || node->num_keys > order) return false;
        }
        else {
            if (node->num_keys < (order + 1) / 2 || node->num_keys > order) return false;
        }
    }
    else {
        /* check the property of the tree structure */
        if (node->num_keys != node->num_children - 1) return false;
        if (node->isRoot == 1) { /* this is the root node */
            if (node->num_keys < 1 || node->num_keys > order - 1) return false;
            else if (node->num_children < 2 || node->num_children > order) return false;
        }
        else {
            if (
3 分
|| node->num_keys > order - 1) return false; else if (node->num_children < (order + 1) / 2 || node->num_children > order) return false; } /* check the property of the value of key */ for (int i = 0; i < node->num_keys; i++) { BpTNode* key_node =
3 分
; while (key_node->isLeaf == 0) { key_node = key_node->children[0]; } if (node->keys[i] != key_node->keys[0]) return false; } for (int i = 0; i < node->num_children; i++) { if (IsBpT(node->children[i], order) == false) return false; } } return true; }