• 数据结构_B树(C语言)

    数据结构总目录

    B树

    1. 图文解析

    B树：属于多叉树，存在多个孩子结点，并遵循左小右大的规则，常用于数据库索引

    1.1 存储结构

    B树的阶数：即该树每个结点下的最大孩子结点数
    例如一棵M = 5阶的B树，其结点结构如下：
    在这里插入图片描述
    其中第5个关键字和第6个孩子指针作为临时空间，用于进行插入操作可能导致的分裂

    typedef int KeyType;
typedef struct TNode
{
    int count;              // 关键字个数
    KeyType key[M];         // 关键字
    struct TNode *parent;   // 父结点指针
    struct TNode *child[M + 1]; // 孩子结点指针 
}TNode, *BTree;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    1.2 B树的插入操作

    首先需要在B树中定位插入的关键字所在的【结点p】以及结点内的【插入位置index】
    （1）第一种情况，结点p内空间未满，则直接插入即可
    在这里插入图片描述
    （2）第二种情况，结点p内空间已满
    在这里插入图片描述

    • 此时关键字插入的是结点p内最后一个临时空间，并以中心进行分裂
      在这里插入图片描述分裂：中间的数据插入父结点内，右区域数据（包括对应的孩子指针）全部粘贴到右兄弟中
      在这里插入图片描述

    （3）第三种情况，经过分裂后，父结点会增加一个关键字，也会导致父结点的分裂，此刻只需对父结点进行递归判断是否需要进行分裂即可
    在这里插入图片描述
    在这里插入图片描述

    1.3 B树的删除操作

    同理，首先需要在B树中定位删除的关键字所在的【结点p】以及结点内的【删除位置index】
    （1）如果所删除的为非叶子结点，则可以取右子树中的最小关键字作为代替，而后递归删除右子树中的最小关键字
    在这里插入图片描述
    （2）如果删除的是叶子结点，则直接删除叶子结点内的关键字，而后进行如下判断
    ----》若删除后结点内的关键字个数 >= （M/2），即删除完成
    ----》若删除后结点内的关键字个数 < （M/2），则说明需要进行【借数据】或者【结点合并】操作，需进行以下判断

    1. 如果左兄弟结点或者右兄弟结点有多余的数据可以借
      在这里插入图片描述
      在这里插入图片描述
    2. 如果左兄弟结点和右兄弟结点都没有多余的数据可以借，则与兄弟结点进行合并
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    3. 合并后会导致父结点的关键字少一个，则还需递归判断父结点是否需要进行【借数据】和【结点合并】操作
      在这里插入图片描述
      在这里插入图片描述

    2. 源代码

    此处源代码仅凭个人对理论知识的理解来写的，不保证其是否标准，如有错误或不足之处、欢迎大家在评论区提出

    #include
#include
#include

#define M 5  // B树的阶数
#define NullKey -32768

typedef int KeyType;
typedef struct TNode
{
    int count;              // 关键值个数
    KeyType key[M];         // 关键值
    struct TNode *parent;   // 父结点指针
    struct TNode *child[M + 1]; // 孩子结点指针 
}TNode, *BTree;

// B树初始化
void InitBTree(BTree *BT)
{
    int i;
    // 分配根结点空间
    (*BT) = (TNode *)malloc(sizeof(TNode));
    // 初始化根结点
    for (i = 0; i < M; i++)
    {
        (*BT)->key[i] = NullKey;
        (*BT)->child[i] = NULL;
    }
    (*BT)->count = 0;
    (*BT)->child[i] = NULL;
    (*BT)->parent = NULL;
    printf("已初始化B树!\n");
}

// 创建新结点（返回新生成的结点）
TNode* NewTNode()
{
    TNode *node = (TNode *)malloc(sizeof(TNode));
    int i;
    for (i = 0; i < M; i++)
    {
        node->key[i] = NullKey;
        node->child[i] = NULL;
    }
    node->count = 0;
    node->child[i] = NULL;
    node->parent = NULL;
    return node;
}

