B樹實作代碼

本代碼是參考《算法導論》講解實作的，自用，閱讀時對照書本便于了解相關變量定義。

// 算法導論版本B樹

typedef int KEY_TYPE;

typedef struct _btree_node
{
    //struct btree_node *children[M * 2];
    struct _btree_node **childrens; //大小靈活
    //KEY_TYPE keys[2 * M - 1];
    KEY_TYPE *keys;

    int num; //key的數量
    int leaf; //是否為葉子
} btree_node;

typedef struct _btree
{
    struct btree_node *root;
    int t; // 除根節點外，每個節點的最小孩子數量
    // key的最大數量為2t - 1, 一個内節點孩子節點數量最多為2t
} btree;


// desc:建立一個節點
// t:代表節點子樹最大數量的一半(M/2)
// leaf: 是否為葉節點
struct btree_node *btree_create_node(int t, int leaf)
{
    struct btree_node *node = (btree_node *)calloc(1, sizeof(btree_node));
    //assert的作用是現計算表達式 expression ，
    //如果其值為假（即為0），那麼它先向stderr列印一條出錯資訊，
    //然後通過調用 abort 來終止程式運作。
    if(node == NULL) assert(0);

    node->leaf = leaf;
    node->keys = (KEY_TYPE *)calloc(1, (2 * t - 1)*sizeof(KEY_TYPE));
    node->childrens = (btree_node **)calloc(1, (2 * t) * sizeof(btree_node *));
    node->num = 0;

    return node;

}

// desc:銷毀一個節點
void btree_destroy_node(btree_node *node)
{
    assert(node);

    free(node->childrens);
    free(node->keys);
    free(node);
}

//desc:建立一顆B樹
void btree_create(btree *T, int t)
{
    T->t = t;

    btree_node *x = btree_create_node(t, 1);

    T->root = x;
}

//desc:分裂節點
//x：待分裂節點的父節點
//i: 分裂節點為x的第幾個孩子
void btree_split_child(btree *T, btree_node *x, int i)
{
    int t = T->t;
    
    btree_node *y = x->children[i]; // 待分裂節點
    // 分裂後左半邊還是利用原來節點，右半邊開個新節點存
    btree_node *z = btree_create_node(t, y->leaf); 

    z->num = t - 1; //分裂出的右半邊節點數量

    int j = 0;
    //将右半邊key值寫入到z節點
    for(j = 0; j < t - 1; j++)
    {
        z->keys[j] = y->keys[j + t];
    }

    //非葉節點，處理孩子節點
    if(y->leaf == 0) 
    {
        for(j = 0;j < t; j++)
        {
            z->childrens[j] = y->children[j + t];
        }
    }

    y->num = t-1; //分裂的節點key數量改變
    //修改x節點（待分裂節點的父節點）
    //節點上移時，x節點可能需要後移i+1位置後孩子和key
    for(j = x->num; j >= i + 1; j--)
    {
        // x從x->num位置開始的孩子統一後移
        x->childrens[j + 1] = x->childrens[j];
    }

    x->childrens[i + 1] = z;
    // x節點從x->num位置開始的key統一後移
    for(j = x->num - 1; j >= i; j--)
    {
        x->keys[j + 1] = x->keys[j];
    }

    x->keys[i] = y->keys[t - 1];
    x->num += 1;
}

//desc:往不滿的節點裡插入
//x: 要插入的節點
//k: 要插入的關鍵字
void btree_insert_nonfull(btree *T, btree_node *x, KEY_TYPE k)
{
    int i = x->num - 1;

    if(x->leaf == 1) //葉子節點，可直接插入
    {
        // 節點内key升序
        while(i >= 0 && x->keys[i] > k)
        {
            x->keys[i + 1] = x->keys[i];
            i--;
        }
        x->keys[i + 1] = k;
        x->num += 1;
    }
    else   // 非葉子節點（插入節點必然在葉結點）
    {
        // 決定向x的哪個子節點遞歸下降
        while(i >= 0 && x->keys[i] > k) i--;
        // 遞歸降至一個滿子節點上，要分裂該子節點
        if(x->childrens[i + 1]->num == (2 * (T->t)) - 1)
        {
            btree_split_child(T, x, i + 1);
            // 确定向兩個孩子中哪個下降正确
            if(k > x->keys[i + 1]) i++;
        }
        // 遞歸
        btree_insert_nonfull(T, x->childrens[i + 1], k);
    }
    
}

