• 磁盘存储链式的B树与B+树

    磁盘存储链式的B树与B+树

    前言

      本文介绍b树与b+树。并对b树的插入与删除做详细介绍，文末附代码。

      本专栏知识点是通过零声教育的线上课学习，进行梳理总结写下文章，对c/c++linux课程感兴趣的读者，可以点击链接 C/C++后台高级服务器课程介绍 详细查看课程的服务。

    磁盘结构分析与数据存储原理

      我们知道常见的数据结构有链表，树，图等等，而树又可以分为二叉树，多叉树等等。对于链表来说，它可以找下一个结点在哪，而树不但可以找下一个数据结点在哪，树可以找两个，找三个，找多个(几叉)，一个结点有几叉就可以找几个结点，通过一个结点可以找n个结点，这就是一个树形结构。

      那么为什么要有多叉树呢？在学术上，通常解释为：树是为了降层高。那为什么要降层高呢？

      对于多叉树来说，一个结点内，可能有多个key，所以多叉树是不能提高查询效率的（与二叉树相比）。但是它有一个好处，“一个结点内，可能有多个key”，这也就意味着多叉树的结点数量比较少，既然结点数量少，那么查找结点的次数就少。

      注意，多叉树的作用：降低层高，使得结点数量变少，那么查找结点的次数就变少了。

      我们知道cpu能直接存取内存，而不能直接存取磁盘。计算机给磁盘发送一个存取指令，磁盘通过旋转找到对应的盘面磁道扇区再读出来放入内存。磁盘为什么慢，就是因为磁盘寻址速度慢。每寻址一次，磁盘就要转一次。内存一次存取大约是10ns，磁盘一次存取是100ms。对于在内存中来说，多叉树的作用不大，但是对于磁盘来说，如果一个结点存了10个key，就可以少寻址很多次。所以多叉树的作用就是使得层高降低为了减少寻址次数。这也就是为什么磁盘的存储适合用b树或b+树的原因。

    多叉树 -> 降低层高 -> 减少结点数量 -> 减少磁盘IO -> 提升性能

    B树的定义

    一颗M阶B树T，满足以下条件

    1. 每个结点至多拥有M课子树
    2. 根结点至少拥有两颗子树
    3. 除了根结点以外，其余每个分支结点至少拥有M/2课子树
    4. 所有的叶结点都在同一层上
    5. 有k棵子树的分支结点则存在k-1个关键字，关键字按照递增顺序进行排序
    6. 关键字数量满足 ceil( M/2 ) - 1 <= n <= M-1

    B树与B+树的区别

      在实际磁盘存储中往往选用的都是b+树
      

    b+树相较于b树的优点：

    1. 关键字不保存数据，只用来索引，所有数据都保存在叶子结点（b树是每个关键字都保存数据）
    2. b+树的叶子结点是带有指针的，且叶结点本身按关键字从小到大顺序连接（适用于范围查询）
    3. b+树的中间结点不保存数据，所以磁盘页能容纳更多结点元素，更“矮胖”

    B树插入的两种分裂

      b树在插入的过程中，都会自上而下的检查当前节点是否可以分裂，如果关键字满了(k=M-1)则先分裂，再插入。并且插入都会插入到叶子结点中。b树插入会有两种分裂，一种是根结点分裂，一种是非根结点分裂。

    非根结点分裂

    非根结点分裂过程：
      1. 创建一个新结点，设为Z，原来的结点设为Y
      2. 将Y的后半部分的关键字和子树赋给Z
      3. 将Y中间那个关键字key给父结点
      4. 父节点x增加一个关键字key和子树Z

    在这里插入图片描述

    在这里插入图片描述

    根结点分裂

    根结点分裂过程：
      1. 创建一个新结点，设为node
      2. 将b树的root指向node
      3. node的第一个子树指向之前的根结点
      4. 现在，根结点分裂就转化为了非根结点分裂
      5. 执行非根结点分裂过程

    在这里插入图片描述

    插入分裂代码

    //分裂
