[C++知识库]b树 c++

插入过程简单，讲解教程也多。

删除思路：非叶节点找替代结点，然后在相应子树中递归删除。叶结点直接删除。

删除完后判断是否要调整。在插入函数中有个find的辅助函数，定位关键值插入的结点和下标，但在删除函数中不能直接定位到删除的目标结点，必须逐层遍历。否则中间的层可能受影响但是略过了导致没有调整，要保证每层都进行判断。

一些特殊情况的处理：

调整函数中判断有没有左右兄弟，是否能借。

根结点删除至无，要指向新结点。怎么判断是不是根结点？只有根结点的关键值数量才会数量减为0，因为非根结点至少为M/2-1或M/2，会通过调整函数自动维护。M/2向上取整，不是整除。

非叶节点删除思路有两种。一种是直接在小于/大于关键值的子树选前驱/后继结点，然后在相应子树中（不可直接跳）递归删除。一种是根据前/后子树关键值的数量选择向哪个子树借，这种会面临一种特殊情况：要删除只有一个关键值的根结点，而左右子树中有M/2-1个关键值。这样两边都不能借，只能合并，然后还要改根结点指针，在新的根结点中删除。

最后就是一些细节，移动操作的for循环有没有等号，keynum要不要减一，数组下标是不是从0开始，等等，结合图走一遍就行。不熟多看几遍就记住了，回想起来才不会迷茫。

#include<queue>
template<class K, int M = 3>
struct BTreeNode {//M阶b树
    K _key[M];//从0开始，M-1用于溢出时暂时存放
    BTreeNode<K, M>* _sub[M + 1];//子树指针，从0开始，M+1暂时存放
    BTreeNode<K, M>* _parent;
    size_t _keynum;//关键字个数

