C语言实现高级数据结构之B树_本关任务:学习b-树的相关知识,用c语言实现b-树的相关操作

B树

概述

B树堪称二叉树放开了生育限制，其任何一个节点，都可以拥有两个以上的孩子。但孩子也不能无限地多下去，否则就成了链表，所以对于任何一个节点而言，其子节点的个数存在一个上界和下界。存在上界便意味着我们可以通过数组来很方便地表示其子节点。

另一方面，由于子节点变多，所以不能再像二叉树一样通过比较左右节点的大小来规范节点的值。所以，每个节点需要有一些键值将其子节点分开。

例如，父节点$P$有$n$个子节点$C_1,C_2,\dots ,C_n$，相应地需要有$n-1$个键值$k_1,k_2,\dots ,k_{n-1}$，使得$C_1⩽k_1⩽C_2⩽k_2\dots ⩽k_{n-1}<C_n$。

除此之外，B树要求每一个末代节点具有相同的深度，所以，如果希望通过数组实现，则需要对末代节点进行标记。再树中，一般把末代节点即没有子节点的节点成为叶节点，所以这个属性写为isLeaf，其C语言实现为

#define M 2

//数组形式的B树节点
typedef struct BTNODE{
    struct BTNODE* father;
    int nKeys;
    int key[2*M-1];             //键值
    struct BTNODE* child[2*M];  //子节点
    int isLeaf;                 //判定是否为末代节点
}btNode;
1
2
3
4
5
6
7
8
9
10

其中，M*2即为B树子节点的上限，在上面的代码中，将M设为2，此时父节点最多有三个键值，四个子节点，此时为B树的一个特例，被称为2-3-4树，如下图所示。

上图父节点的四个子节点中，左数第一个节点小于key[0]，第二个处于key[0]和key[1]之间，依次类推。

由于父节点的子节点数目可变，所以这个B树的子节点或许可以借鉴有序链表的一些思路，通过另一种形式实现。

//链表形式的B树节点
typedef struct BNODE{
    struct BNODE* father;
    struct BNODE* next;     //兄弟节点
    struct BNODE* child;    //子节点
    int nChilds;            //即其子节点及其兄弟节点个数
}bNode;
1
2
3
4
5
6
7

链表思路下，如果child为NULL则说明此节点为末代节点。然而，B树之所以被提出是用于解决机械硬盘的存储问题，链表作为一种指针索引的方式，其数据存储位置并不连续，用在机械硬盘中效率应该是十分低下的。

所以，接下来对B树的实现将以数组形式为主。由于每一个节点都包含许多键值，所以对于搜索操作而言，不仅需要返回当前节点，而且需要返回当前节点键值所对应的位置。

因此，需要定义一个包含节点指针和键值位置的数据结构

typedef struct BKEYNODE{
    btNode* node;           //节点指针
    int key;                //键值的序号
}bKeyNode;
//B树查询操作
bKeyNode searchBtNode(btNode* root, int val){
    bKeyNode bKey = {NULL,0};
    int i;
    while (root->isLeaf == 0){
        i = 0;
        while (i<root->nKeys && root->key[i]<val)
            i++;
        if(val==root->key[i]){
            bKey.node = root;
            bKey.key = i;
        }else
            root = root->child[i];
    }
    bKey.node = root;
    i = 0;
    while(i<root->nKeys && root->key[i]<val)
        i++;
    if(val==root->key[i]){
        bKey.node = root;
        bKey.key = i;
    }
    return bKey;
}
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

初始化

B树最麻烦的性质便是等深性，由于末代节点的深度相同，所以新插入的节点不能像二叉树那样挂在已有的末代节点下面，而是需要嵌入到某个父节点的一群子节点当中。

假设当前的B树共有$n$代，那么我们新插入的节点最多也只能在第$n$代。设其父节点为第$n-1$代的$P$，如果$P$的子节点个数已经达到了上限，那么新插入的节点就装不下了，所以需要某种操作，将$P$裂开。此时$n-1$代将多出一个节点，如果因此而导致$P$所在的$n-1$代子节点个数超出上限，那么就需要把$P$的父节点裂开，依次上推，一直裂到不超上限为止。

如果最后连根节点都不得不裂开，那么树高加一。故其分裂算法为

#define M 2