void btree_split_clild(struct btree *T, struct btree_node *x, int i) {
    //y 需要分裂的结点
    struct btree_node *y = x->children[i];
    //新节点
    struct btree_node *z = btree_create_node(T->t, y->leaf);
    int j = 0;
    z->num = T->t - 1;
    //把y后半部分的key和子树copy到z里
    for (j = 0; j < T->t - 1; j++) {
        z->keys[j] = y->keys[j + T->t];
    }
    if (y->leaf == 0) {
        for (j = 0; j < T->t; j++) {
            z->children[j] = y->children[j + T->t];
        }
    }
    //y结点修改数量
    y->num = T->t - 1;
    //将父节点x增加一个key和子树z
    for (j = x->num; j >= i + 1; j--) {
        x->children[j + 1] = x->children[j];
    }
    x->children[i + 1] = z;
    for (j = x->num - 1; j >= i; j--) {
        x->keys[j + 1] = x->keys[j];
    }
    x->keys[i] = y->keys[T->t - 1];
    x->num++;
}

void btree_insert_nonfull(struct btree *T, struct btree_node *x, KEY_TYPE key) {
    int i = x->num - 1;
    if (x->leaf) {
        while (i >= 0 && x->keys[i] > key) {
            x->keys[i + 1] = x->keys[i];
            i--;
        }
        x->keys[i + 1] = key;
        x->num++;
    }
    else {
        while (i >= 0 && x->keys[i] > key)i--;
        if (x->children[i + 1]->num == 2 * T->t - 1) {
            btree_split_clild(T, x, i + 1);
            if (key > x->keys[i + 1])i++;
        }
        btree_insert_nonfull(T, x->children[i + 1], key);
    }
}

void btree_insert(struct btree *T, KEY_TYPE key) {
    struct btree_node *root = T->root;
    //如果根结点满了，根节点分裂再插入
    if (root->num == 2 * T->t - 1) {
        btree_node *node = btree_create_node(T->t, 0);
        T->root = node;
        node->children[0] = root;
        btree_split_clild(T, node, 0);
        int i = 0;
        if (key > node->keys[0]) i++;
        btree_insert_nonfull(T, node->children[i], key);
    }
    else {
        btree_insert_nonfull(T, root, key);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67

    B树删除的前后借位与节点合并

    为什么删除关键字要借位或者合并呢？因为我们需要满足b树的定义

    判断子树关键字的数量

    1. 相邻两棵子树都是M/2-1 ，则合并
    2. 左子树大于M/2-1，向左借位
    3. 右子树大于M/2-1，向右借位

    关键字在叶子结点中，直接删除

    关键字在叶子结点中

    • 直接删除

    在这里插入图片描述

    当前结点为内结点，且左孩子至少包含M/2个关键字，则向前借位再删除

    当前结点为内结点，且左孩子至少包含M/2个关键字

    • 先借位
    • 在删除

    在这里插入图片描述

    当前结点为内结点，且右孩子至少包含M/2个关键字，则向后借位再删除

    当前结点为内结点，且右孩子至少包含M/2个关键字

    • 先借位
    • 在删除

    在这里插入图片描述

    左右孩子都是M/2-1个关键字，则合并再删除

    左右孩子都是M/2-1个关键

    • 先合并
    • 再删除

    在这里插入图片描述

    删除合并代码

    //{child[idx], key[idx], child[idx+1]}
void btree_merge(btree *T, btree_node *node, int idx) {
    //左右子树
    btree_node *left = node->children[idx];
    btree_node *right = node->children[idx + 1];

    int i = 0;

    //data merge
    left->keys[T->t - 1] = node->keys[idx];
    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->children[T->t + i] = right->children[i];
        }
    }
    left->num += T->t;

    //destroy right
    btree_destroy_node(right);

    //node
    for (i = idx + 1; i < node->num; i++) {
        node->keys[i - 1] = node->keys[i];
        node->children[i] = node->children[i + 1];
    }
    node->children[i + 1] = NULL;
    node->num -= 1;

    if (node->num == 0) {
        T->root = left;
        btree_destroy_node(node);
    }
}

