首页 > 数据结构 > 树形结构 > B树(二)插入操作的实现
2014
07-31

B树(二)插入操作的实现

在前面的文章 B树(一)概述和C++实现 讨论了B树的概念和基本的查找实现。在这篇文章中,将讨论比较复杂的insert()操作。

插入操作的实现

一个新的key总是插入在叶节点。假设插入的关键字为key,和二分查找树类似,我们从根开始遍历,直到到达一个叶子节点。不同之处在于,我们要保证关键字的个数不能超过定义的个数(由t决定)。所以之前插入一个关键节点,我们确保节点有额外的空间。如果空间不够的话,就要进行分裂,这里使用splitChild()函数完成分裂操作。根据B树的规则,每个节点的关键字个数在[t-1, 2t-1]之间,故当target要加入到某个叶子时,如果该叶子节点已经有2t-1个关键字,则再加入target就违反了B树的定义,这时就需要对该叶子节点进行分裂,将叶子以中间节点为界,分成两个包含t-1个关键字的子节点,同时把中间节点提升到该叶子的父节点中,如果这样使得父节点的关键字个数超过2t-1,则要继续向上分裂,直到根节点,根节点的分裂会使得树加高一层。上面的过程需要回溯,那么能否从根下降到叶节点后不回溯就能完成节点的插入呢?答案是肯定的,核心思想就是未雨绸缪,在下降的过程中,一旦遇到已满的节点(关键字个数为2t-1),就就对该节点进行分裂,这样就保证在叶子节点需要分裂时,其父节点一定是非满的,从而不需要再向上回溯。

通过下面的例子来理解插入操作:

假设我们定义的B树最小度数位t=3,即关键字个数在 [2, 5] 之间。我们再一颗空的B树中插入下面的序列: 10, 20, 30, 40, 50, 60, 70, 80 ,90

1) 当插入 10, 20, 30, 40, 50 后,次数还是一个节点,但是关键字个数已经达到上限:

BTree2Ins

 

2) 现在插入60, 插入之前发现关键字已经满了,需要先进行分裂操作。分别完成后在进行插入:

BTreeIns3

 

3) 在继续插入 70 和 80

BTreeIns4

 

4)最后插入90,还要进行一次分裂操作

BTreeIns6

 

点击这里查看更多的例子。

下面是C++的实现:

#include<iostream>
using namespace std;

// 一个 BTree 节点
class BTreeNode
{
    int *keys;  // 关键字 的数组
    int t;      //最小的度
    BTreeNode **C; // 孩子节点指针数组
    int n;     // 当前节点关键字的数量
    bool leaf; // 是否是叶子节点
public:
    BTreeNode(int _t, bool _leaf);   // 构造函数

    // 遍历B树
    void traverse();

    //在B树中查找 k
    BTreeNode *search(int k);

friend class BTree;
};

// B树类
class BTree
{
    BTreeNode *root; // 指向根节点
    int t;  // 最小的度
public:
    // 构造函数
    BTree(int _t)
    {  root = NULL;  t = _t; }

    // 遍历树
    void traverse()
    {  if (root != NULL) root->traverse(); }

    // 查找
    BTreeNode* search(int k)
    {  return (root == NULL)? NULL : root->search(k); }
};

// 构造函数
BTreeNode::BTreeNode(int _t, bool _leaf)
{
    t = _t;
    leaf = _leaf;

    // 分配内存
    keys = new int[2*t-1];
    C = new BTreeNode *[2*t];

    // 初始关键字个数为0
    n = 0;
}

// 遍历当前节点和当前节点下的子树
void BTreeNode::traverse()
{
    // n个关键字,和n+1个孩子
    int i;
    for (i = 0; i < n; i++)
    {
        if (leaf == false)
            C[i]->traverse();
        cout << " " << keys[i];
    }

    //遍历最后一个孩子
    if (leaf == false)
        C[i]->traverse();
}

// 在当前节点下查找 k
BTreeNode *BTreeNode::search(int k)
{
    // 找到第一个大于或等于k的关键字
    int i = 0;
    while (i < n && k > keys[i])
        i++;

    //如果相等,就找到了
    if (keys[i] == k)
        return this;

    //如果是叶节点,未找到
    if (leaf == true)
        return NULL;

    // 否则可能在子树中
    return C[i]->search(k);
}

// 插入关键字k
void BTree::insert(int k){
    if (root == NULL){
        // 分配内存
        root = new BTreeNode(t, true);
        root->keys[0] = k;  
        root->n = 1;  // 更新关键字个数
    }
    else{
    	if (root->n == 2*t-1){ //如果关键字 已满
    		//为新的根节点 分配内存
            BTreeNode *s = new BTreeNode(t, false);
            s->C[0] = root;
            // 分裂操作
            s->splitChild(0, root);
            int i = 0;
            if (s->keys[0] < k)
                i++;
            s->C[i]->insertNonFull(k);
            // 更改根节点
            root = s;
        }
        else  // 不满
            root->insertNonFull(k);
    }
}

void BTreeNode::insertNonFull(int k){
    // 初始化为最右
    int i = n-1;
    if (leaf == true){
        //找到合适的位置插入,类似插入排序
        while (i >= 0 && keys[i] > k)
        {
            keys[i+1] = keys[i];
            i--;
        }
        keys[i+1] = k;
        n = n+1;
    }
    else // 不是根节点
    {
        // 在子节点插入
        while (i >= 0 && keys[i] > k)
            i--;
        if (C[i+1]->n == 2*t-1)
        {
            splitChild(i+1, C[i+1]);
            // 分裂后,C[i]的中间节点被提升,C[i]分成两部分
            //需要知道那一部分包含新的key
            if (keys[i+1] < k)
                i++;
        }
        C[i+1]->insertNonFull(k);
    }
}

void BTreeNode::splitChild(int i, BTreeNode *y){
    BTreeNode *z = new BTreeNode(y->t, y->leaf);
    z->n = t - 1;
    // 复制
    for (int j = 0; j < t-1; j++)
        z->keys[j] = y->keys[j+t];

    if (y->leaf == false)
    {
        for (int j = 0; j < t; j++)
            z->C[j] = y->C[j+t];
    }
    y->n = t - 1;
    for (int j = n; j >= i+1; j--)
        C[j+1] = C[j];
    C[i+1] = z;

    for (int j = n-1; j >= i; j--)
        keys[j+1] = keys[j];

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

// 测试
int main()
{
    BTree t(3); // 最小度为3的B树
    t.insert(10);
    t.insert(20);
    t.insert(5);
    t.insert(6);
    t.insert(12);
    t.insert(30);
    t.insert(7);
    t.insert(17);
    cout << "Traversal of the constucted tree is ";
    t.traverse();

    int k = 6;
    (t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";

    k = 15;
    (t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";

    return 0;
}

输出:

Traversal of the constucted tree is  5 6 7 10 12 17 20 30
Present
Not Present

参考:http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture17.htmlhttp://www.geeksforgeeks.org/b-tree-set-1-insert-2/

 


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