// desc:往樹T中插入鍵為key的節點
void btree_insert(btree *T, KEY_TYPE key)
{
    btree_node *r = T->root;
    //根節點若滿(key數量 == 2 * t - 1)，分裂時，需要在頂上建立一個空節點（接受分裂後中間節點）
    if(r->num == 2 * T->t -1)
    {
        btree_node *node = btree_create_node(T->t, 0);
        T->root = node;

        node->childrens[0] = r;//空根節點的第一個孩子設定為真正根節點

        btree_split_child(T, node, 0);

        int i = 0;
        if(node->keys[0] < key) i++;
        btree_insert_nonfull(T, node->childrens[i], key);
    }
    else
    {
        btree_insert_nonfull(T, r, key);
    }

}
// 左右都是t - 1個key才合并
// 将child[idx], key[idx], child[idx + 1]合并為一個節點
void btree_merge(btree *T, btree_node *node, int idx)
{
    btree_node *left = node->childrens[idx];
    btree_node *right = node->childrens[idx + 1];

    int i = 0;

    // merge to left
    left->keys[T->t - 1] = node->keys[idx];
    // child[idx + 1]合并進去
    for(i = 0;i < T->t - 1; i++)
    {
        left->keys[T->t + i] = right->keys[i];
    }
    if(!left->leaf) // 非葉情況，右邊節點孩子要并進去
    {
        for(i = 0; i < T->t; i++)
        {
            left->childrens[T->t + i] = right->childrens[i];
        }
    }
    left->num += T->t;

    btree_destroy_node(right);

    // node 情況2c，即node非根，node的key減少1個
    for(i = idx + 1; i < node->num; i++)
    {
        node->keys[i - 1] = node->keys[i];
        node->childrens[i] = node->childrens[i + 1]
    }
    node->childrens[i + 1] = NULL;
    node->num -= 1;
    // 中間為根節點
    if(node->num == 0)
    {
        T->root = left;
        btree_destroy_node(node);
    }

}

// 從以根為x的子樹的删除時必須保證，節點遞歸調用自身時x中key數量至少為t(比最小key數量多1)