void btree_delete_key(btree *T, btree_node *node, KEY_TYPE key) {
    //如果删除的是null直接返回
    if (node == NULL) return;
    int idx = 0, i;
    //找到key的位置
    while (idx < node->num && key > node->keys[idx]) {
        idx++;
    }
    //如果key是内节点
    if (idx < node->num && key == node->keys[idx]) {
        //如果内节点是叶子节点，直接删
        if (node->leaf) {
            for (i = idx; i < node->num - 1; i++) {
                node->keys[i] = node->keys[i + 1];
            }
            node->keys[node->num - 1] = 0;
            node->num--;
            if (node->num == 0) { //如果整个树都被删了
                free(node);
                T->root = NULL;
            }
            return;
        }
            //前面的结点借位
        else if (node->children[idx]->num >= T->t) {
            btree_node *left = node->children[idx];
            node->keys[idx] = left->keys[left->num - 1];
            btree_delete_key(T, left, left->keys[left->num - 1]);
        }
            //后面的结点借位
        else if (node->children[idx + 1]->num >= T->t) {
            btree_node *right = node->children[idx + 1];
            node->keys[idx] = right->keys[0];
            btree_delete_key(T, right, right->keys[0]);
        }
        else {//合并
            btree_merge(T, node, idx);//合并了一个子树上
            btree_delete_key(T, node->children[idx], key);
        }
    }
    else {
        //key不在这层，进入下层
        btree_node *child = node->children[idx];
        if (child == NULL) {
            printf("Cannot del key = %d\n", key);
            return;
        }
        //说明需要借位
        if (child->num == T->t - 1) {
            //left child right三个节点
            btree_node *left = NULL;
            btree_node *right = NULL;
            if (idx - 1 >= 0)
                left = node->children[idx - 1];
            if (idx + 1 <= node->num)
                right = node->children[idx + 1];
            //说明有一个可以借位
            if ((left && left->num >= T->t) || (right && right->num >= T->t)) {
                int richR = 0;
                if (right) {
                    richR = 1;
                }
                //如果右子树比左子树的key多，则richR=1
                if (left && right) {
                    richR = (right->num > left->num) ? 1 : 0;
                }
                //从下一个借
                if (right && right->num >= T->t && richR) {
                    child->keys[child->num] = node->keys[idx];//将父节点的key拿来，拿子树，右节点的第一个子树
                    child->children[child->num + 1] = right->children[0];
                    child->num++;
                    //父节点借右节点的第一个key
                    node->keys[idx] = right->keys[0];
                    //右节点被借位，删除一些东西
                    for (i = 0; i < right->num - 1; i++) {
                        right->keys[i] = right->keys[i + 1];
                        right->children[i] = right->children[i + 1];
                    }
                    right->keys[right->num - 1] = 0;
                    right->children[right->num - 1] = right->children[right->num];
                    right->children[right->num] = NULL;
                    right->num--;
                }
                    //从上一个借
                else {
                    for (i = child->num; i > 0; i--) {
                        child->keys[i] = child->keys[i - 1];
                        child->children[i + 1] = child->children[i];
                    }
                    child->children[1] = child->children[0];
                    //将左子树的最后一个子树拿来
                    child->children[0] = left->children[left->num];
                    //拿父节点的key
                    child->keys[0] = node->keys[idx - 1];
                    child->num++;
                    //父节点那左子树的key
                    node->keys[idx - 1] = left->keys[left->num - 1];
                    left->keys[left->num - 1] = 0;
                    left->children[left->num] = NULL;
                    left->num--;
                }
            }
                //合并
            else if ((!left || (left->num == T->t - 1)) && (!right || (right->num == T->t - 1))) {
                //把node和left合并
                if (left && left->num == T->t - 1) {
                    btree_merge(T, node, idx - 1);
                    child = left;
                }
                    //把node和right合并
                else if (right && right->num == T->t - 1) {
                    btree_merge(T, node, idx);
                }
            }
        }
        //递归下一层
        btree_delete_key(T, child, key);
    }
}