//当pNode保留[0,M)个节点，将[M,2M]节点分给qNode
//root为根节点，pNode为将要分裂的节点
btNode* splitBtNode(btNode* root,btNode* pNode){
    btNode* qNode = (btNode*)malloc(sizeof(btNode));
    btNode* gNode;     //p,q节点的父节点
    int i;
    //pNode将区间(M,2M)分给qNode
    for (i = M; i < M*2-1; i++){
        qNode->key[i-M]=pNode->key[i+1];
        qNode->child[i-M]=pNode->child[i];
    }
    qNode->isLeaf = pNode->isLeaf;

    //如果pNode为根节点，新建一个空的根节点
    if (pNode->father==NULL){
        gNode = (btNode*)malloc(sizeof(btNode));
        gNode->father = NULL;
        gNode->child[0] = pNode;
        pNode->father = gNode;
        gNode->nKeys = 0;
        gNode->isLeaf = 0;
        root = gNode;
    }else
        gNode=pNode->father;

    //将key[M]分给gNode
    for(i=0;i<gNode->nKeys;i++)
        if(gNode->key[i]>pNode->key[M])
            break;      //i为pNode->key[M]的插入点
    for (int j = gNode->nKeys; j > i; j--)
        gNode->key[j]=gNode->key[j-1];  //gNode键值后移
    for (int j = gNode->nKeys; j>i; j--)
        gNode->child[j+1]=gNode->child[j];

    gNode->key[i] = pNode->key[M];
    gNode->child[i+1] = qNode;          //qNode认父
    gNode->nKeys++;                     //gNode键数加1

    qNode->father = gNode;
    qNode->nKeys = pNode->nKeys-M-1;    //(M,nKeys)共有nKeys-M-1个节点
    if(pNode->isLeaf != 1)
        for(i = 0; i <= qNode->nKeys;i++){
            qNode->child[i]=pNode->child[i+M+1];
            qNode->child[i]->father = qNode;
        }
    pNode->nKeys=M;

    //如果gNode的键值达到最大，则需要对gNode进行分裂
    if(gNode->nKeys==M*2)
        root=splitBtNode(root,gNode);
    return root;
}
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

B树的插入与此前的二叉树最大的不同在于，二叉树每次插入一个新值，总结点数就会加1，B树则不然，每次插入一个新值，只不过是增加某一个节点的键数而已。只有当当前节点的键数大于上限，才会通过分裂操作增加节点的数目。其插入操作实现为

//B树插入操作
btNode* insertBtNode(btNode* root, int val){
    int i;
    btNode *oriRoot = root; //保护根
    while(root->isLeaf!=1){
        i=0;
        while(i<root->nKeys && root->key[i]<val)
            i++;            //插入点
        root = root->child[i];  
    }

    for(i = 0; i < root->nKeys; i++)
        if(root->key[i]>val)
            break;      //i为val插入tempRoot的位置
    for (int j = root->nKeys; j > i; j--)
        root->key[j]=root->key[j-1];    //gNode键值后移
    root->key[i] = val;                 //为节点添加一个新的键值
    root->nKeys++;                      //当前节点键数加一
    
    if(root->nKeys==2*M)
        oriRoot = splitBtNode(oriRoot,root);
    printf("%d was inserted\n",val);

    return oriRoot;
}
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

然后，像往常一样，建立主函数生成一棵B树，并且打印出来