// 打印单个结点内的数据
void DispalyNode(TNode *node)
{
    int i;
    if (node)
    {
        for (i = 0; i < M; i++)
        {
            printf("[ ");
            if (node->key[i] != NullKey && i < node->count)
            {
                printf("%d ", node->key[i]);
            }
            else
            {
                printf("  ", node->key[i]);
            }
            printf("]");
        }
        printf("\n");
    }
    else
    {
        printf("NULL\n");
    }
}

// 插入二（插入关键字并判断是否需要分裂）
void TNodeInsert(TNode *node, KeyType key)
{
    int i, j;
    // 查找关键字在当前结点的插入位置
    for (i = 0; i < node->count; i++)
    {
        if (key < node->key[i])
        {
            break;
        }
    }
    // 将关键字插入相应的位置
    for (j = node->count; j > i; j--)
    {
        node->key[j] = node->key[j - 1]; 
        node->child[j] = node->child[j - 1];
    }
    node->key[i] = key;
    node->count++;
    printf("关键值(%d)插入 => ", key);
    DispalyNode(node);
    
    // 判断插入数据后的结点是否需要分裂
    if (node->count == M)
    {
        // 如果插入后的结点数等于阶数，则需要进行分裂
        printf("\n结点已满, 需要进行分裂\n");
        
        // 分裂后的【中间关键字】下标
        int mid = M / 2;
        // 分裂后的中间关键字在父结点内插入的下标
        int index;

        // 1. 分裂后的父结点
        TNode *parent = node->parent;
        if (parent == NULL)
        {
            // 若父结点为空，则初始化一个新结点作为父结点
            parent = NewTNode();
            // 分裂后的中间关键值在新的父结点插入的下标必定为 0
            index = 0;
            // 新的父结点与原结点进行链接
            node->parent = parent;
            parent->child[index] = node;
        }
        else
        {
            // 若父结点不为空，则查找分裂后的中间关键值在父结点内的插入位置
            for (j = 0; j < M; j++)
            {
                if (parent->child[j] == node)
                {
                    index = j;
                    break;
                }
            }
        }
        
        // 2. 分裂后的右兄弟结点
        int k;
        TNode *rightSibling = NewTNode();
        // 将原结点中的右区域数据（包括孩子指针）粘贴到到右兄弟结点内
        for(k = 0, j = mid + 1; j < M; j++, k++)
        {
            rightSibling->key[k] = node->key[j];
            rightSibling->child[k] = node->child[j];
            if (node->child[j])
            {   
                // 更新分裂到右兄弟的孩子结点的父结点 
                node->child[j]->parent = rightSibling;
            }
            rightSibling->count++;
            node->count--;
            // 初始化原结点的右区域数据
            node->key[j] = NullKey;
            node->child[j] = NULL;
        }
        // 粘贴最后一个临时孩子指针到右兄弟结点中
        rightSibling->child[k] = node->child[j];
        if (node->child[j])
        {
            node->child[j]->parent = rightSibling;
        }
        node->child[j] = NULL;

        // 右兄弟结点 与 父结点 进行链接
        rightSibling->parent = parent;
        parent->child[index + 1] = rightSibling;

        // 删除原结点内的中间关键字
        node->count--;
        
        printf("\t分裂后的原结点:");
        DispalyNode(node);
        printf("\t分裂后的右结点:");
        DispalyNode(rightSibling);
        
        // 最后将中间关键值递归插入父结点内（之所以递归是因为父结点也可能会发生分裂）
        TNodeInsert(node->parent, node->key[mid]);
        node->key[mid] = NullKey;
        printf("\n");
    }
}