int btree_delete(btree *T, KEY_TYPE key) {
    if (!T->root) return -1;
    btree_delete_key(T, T->root, key);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163

    B树插入，删除，遍历，查找代码

    #include <stdio.h>
#include <stdlib.h>

//b tree


#define M 3//最好是偶数，易于分裂。阶
typedef int KEY_TYPE;

//btree节点
struct btree_node {
    struct btree_node **children;//子树
    KEY_TYPE *keys;//关键字
    int num;//关键字数量
    int leaf;//是否是叶子结点 1yes,0no
};
//btree
struct btree {
    struct btree_node *root;
    int t;
};

//创建一个结点
struct btree_node *btree_create_node(int t, int leaf) {
    struct btree_node *node = (struct btree_node *) calloc(1, sizeof(struct btree_node));
    if (node == NULL)return NULL;

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

    return node;
}

//销毁一个结点
struct btree_node *btree_destroy_node(struct btree_node *node) {
    if (node) {
        if (node->keys) {
            free(node->keys);
        }
        if (node->children) {
            free(node->children);
        }
        free(node);
    }
}

//创建一个btree
void btree_create(btree *T, int t) {
    T->t = t;
    struct btree_node *x = btree_create_node(t, 1);
    T->root = x;
}

//分裂
void btree_split_clild(struct btree *T, struct btree_node *x, int i) {
    //y 需要分裂的结点
    struct btree_node *y = x->children[i];
    //新节点
    struct btree_node *z = btree_create_node(T->t, y->leaf);
    int j = 0;
    z->num = T->t - 1;
    //把y后半部分的key和子树copy到z里
    for (j = 0; j < T->t - 1; j++) {
        z->keys[j] = y->keys[j + T->t];
    }
    if (y->leaf == 0) {
        for (j = 0; j < T->t; j++) {
            z->children[j] = y->children[j + T->t];
        }
    }
    //y结点修改数量
    y->num = T->t - 1;
    //将父节点x增加一个key和子树z
    for (j = x->num; j >= i + 1; j--) {
        x->children[j + 1] = x->children[j];
    }
    x->children[i + 1] = z;
    for (j = x->num - 1; j >= i; j--) {
        x->keys[j + 1] = x->keys[j];
    }
    x->keys[i] = y->keys[T->t - 1];
    x->num++;
}

void btree_insert_nonfull(struct btree *T, struct btree_node *x, KEY_TYPE key) {
    int i = x->num - 1;
    if (x->leaf) {
        while (i >= 0 && x->keys[i] > key) {
            x->keys[i + 1] = x->keys[i];
            i--;
        }
        x->keys[i + 1] = key;
        x->num++;
    }
    else {
        while (i >= 0 && x->keys[i] > key)i--;
        if (x->children[i + 1]->num == 2 * T->t - 1) {
            btree_split_clild(T, x, i + 1);
            if (key > x->keys[i + 1])i++;
        }
        btree_insert_nonfull(T, x->children[i + 1], key);
    }
}

void btree_insert(struct btree *T, KEY_TYPE key) {
    struct btree_node *root = T->root;
    //如果根结点满了，根节点分裂
    if (root->num == 2 * T->t - 1) {
        btree_node *node = btree_create_node(T->t, 0);
        T->root = node;
        node->children[0] = root;
        btree_split_clild(T, node, 0);
        int i = 0;
        if (key > node->keys[0]) i++;
        btree_insert_nonfull(T, node->children[i], key);

    }
    else {
        btree_insert_nonfull(T, root, key);
    }
}

//{child[idx], key[idx], child[idx+1]}
void btree_merge(btree *T, btree_node *node, int idx) {
    //左右子树
    btree_node *left = node->children[idx];
    btree_node *right = node->children[idx + 1];

    int i = 0;

    //data merge
    left->keys[T->t - 1] = node->keys[idx];
    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->children[T->t + i] = right->children[i];
        }
    }
    left->num += T->t;

    //destroy right
    btree_destroy_node(right);

    //node
    for (i = idx + 1; i < node->num; i++) {
        node->keys[i - 1] = node->keys[i];
        node->children[i] = node->children[i + 1];
    }
    node->children[i + 1] = NULL;
    node->num -= 1;

    if (node->num == 0) {
        T->root = left;
        btree_destroy_node(node);
    }
}