//打印B树
void printBtNode(btNode* root, int n){
    printf("the %dth has %d keys:",n,root->nKeys);
    for (int i = 0; i < root->nKeys; i++)
        printf("%d,",root->key[i]);
    printf("\n");
    if (root->isLeaf)
        return;
    for (int i = 0; i < root->nKeys+1; i++){
        printBtNode(root->child[i],n+1);
    }
}
//主函数
int main(){
    btNode *root = (btNode*)malloc(sizeof(btNode));
    root->isLeaf=1;
    root->key[0] = 10;
    root->father=NULL;
    root->nKeys = 1;

    int temp[20] = {12,20,25,35,7,
                    18,9,33,17,15,
                    14,16,29,21,11,
                    23,6,22,28,3};
    for (int i = 0; i < 20; i++)
        root = insertBtNode(root,temp[i]);

    printBtNode(root,0);
    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

得到结果为

PS E:\Code\AlgC> gcc .\bTree.c
PS E:\Code\AlgC> .\a.exe      
...
the 0th has 2 keys:12,20,
the 1th has 2 keys:7,10,
the 2th has 2 keys:3,6,
the 2th has 1 keys:9,
the 2th has 1 keys:11,
the 1th has 1 keys:17,
the 2th has 3 keys:14,15,16,
the 2th has 1 keys:18,
the 1th has 2 keys:25,33,
the 2th has 3 keys:21,22,23,
the 2th has 2 keys:28,29,
the 2th has 1 keys:35,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

其树图为

可见实现了B树的基本特征.

删除节点

根据以往的经验，删除节点往往比插入节点更复杂，B树也不列外。对于B树来说，被删除的节点可分为两类，一类是末代节点，另一类为非末代节点。

对于非末代节点来说，只需像以前一样，通过交换待删除节点键值与子节点键值，从而使得删除指针下移，直到删除指针抵达末代节点，所以最终我们只需考虑末代节点的情况即可。

如果待删除的末代节点有多于一个键值，那么直接删除即可。如果末代节点只有一个键，那么则需要查看其兄弟节点，如果其兄弟节点的键数多于1，则只需将删除指针转向其兄弟节点，然后删除即可。

如果其兄弟节点只有一个键值，那么需要考虑合并这两个节点。

//数组arr中有n个元素，删除数组中第i个元素
void deleteArray(int* arr, int n,int i){
    for (int j = i; j < n; j++)
        arr[j] = arr[j+1];
}

//B树删除操作
//root为根节点，dNode为待删除节点,nKey为待删除键值的序号
btNode* deleteBtNode(btNode* root, btNode* dNode, int nkey){
    //当被删除节点不是叶节点，则删除指针下移
    if(dNode->isLeaf==0){
        int dChild = dNode->nKeys<M ? nkey+1:nkey;//被删除的孩子
        int dKey = dNode->nKeys<M ?
             0 : dNode->child[dChild]->nKeys-1;
        dNode->key[nkey] = dNode->child[dChild]->key[dKey];
        root = deleteBtNode(root, dNode->child[dChild],dKey);
    }else{
        if(dNode->nKeys>1){
            deleteArray(dNode->key,dNode->nKeys,nkey);
            dNode->nKeys--;
        }else{
            btNode* pNode = dNode->father;
            int i=0;
            while (i<pNode->nKeys&&pNode->key[i]<dNode->key[nkey])
                i++;    //i为待删除节点的序号

            if(i<pNode->nKeys/2){    //当i为左边的节点时，考虑i右侧的孩子
                btNode* bNode = pNode->child[i+1];
                //当dNode右侧兄弟有多于一个节点时，则取之首节点
                if(pNode->child[i+1]->nKeys>1){
                    dNode->key[0] = pNode->key[i];
                    pNode->key[i]=bNode->key[0];
                    deleteArray(bNode->key,bNode->nKeys,0);
                    dNode->nKeys--;
                }else{//当dNode左侧的兄弟也只有一个节点时，则采取合并操作
                    for(int j=bNode->nKeys-1; j>0;j--)
                        bNode->key[j]=bNode->key[j-1];
                    bNode->key[0] = pNode->key[i];
                    bNode->nKeys++;
                    deleteArray(pNode->key,pNode->nKeys,i);
                    pNode->nKeys--;
                }
            }else{
                btNode* bNode = pNode->child[i-1];
                if(bNode->nKeys>1){
                    dNode->key[0] = pNode->key[i-1];
                    pNode->key[i-1] = bNode->key[bNode->nKeys-1];
                    bNode->nKeys--;//删除最后一个节点
                }else{//当dNode左侧的兄弟也只有一个节点时，则采取合并操作
                    bNode->key[bNode->nKeys]=pNode->key[i-1];
                    bNode->nKeys++;
                    deleteArray(pNode->key,pNode->nKeys,i-1);
                    pNode->nKeys--;
                }
            }
        }
    }
    return root;
}
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

验证一下

int main(){
    btNode *root = (btNode*)malloc(sizeof(btNode));
    root->isLeaf=1;
    root->key[0] = 10;
    root->father=NULL;
    root->nKeys = 1;

    int temp[20] = {12,20,25,35,7,
                    18,9,33,17,15,
                    14,16,29,21,11,
                    23,6,22,28};
    for (int i = 0; i < 20; i++)
        root = insertBtNode(root,temp[i]);
    
    printBtNode(root,0);
    
    bKeyNode delNode = searchBtNode(root, 18);
    printf("-----");
    printf("the %d key was searched from %d keys\n",delNode.key,delNode.node->nKeys);
    
    root = deleteBtNode(root, delNode.node,delNode.key);
    printBtNode(root,0);

    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

结果为

PS E:\Code\AlgC> gcc .\bTree.c
PS E:\Code\AlgC> .\a.exe      
...//和之前相同
-----the 0 key was searched from 1 keys
the 0th has 2 keys:12,20,
the 1th has 2 keys:7,10,
the 2th has 2 keys:3,6,
the 2th has 1 keys:9,
the 2th has 1 keys:11,
the 1th has 1 keys:16,
the 2th has 2 keys:14,15,
the 2th has 1 keys:17,
the 1th has 2 keys:25,33,
the 2th has 3 keys:21,22,23,
the 2th has 2 keys:28,29,
the 2th has 1 keys:35,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

画图表示为