    BTreeNode() :_keynum(0), _parent(nullptr) {
        memset(_sub, 0, sizeof(BTreeNode<K, M>*) * (M + 1));
    }
};
template<class K, int M = 3>//M阶b树
class BTree {
    typedef BTreeNode<K, M> BTNode;
    BTNode* _root;
public:
    BTree() :_root(nullptr) {}
    ~BTree() { destoryTree(_root); _root = nullptr; }
    void levelorder() {
        if (!_root) { cout << "levelorder,null" << endl; return; }
        queue<BTNode*>q;
        q.push(_root);
        int a = 1, b;
        BTNode* node;
        while (!q.empty())
        {
            b = 0;
            for (int j = 0; j < a; j++) {
                node = q.front();
                cout << " ( ";
                for (int i = 0; i < node->_keynum; i++) {
                    cout << node->_key[i] << ",";
                }
                cout << ") ";
                for (int i = 0; i <= node->_keynum; i++) {
                    if (node->_sub[i]) {
                        q.push(node->_sub[i]);
                        b++;
                    }
                }
                q.pop();
            }
            cout << endl;
            a = b;
        }
    }
    pair<BTNode*, int>find(const K& key) {
        BTNode* parent = nullptr, * node = _root;
        while (node) {
            int i = 0;
            while (i<node->_keynum && key>node->_key[i]) {
                i++;//i最大等于_keynum，刚好是最右边的子树
            }
            if (i < node->_keynum && key == node->_key[i]) {
                return make_pair(node, i);//返回关键值所在结点和下标
            }//找到关键值
            parent = node;
            node = node->_sub[i];//到key[i]右边的子树找
        }
        return make_pair(parent, -1);//没找到
    }
    bool insert(K key) {
        if (_root == nullptr) {
            _root = new BTNode;
            _root->_key[0] = key;
            _root->_keynum++;
            return true;
        }//空树

        pair<BTNode*, int> result = find(key);
        if (result.second != -1)return false;//关键值已存在

        K k = key;
        BTNode* node = result.first;
        BTNode* sub = nullptr;//新关键值插入的结点必为叶结点，子树为空
        while (1) {
            _insert(node, k, sub);//先插入再判断
            if (node->_keynum < M)return true;//关键值没满

            //结点分裂，将大于“中间值”[M/2]的关键值及子树分裂到新结点中
            BTNode* temp = new BTNode;
            for (int i = M / 2 + 1, j = 0; i < M; i++, j++) {//移动关键值
                temp->_key[j] = node->_key[i];
                node->_keynum--;
                temp->_keynum++;
            }
            for (int i = M / 2 + 1, j = 0; i <= M; i++, j++) {//移动子树
                if (node->_sub[i]) {
                    temp->_sub[j] = node->_sub[i];//大于关键值的子树移到新结点
                //if (node->_sub[i])node->_sub[i]->_parent = temp;//更新双亲结点
                    //node->_sub[i]->_parent = temp;//更新双亲结点
                    temp->_sub[j]->_parent = temp;//更新双亲结点
                    node->_sub[i] = nullptr;//清空
                }
            }

            k = node->_key[M / 2];//中间上移的关键值，插入到双亲结点，M/2
            node->_keynum--;

            if (node->_parent == nullptr) {//分裂到根结点了，新建根结点
                _root = new BTNode;
                _root->_key[0] = k;
                _root->_keynum = 1;
                _root->_sub[0] = node;
                _root->_sub[1] = temp;//两个子树
                temp->_parent = _root;
                node->_parent = _root;
                return true;
            }

            node = node->_parent;//分裂出来的关键值和新结点插入到父结点中
            sub = temp;
        }
    }
    bool remove(K key) {
        return remove(_root, key);
    }

private:
    void shownode(BTNode* node) {//输出结点的关键值
        if (!node) {
            cout << "shownode, null" << endl;
            return;
        }
        for (int i = 0; i < node->_keynum; i++)cout << node->_key[i] << ",";
        cout << endl;
    }
    bool remove(BTNode* node, K key) {
        if (!node)return false;
        bool result = false;
        pair<bool, int> ret = get_keyindex(node, key);
        int index = ret.second;//关键值是否在此结点中
        if (ret.first) {
            result = true;
            if (is_leaf(node)) {//已经是叶结点，直接删除
                for (int i = index; i < node->_keynum - 1; i++) {
                    node->_key[i] = node->_key[i + 1];
                }
                node->_keynum--;

                if (_root->_keynum == 0) {//只剩根结点也为叶结点，且无关键值
                    cout << "_root->_keynum == 0 " << endl;
                    delete _root;
                    _root = nullptr;

                }
                return true;
            }
            else {//不是叶结点，用子树中最小的关键值代替，和BST类似
                BTNode* pre = node->_sub[index];//小于关键值的子树
                BTNode* next = node->_sub[index + 1];//大于关键值的子树

                if (pre->_keynum >= (M + 1) / 2) {//用前驱代替
                    //cout << "get pre" << endl;
                    for (; pre->_sub[pre->_keynum] != nullptr; pre = pre->_sub[pre->_keynum]);
                    node->_key[index] = pre->_key[pre->_keynum - 1];
                    remove(node->_sub[index], pre->_key[pre->_keynum - 1]);//在子树中递归的删除代替的关键值
                }
                else if (next->_keynum >= (M + 1) / 2) {//后继代替
                    for (; next->_sub[0] != nullptr; next = next->_sub[0]);
                    node->_key[index] = next->_key[0];
                    remove(node->_sub[index + 1], next->_key[0]);//在右子树中递归的删除代替的关键值//不能直接的跳到next删除
                }
                else {
                    merge(node, index);//子树next和pre合并再删除
                    remove(pre, key); 
                    node = pre;//更新结点，方便检查是否需要调整
                }
            }
        }
        else result = remove(node->_sub[index], key);//在相应子树中找
        if (node->_sub[index] && node->_sub[index]->_keynum < (M + 1) / 2 - 1) //删除完了检查子树是否需要调整
        {
            adjust(node, index);//子树index需要调整
        }
        return result;
    }
    void adjust(BTNode* node, int index) {
        BTNode* sub = node->_sub[index];
        BTNode* left = index > 0 ? node->_sub[index - 1] : nullptr;
        BTNode* right = index < node->_keynum ? node->_sub[index + 1] : nullptr;
        //BTNode* right = index < M - 1 && index < node->_keynum ? node->_sub[index + 1] : nullptr;
        if (right && right->_keynum >= (M + 1) / 2) {//有右兄弟且可借
            sub->_key[sub->_keynum++] = node->_key[index];//父结点借给sub
            node->_key[index] = right->_key[0];//right借给父
            right->_keynum--;
            for (int i = 0; i < right->_keynum; i++) {//right借了一个关键值，往左填补空位
                right->_key[i] = right->_key[i + 1];
            }
            if (right->_sub[0]) {//借的关键值的子树也要移动
                sub->_sub[sub->_keynum] = right->_sub[0];
                for (int i = 0; i <= right->_keynum; i++) {
                    right->_sub[i] = right->_sub[i + 1];
                }
            }
        }
        else if (left && left->_keynum >= (M + 1) / 2) {//有左兄弟且可借
            for (int i = sub->_keynum; i > 0; i--) {//sub空出位置
                sub->_key[i] = sub->_key[i - 1];
            }
            sub->_keynum++;
            sub->_key[0] = node->_key[index - 1];//父结点借给sub
            if (left->_sub[left->_keynum]) {//借的关键值的子树也要移动
                for (int i = sub->_keynum; i > 0; i--) {//sub空出位置
                    sub->_sub[i] = sub->_sub[i - 1];
                }
                sub->_sub[0] = left->_sub[left->_keynum];
            }
            node->_key[index - 1] = left->_key[--left->_keynum];//left借给父
        }
        else if (left) {//与左兄弟合并
            merge(node, index - 1);
        }
        else {//与右兄弟合并
            merge(node, index);
        }
    }
    void merge(BTNode* node, int index) {//合并，保留index，删index+1
        if (!node || index < 0)return;
        BTNode* sub1 = node->_sub[index], * sub2 = node->_sub[index + 1];
        sub1->_key[sub1->_keynum++] = node->_key[index];//差一个满足最少
        for (int i = 0; i < sub2->_keynum; i++)//关键值合并//sub2->_keynum//(M + 1) / 2 - 1
            sub1->_key[sub1->_keynum + i] = sub2->_key[i];
        if (sub2->_sub[0]) {//子树合并
            for (int i = 0; i <= sub2->_keynum; i++)
                sub1->_sub[sub1->_keynum + i] = sub2->_sub[i];
        }
        sub1->_keynum += sub2->_keynum;
        node->_keynum--;
        free(sub2);
        if (node->_keynum > 0) {
            for (int i = index; i < node->_keynum; i++) {//父结点借出关键值，调整
                node->_key[i] = node->_key[i + 1];
                node->_sub[i + 1] = node->_sub[i + 2];
            }
            node->_sub[node->_keynum + 1] = nullptr;
        }
        if (node->_keynum == 0) {//根才会减到0？其他结点都会合并不会为0,直到合并到根结点
            cout << "node->_keynum == 0" << endl;//合并导致上层结点关键值没了
            free(_root);
            _root = sub1;//改根结点
        }
    }
    pair<bool, int> get_keyindex(BTNode* node, K key) {//单个结点中搜索关键值
        int i = 0;
        while (i < node->_keynum && key > node->_key[i])i++;
        if (i < node->_keynum && key == node->_key[i]) return make_pair(true, i);//找到关键值
        else return make_pair(false, i);//没找到
    }
    bool is_leaf(BTNode* node) {
        if (node->_sub[0] == nullptr)return true;
        else return false;
    }
    //将关键值和子树插入到双亲结点中
    void _insert(BTNode* node, const K& key, BTNode* sub) {
        int i = node->_keynum - 1;//最后一个关键值的下标
        while (i >= 0 && node->_key[i] > key) {
            node->_key[i + 1] = node->_key[i];
            node->_sub[i + 2] = node->_sub[i + 1];//子树大于关键值
            i--;
        }
        node->_key[i + 1] = key;
        node->_sub[i + 2] = sub;
        if (sub)sub->_parent = node;
        node->_keynum++;
    }
    void destoryTree(BTNode* root) {//连同所有子树一同删除
        if (root) {
            //cout << "destoryTree=" << root << endl;
            for (int i = 0; i <= root->_keynum; i++) {
                destoryTree(root->_sub[i]);
                root->_sub[i] = nullptr;
            }
            //root->_parent = nullptr;
            //root->_keynum = 0;
            delete root;
        }
    }
};

void test02() {


    //sizeof(a) / sizeof(*a)


    int a11[] = { 1,3,7,14,8,5,11,17,13,6,12,20,23,26,4,19 };
    int a[] = { 36,1,43,45,15,35,6,0,46,31,3,9,16,34,21,44,24,10,30,17,5,40,32,4,29,27,12,2,18,19 };
    BTree<int, 5> bt;
    for (auto i : a) {
        bt.insert(i);
        //bt.levelorder();
        //cout << "----------" << endl;
    }
    //bt.levelorder();
    //cout << "----------" << endl;
    for (auto i : a) {
        cout << "delete " << i << endl;
        bt.remove(i);
        //bt.levelorder();
        //cout << "----------" << endl;
    }
    bt.levelorder();



}