void btree_delete_key(btree *T, btree_node *node, KEY_TYPE key) {
    //如果删除的是null直接返回
    if (node == NULL) return;
    int idx = 0, i;
    //找到key的位置
    while (idx < node->num && key > node->keys[idx]) {
        idx++;
    }
    //如果key是内节点
    if (idx < node->num && key == node->keys[idx]) {
        //如果内节点是叶子节点，直接删
        if (node->leaf) {
            for (i = idx; i < node->num - 1; i++) {
                node->keys[i] = node->keys[i + 1];
            }
            node->keys[node->num - 1] = 0;
            node->num--;
            if (node->num == 0) { //如果整个树都被删了
                free(node);
                T->root = NULL;
            }
            return;
        }
            //前面的结点借位
        else if (node->children[idx]->num >= T->t) {
            btree_node *left = node->children[idx];
            node->keys[idx] = left->keys[left->num - 1];
            btree_delete_key(T, left, left->keys[left->num - 1]);
        }
            //后面的结点借位
        else if (node->children[idx + 1]->num >= T->t) {
            btree_node *right = node->children[idx + 1];
            node->keys[idx] = right->keys[0];
            btree_delete_key(T, right, right->keys[0]);
        }
        else {//合并
            btree_merge(T, node, idx);//合并了一个子树上
            btree_delete_key(T, node->children[idx], key);
        }
    }
    else {
        //key不在这层，进入下层
        btree_node *child = node->children[idx];
        if (child == NULL) {
            printf("Cannot del key = %d\n", key);
            return;
        }
        //说明需要借位
        if (child->num == T->t - 1) {
            //left child right三个节点
            btree_node *left = NULL;
            btree_node *right = NULL;
            if (idx - 1 >= 0)
                left = node->children[idx - 1];
            if (idx + 1 <= node->num)
                right = node->children[idx + 1];
            //说明有一个可以借位
            if ((left && left->num >= T->t) || (right && right->num >= T->t)) {
                int richR = 0;
                if (right) {
                    richR = 1;
                }
                //如果右子树比左子树的key多，则richR=1
                if (left && right) {
                    richR = (right->num > left->num) ? 1 : 0;
                }
                //从下一个借
                if (right && right->num >= T->t && richR) {
                    child->keys[child->num] = node->keys[idx];//将父节点的key拿来，拿子树，右节点的第一个子树
                    child->children[child->num + 1] = right->children[0];
                    child->num++;
                    //父节点借右节点的第一个key
                    node->keys[idx] = right->keys[0];
                    //右节点被借位，删除一些东西
                    for (i = 0; i < right->num - 1; i++) {
                        right->keys[i] = right->keys[i + 1];
                        right->children[i] = right->children[i + 1];
                    }
                    right->keys[right->num - 1] = 0;
                    right->children[right->num - 1] = right->children[right->num];
                    right->children[right->num] = NULL;
                    right->num--;
                }
                    //从上一个借
                else {
                    for (i = child->num; i > 0; i--) {
                        child->keys[i] = child->keys[i - 1];
                        child->children[i + 1] = child->children[i];
                    }
                    child->children[1] = child->children[0];
                    //将左子树的最后一个子树拿来
                    child->children[0] = left->children[left->num];
                    //拿父节点的key
                    child->keys[0] = node->keys[idx - 1];
                    child->num++;
                    //父节点那左子树的key
                    node->keys[idx - 1] = left->keys[left->num - 1];
                    left->keys[left->num - 1] = 0;
                    left->children[left->num] = NULL;
                    left->num--;
                }
            }
                //合并
            else if ((!left || (left->num == T->t - 1)) && (!right || (right->num == T->t - 1))) {
                //把node和left合并
                if (left && left->num == T->t - 1) {
                    btree_merge(T, node, idx - 1);
                    child = left;
                }
                    //把node和right合并
                else if (right && right->num == T->t - 1) {
                    btree_merge(T, node, idx);
                }
            }
        }
        //递归下一层
        btree_delete_key(T, child, 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) {
    int i = 0;

    for (i = 0; i < x->num; i++) {
        if (x->leaf == 0)
            btree_traverse(x->children[i]);
        printf("%C ", x->keys[i]);
    }

    if (x->leaf == 0) btree_traverse(x->children[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", layer, p->num, p->leaf);
        for (i = 0; i < node->num; i++)
            printf("%c ", p->keys[i]);
        printf("\n");
#if 0
        printf("%p\n", p);
        for(i = 0; i <= 2 * T->t; i++)
            printf("%p ", p->childrens[i]);
        printf("\n");
#endif
        layer++;
        for (i = 0; i <= p->num; i++)
            if (p->children[i])
                btree_print(T, p->children[i], layer);
    }
    else printf("the tree is empty\n");
}


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[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (i = 0; i < 26; i++) {
        //key[i] = rand() % 1000;
        printf("%c ", key[i]);
        btree_insert(&T, key[i]);
    }
    btree_print(&T, T.root, 0);
    for (i = 0; i < 26; i++) {
        printf("\n---------------------------------\n");
        btree_delete(&T, key[25 - i]);
        //btree_traverse(T.root);
        btree_print(&T, T.root, 0);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
  • 相关阅读:
    ES7升级、jar包升级、工具类封装，代码改造
    《致新来的你》
    【GD32】05 - PWM 脉冲宽度调制
    excel中vlookup用法
    Vue2.0简讲！
    【20字符串代码题】下标法，辅助数组法
    杨辉三角c语言程序
    嵌入式程序开发1
    数据库第四章习题-数据库安全性控制
    导轨中间继电器JDZY-1202/DC110V
  • 原文地址：https://blog.csdn.net/qq_42956653/article/details/125569179