// b樹删除key
// node -- key的祖先節點（不一定是根）
// key -- 待删除的key
void btree_delete_key(btree *T, btree_node *node, KEY_TYPE key)
{
    // 先借位合并後删除
    if(node == NULL) return;
    int idx = 0, i;
    // 在節點内找key
    while (idx < node->num && key > node->keys[idx])
    {
        idx++;
    }
    
    // 在node裡找到待删的key
    if(idx < node->num && node == node->keys[idx])
    {
        // key在葉結點中
        if(node->leaf)
        {
            // node内所有key前移
            for(i = idx; i < node->num - 1; i++ )
            {
                node->keys[i] = node->keys[i + 1];
            }
            node->keys[node->num - 1] = 0;
            node->num--;

            // root
            if(node->num == 0)
            {
                free(node);
                T->root = NULL;
            }
            return ;
        }
        // key在内節點, 且左邊孩子key數量大于t，可借位
        else if(node->childrens[idx]->num >= T->t)
        {
            // 找節點左邊孩子最右key借位上移再删除這個孩子最右key
            btree_node *left = node->childrens[idx];
            node->keys[idx] = left->keys[left->num - 1];

            btree_delete_key(T, left, left->keys[left->num - 1]);
        }
        // key在内節點, 且右邊孩子key數量大于t，可借位
        else if(node->childrens[idx + 1]->num >= T->t)
        {
            btree_node *right = node->childrens[idx + 1];
            node->keys[idx] = right->keys[0];

            btree_delete_key(T, right, right->keys[0]);
        }
        // 兩邊孩子節點的key數量都為t - 1
        else
        {
            // 合并左右孩子，放到下一層
            btree_merge(T, node, idx);
            btree_delete_key(T, node->childrens[idx], key);
        }
    }
    else // 查找子節點
    {
        // key <= node->keys[idx]
        btree_node *child = node->childrens[idx];
        if(child == NULL)
        {
            printf("Cannot del key = %d\n", key);
            return ;
        }
        // 孩子節點的key數量要 >=t ,否則要借位
        if(child->num == T->t - 1)
        {
            btree_node *left = NULL;
            btree_node *right = NULL;
            // 擷取child的左右兄弟節點
            if(idx - 1 >= 0)
            {
                left = node->childrens[idx - 1];
            }
            if(idx + 1 <= node->num)
            {
                right = node->childrens[idx + 1];
            }

            if((left && left->num >= T->t) || (right && right->num >= T->t))
            {
                int richR = 0;
                if(right)
                {
                    richR = 1;
                }
                if(left && right)
                {
                    // 那邊孩子的key多
                    richR = (right->num > left->num) ? 1 : 0;
                }
                // 向右孩子借結點，父節點放到child節點上，然後向右child右兄弟借最左邊key放到父節點
                if(right && right->num >= T->t && richR)
                {
                    child->keys[child->num] = node->keys[idx];
                    child->childrens[child->num + 1] = right->childrens[0];
                    child->num++;

                    node->keys[idx] = right->keys[0];
                    for(i = 0; i < right->num - 1; i++)
                    {
                        right->keys[i] = right->keys[i + 1];
                        right->childrens[i] = right->keys[i + 1];
                    }

                    right->keys[right->num - 1] = 0;
                    right->childrens[right->num - 1] = right->childrens[right->num];
                    right->childrens[right->num] = NULL;
                    right->num--;
                }
                // 向左孩子借節點，用的是左孩子最右節點
                else
                {
                    // 把child的key和孩子節點指針數組先整體右移一位
                    for(i = child->num; i > 0; i--)
                    {
                        child->keys[i] = child->keys[i - 1];
                        child->childrens[i + 1] = child->childrens[i];
                    }
                    // 孩子數組調整一下
                    child->childrens[1] = child->childrens[0];
                    child->childrens[0] = left->childrens[left->num];
                    child->keys[0] = node->keys[idx - 1];

                    child->num ++;
                    
                    node->key[idx - 1] = left->keys[left->num - 1];
                    left->keys[left->num - 1] = 0;
                    left->childrens[left->num] = NULL;
                    left->num--;
                }            
            }
            // 如果左右兄弟都沒得借，那就合并
            else if((!left || (left->num == T->t - 1))
                && (!right || (right->num == T->t - 1)))
            {
                if(left && left->num == T->t - 1)
                {
                    // 孩子，父親，孩子左兄弟
                    btree_merge(T, node, idx - 1)
                }
                else if(right && right->num == T->t - 1)
                {
                    btree_merge(T, node, idx);
                }
            }
        }
        // 遞歸
        btree_delete(T, child, key);
    }
    

}

// 從樹T中删除key
int btree_delete(btree *T, KEY_TYPE key)
{
    if(!T->root) return -1;
    btree_delete_key(T, T->root, key);
    return 0;
}

void btree_traverse(btree_node *x)
{
    // bfs
    int i = 0;
    for(i = 0; i < x->num; i++)
    {
        if(x->leaf == 0)
        {
            btree_traverse(x->childrens[i]);
        }
        printf("%C", x->keys[i]);
    }

    if(x->leaf == 0) btree_traverse(x->childrens[i]);
}

void btree_print(btree *T, btree_node *node, int layer)
{
    btree_node *p = node;
    int i;
    if(p)
    {
        printf("\nlayer = %d keynum = %d is_leaf = %d\n", leaf, p->num, p->leaf);
        for(i = 0; i < node->num; i++)
        {
            printf("%c ", p->keys[i]);
        }
        printf("\n");
        layer++;
        for(i = 0; i <= p->num; i++)
        {
            if(p->childrens[i])
            {
                btree_print(T, p->childrens[i], layer);
            }
        }
    }
    else
    {
        printf("the tree is empty\n");
    }

}

// 在node[low, high] 中查找key
int btree_bin_search(btree_node *node, int low, int high, KEY_TYPE key)
{
    int mid;
    if(low > high || low < 0 || high < 0)
    {
        return -1;
    }

    while(low <= high)
    {
        mid = (low + high) / 2;
        if(key > node->keys[mid])
        {
            low = mid + 1;
        }
        else 
        {
            high = mid - 1;
        }
    }

    return low;
}

int main()
{
    btree T = {0};
    btree_create(&T, 3);
    srand(48);

    int i = 0;
    char key[26] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for(i = 0; i < 26; i++)
    {
        printf("%c ", key[i]);
        btree_insert(&T, key[i]);
    }
    // 從B樹T第0層開始列印
    btree_print(&T, T.root, 0);

    for(i = 0; i < 26; i++)
    {
        printf("----------------------------------\n");
        btree_delete(&T, key[i]);
        btree_print(&T, T.root, 0);
    }
}