// 插入一（查找插入的结点）
void BTreeInsert(BTree *BT, KeyType key)
{
    int i;
    TNode *p = (*BT);
    // 查找关键字插入的结点
    while (p)
    {   
        for (i = 0; i < p->count; i++)
        {
            if (key < p->key[i])
            {
                break;
            }
        }
        // key的插入位置在孩子结点中
        if (p->child[i] != NULL)
        {
            p = p->child[i];
        }
        else
        {
            break;
        }
    }
    
    // 在结点内插入key
    TNodeInsert(p, key);

    // 插入可能会发生分裂生成新的父结点，故需要重置根结点
    while (p->parent)
    {
        p = p->parent;
    }
    (*BT) = p;
}

// 删除三（借数据或者合并结点）
TNode* BorrowOrMerge(TNode *node)
{
    int mid = M / 2;
    if (node->parent && node->count < mid)
    {
        // 若父结点存在，且结点内数据小于一半
        // 则说明需要向左右兄弟其中一个结点借数据或者与他们其中一个合并
        printf("当前结点: ");
        DispalyNode(node);
        printf("结点内关键字个数 %d < %d\n", node->count, mid);
        int i, j, k;
        TNode *parent = node->parent;
        TNode *leftSibling = NULL;
        TNode *rightSibling = NULL;
        // 获取左兄弟结点和右兄弟结点
        for (i = 0; i <= parent->count; i++)
        {
            if (parent->child[i] == node)
            {
                if (i > 0)
                {
                    leftSibling = parent->child[i - 1];
                }
                if (i < node->count)
                {
                    rightSibling = parent->child[i + 1];
                }
                break;
            }
        }
        printf("\t左兄弟: ");
        DispalyNode(leftSibling);
        printf("\t右兄弟: ");
        DispalyNode(rightSibling);
        // 借数据、合并判断
        if (leftSibling && leftSibling->count > mid)
        {
            // 左兄弟结点有多余的数据可以借
            printf("可向左兄弟结点借数据\n");
            for (j = node->count; j > 0; j--)
            {
                // 将删除位置前的数据整体后移，空出第一个数据
                node->key[j] = node->key[j - 1];
                // 因为此时删除的一定是叶子结点，所以无需考虑孩子指针
            }
            
            // 原结点内空出的第一个位置添加为父结点内对应的数据
            node->key[0] = parent->key[i - 1];
            node->count++;
            // 而对应的父结点数据替换为左兄弟结点的最后一个数据
            parent->key[i - 1] = leftSibling->key[leftSibling->count - 1];
            
            // 删除左兄弟结点的最后一个数据
            leftSibling->key[leftSibling->count - 1] = NullKey;
            leftSibling->count--;
            // 因为借数据不会导致根结点的变化，故返回空 
            return NULL;
        }
        else if(rightSibling && rightSibling->count > mid)
        {
            // 左兄弟结点有多余的数据可以借
            printf("可向右兄弟结点借数据\n");
            
            // 原结点内最后一个位置添加为父结点内对应的数据
            node->key[node->count] = parent->key[i];
            node->count++;
            // 父结点数据获取右兄弟结点的第一个数据
            parent->key[i] = rightSibling->key[0];

            // 删除右兄弟结点被借去第一个数据，整体前移一个位置
            for (j = 0; j < rightSibling->count - 1; j++)
            {
                rightSibling->key[j] = rightSibling->key[j + 1];
            }
            leftSibling->count--; 
            // 同理
            return NULL;
        }
        else 
        {
            // 若左兄弟和右兄弟都借不来数据，则说明需要进行合并
            if (leftSibling)
            {
                // 可以与左兄弟结点进行合并
                printf("与左兄弟结点合并: ");

                // 左兄弟结点末尾添加其对应的父结点数据
                leftSibling->key[leftSibling->count] = parent->key[i - 1];
                leftSibling->count++;
                
                // 将原结点内的所有数据（包括孩子指针）添加到左兄弟内
                for (j = leftSibling->count, k = 0; k <= node->count; j++, k++)
                {
                    leftSibling->key[j] = node->key[k];
                    leftSibling->child[j] = node->child[k];
                }
                leftSibling->count += node->count;

                // 销毁原结点
                free(node);
                parent->child[i] = NULL;
                
                // 删除左兄弟结点所对应的父结点内数据，整体前移
                parent->key[i - 1] = parent->key[i];
                for (j = i; j < parent->count; j++)
                {
                    parent->key[j] = parent->key[j + 1];
                    parent->child[j] = parent->child[j + 1];
                }
                parent->count--;
                DispalyNode(leftSibling);
                
                // 如果合并后父结点没有数据，则证明该父结点为根结点
                if (parent->count == 0)
                {
                    free(parent);
                    leftSibling->parent = NULL;
                    return leftSibling;
                }
            }
            else
            {
                // 可以与又兄弟结点进行合并
                printf("与右兄弟结点合并: ");
                
                // 原结点末尾添加其对应的父结点数据
                node->key[node->count] = parent->key[i];
                node->count++;
                
                // 将右兄弟内的数据全部添加到原结点内
                for (j = node->count, k = 0; k < rightSibling->count; j++, k++)
                {
                    node->key[j] = rightSibling->key[k];
                    node->child[j] = rightSibling->child[k];
                }
                node->count += rightSibling->count; 
                
                // 销毁右兄弟结点
                free(rightSibling);
                parent->child[i + 1] = NULL;
                
                // 删除原结点所对应的父结点内数据，整体前移
                parent->key[i] = parent->key[i + 1];
                for (j = i + 1; j < parent->count; j++)
                {
                    parent->key[j] = parent->key[j + 1];
                    parent->child[j] = parent->child[j + 1];
                }
                parent->count--;
                DispalyNode(node);

                // 同理如果合并后父结点没有数据，则证明该父结点为根结点
                if (parent->count == 0)
                {
                    free(parent);
                    node->parent = NULL;
                    return node;
                }
            }
            printf("\n");
            // 因为合并后会导致父结点少一个数据，故还需向父结点递归判断是否需要进行借数据或者合并操作
            return BorrowOrMerge(parent);
        }
    }
    return NULL;
}

