B樹的插入演算法

為什么我以關鍵碼從小到大，依次插入B樹，建立B樹（4階B樹），當關鍵碼數量較少時結點能正常分裂，但是數量大了，就幾乎變成2叉樹了，估計是插入演算法的分裂有問題，有沒有大佬教教我。本人新手。

uj5u.com熱心網友回復：

#include<iostream>
using namespace std;

template<class K,int M=3>
struct BTreeNode
{
    BTreeNode()
    :_pParent(NULL)
    , _size(0)
    {
        for (size_t i = 0; i <= M; i++)
        {
            _pSub[i] = NULL;
        }
    }

    K _key[M];
    BTreeNode<K, M> *_pSub[M + 1];
    BTreeNode<K, M> *_pParent;
    size_t _size;
};

template<class K,int M=3>
class BTree
{
    typedef BTreeNode<K, M> Node;
    typedef Node* pNode;
public:
    BTree()
        :_pRoot(NULL)
    {}

    bool Insert(K& key)
    {
        if (_pRoot == NULL)     //無根節點
        {
            _pRoot = new Node();
            _pRoot->_key[0] = key;
            _pRoot->_size = 1;
            return true;
        }

        pair<pNode, int> ret = Find(key);
        if (ret.second >= 0)
            return false;
        pNode pCur = ret.first;
        pNode pSub = NULL;
        while (1)
        {
            _Insert(pCur, key, pSub);
            size_t size = pCur->_size;
            if (size < M)
                return true;
            else
            {
                size_t mid = size >> 1;
                pNode tmp = new Node();
                for (size_t i= mid + 1; i < size; i++)
                {
                    tmp->_key[tmp->_size] = pCur->_key[i];
                    tmp->_pSub[tmp->_size] = pCur->_pSub[i];
                    if (tmp->_pSub[tmp->_size])
                        tmp->_pSub[tmp->_size]->_pParent = tmp;
                    tmp->_size++;
                }
                tmp->_pSub[tmp->_size] = pCur->_pSub[pCur->_size];

                if (tmp->_pSub[tmp->_size])
                    tmp->_pSub[tmp->_size]->_pParent = tmp;
                pCur->_size -= (tmp->_size + 1);               //處理size

                if (pCur == _pRoot)                            //如果當前結點是根結點，還需要再處理
                {
                    _pRoot = new Node;
                    _pRoot->_key[0] = pCur->_key[mid];
                    _pRoot->_pSub[0] = pCur;
                    pCur->_pParent = _pRoot;
                    _pRoot->_pSub[1] = tmp;
                    tmp->_pParent = _pRoot;
                    _pRoot->_size = 1;
                    return true;
                }
                else
                {
                    key = pCur->_key[mid];
                    pCur = pCur->_pParent;
                    pSub = tmp;
                }
            }
        }
    }

    pair<pNode, int> Find(const K& key)
    {
        pNode pCur = _pRoot;
        pNode pParent = NULL;

        while (pCur)
        {
            size_t i = 0;
            while (i < pCur->_size)
            {
                if (key == pCur->_key[i])
                    return pair<pNode, int>(pCur, i);
                else if (key < pCur->_key[i])
                    break;
                else
                    i++;
            }
            pParent = pCur;
            pCur = pCur->_pSub[i];
        }
        return make_pair(pParent, -1);//沒找到回傳-1
    }
private:
    void _Insert(pNode pCur, const K& key, pNode pSub)
    {
        //直接插入的思想
        int end = pCur->_size - 1;
        while (key < pCur->_key[end] && end >= 0)
        {
            pCur->_key[end + 1] = pCur->_key[end];
            pCur->_pSub[end + 2] = pCur->_pSub[end + 1];
            end--;
        }

        pCur->_key[end + 1] = key;
        pCur->_pSub[end + 2] = pSub;
        if (pSub)
            pSub->_pParent = pCur;
        pCur->_size += 1;
    }
private:
    Node *_pRoot;
};

int main()
{
    int arr[] = { 53, 75, 139, 49, 145, 36, 101 };
    BTree<int> b;
    size_t size = sizeof(arr) / sizeof(arr[0]);
    for (size_t i = 0; i < 7; i++)
        b.Insert(arr[i]);

    system("pause");
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/20670.html

標籤：基礎類

上一篇：萌新。51單片機串口使字串倒敘

下一篇：謝謝大佬們了