// 删除二（判断是否为叶子结点）
TNode* TNodeDelete(TNode *node, int index)
{
    
    int i;
    // 判断右子树是否存在
    if (node->child[index + 1] == NULL)
    {
        // 若右子树不存在，则当前结点为叶子结点
        printf("当前删除的为叶子结点: ");
        DispalyNode(node);
        // 先删除该结点内数据
        for (i = index; i < node->count - 1; i++)
        {
            // 因为是叶子结点，只需左移数据即可
            node->key[i] = node->key[i + 1];
        }
        node->key[i] = NullKey;
        node->count--;
        printf("已完成删除: ");
        DispalyNode(node);
        printf("\n");
        // 根据结点内关键字个数，进行借数据或者合并操作
        return BorrowOrMerge(node);
    }
    else    
    {
        // 若右子树存在，则当前结点为非叶子结点
        printf("当前删除的为非叶子结点内数据: ");
        DispalyNode(node);
        
        // 查找右子树中的最小结点，且最小值必定为该结点内的第一个关键字
        TNode *min = node->child[index + 1];
        while (min->child[0])
        {
            min = min->child[0];
        }
        node->key[index] = min->key[0];
        printf("替换为其右子树中的最小关键字: ");
        DispalyNode(node);
        printf("\n\n");
        // 递归删除右子树中的最小结点内的最小关键字
        return TNodeDelete(min, 0);
    }
}

// 删除一（查找删除的结点及其位置）
void BTreeDelete(BTree *BT, KeyType key)
{
    int i, flag = 0;
    TNode *p = (*BT);
    // 查找数据所在的结点
    while (p)
    {   
        for (i = 0; i < p->count; i++)
        {
            if (key < p->key[i])
            {
                break;
            }
            else if (key == p->key[i])
            {
                // 查找成功
                flag = 1;
                printf("\n查找成功! 正在进行删除操作\n");
                break;
            }
        }
        if (flag == 0 && p->child[i] != NULL)
        {
            // 若未找到，则在左子树中查找
            p = p->child[i];
        }
        else
        {
            break;
        }
    }
    
    if (flag == 1)
    {
        // 查找成功，进行删除操作
        p = TNodeDelete(p, i);
        // 删除导致的合并可能会使得父结点发生改变
        if (p)
        {
            (*BT) = p;
        }
    }
    else
    {
        printf("\n删除失败, 未查找到该数据!\n");
    }
}


// 先序遍历B树
void PreOrderTraverse(BTree BT)
{
    int i;
    printf("[ ");
    for (i = 0; i < BT->count; i++)
    {
        if (BT->key[i] != NullKey)
        {
            printf("%d ", BT->key[i]);
        }
    }
    printf("]  ");
    
    for (i = 0; i < BT->count + 1; i++)
    {
        if (BT->child[i] != NULL)
        {
            PreOrderTraverse(BT->child[i]);
        }
    }
}


int main()
{ 
    int i, k;
    BTree BT;
    KeyType key;
    InitBTree(&BT);

    while (1)
    {
        printf("请输入插入个数(小于0退出循环):");
        scanf("%d", &k);
        if (k < 0)
        {
            break;
        }
        else if (k > 0)
        {
            printf("请输入插入的数据:");
            for (i = 0; i < k; i++)
            {
                scanf("%d", &key);
                BTreeInsert(&BT, key);
            }
            printf("\n先序遍历:");
            PreOrderTraverse(BT);
            printf("\n\n");
            
        }
        else
        {
            printf("请输入删除的数据:");
            scanf("%d", &key);
            BTreeDelete(&BT, key);
            
            printf("\n先序遍历:");
            PreOrderTraverse(BT);
            printf("\n\n");
        }
    }
    system("pause");
    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
    • 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
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
    • 435
    • 436
    • 437
    • 438
    • 439
    • 440
    • 441
    • 442
    • 443
    • 444
    • 445
    • 446
    • 447
    • 448
    • 449
    • 450
    • 451
    • 452
    • 453
    • 454
    • 455
    • 456
    • 457
    • 458
    • 459
    • 460
    • 461
    • 462
    • 463
    • 464
    • 465
    • 466
    • 467
    • 468
    • 469
    • 470
    • 471
    • 472
    • 473
    • 474
    • 475
    • 476
    • 477
    • 478
    • 479
    • 480
    • 481
    • 482
    • 483
    • 484
    • 485
    • 486
    • 487
    • 488
    • 489
    • 490
    • 491
    • 492
    • 493
    • 494
    • 495
    • 496
    • 497
    • 498
    • 499
    • 500
    • 501
    • 502
    • 503
    • 504
    • 505
    • 506
    • 507
    • 508
    • 509
    • 510
    • 511
    • 512
    • 513
    • 514
    • 515
    • 516
    • 517
    • 518
    • 519
    • 520
    • 521
    • 522
    • 523
    • 524
    • 525
    • 526
    • 527
    • 528
    • 529
    • 530
    • 531
    • 532
    • 533
    • 534
    • 535
    • 536
    • 537
    • 538
    • 539
    • 540
    • 541
    • 542
    • 543
    • 544
    • 545
    • 546
    • 547
    • 548
    • 549

    3. 测试结果

    3.1 插入

    插入：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

    • 1

    在这里插入图片描述

    3.2 删除

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

  • 相关阅读:
    Parallel通过XCM与Moonbeam集成，将PARA以及DeFi用例带入Moonbeam生态
    若依微服务项目本地启动
    【C++入门】友元函数详解（定义、实现、优缺点）
    小型气象站的分类和选型要点
    什么是“2 Way SSL”以及它是如何工作的？
    KestrelServer详解[2]: 网络连接的创建
    库存管理方法有哪些？有哪些库存管理软件比较好用？
    vue axios请求两种方式，出现401错误，需要添加config配置
    nginx自动化脚本安装
    Linux_基础指令（一）
  • 原文地址：https://blog.csdn.net/qq_44625774/article/details/126337914