树 C++模板类封装（有图有真相）

    bool Insert(K& key)

    {

        // 1.B-树为空

        if (NULL == _root)

        {

            _root = new BTreeNode<K, M>;

            _root->_key[0] = key;

            ++_root->_size;

            return true;

        }

 

        Pair<BTreeNode<K, M>*, int> ret = Find(key);

        // 2.该数据已经存在

        if (ret._second != -1) 

            return false;

 

        // 3.插入数据到关键字数组

        BTreeNode<K, M>* cur = ret._first;

        BTreeNode<K, M>* sub = NULL;

        while (1)

        {

            int i = 0;

            for ( i = cur->_size - 1; i >= 0; )

            { // 把大数往后挪，对应子树也要进行挪动

                if (cur->_key[i] > key)

                {

                    cur->_key[i + 1] = cur->_key[i];

                    cur->_sub[i + 2] = cur->_sub[i + 1];

                    i--;

                }

                else

                {

                    break;

                }

            }

            cur->_key[i + 1] = key;

            cur->_sub[i + 2] = sub;

            if (sub!=NULL)

                cur->_sub[i+2]->_parent = cur;

            cur->_size++;

 

            //关键字数组未满，插入成功

            if (cur->_size < M)

                return true;

 

            //关键字数组已满，需要进行分裂

            int mid = M / 2;

            BTreeNode<K, M>* tmp = new BTreeNode<K, M>;

            int index = 0;

            size_t k;

 

            for ( k = mid + 1; k < cur->_size; k++)

            {

                tmp->_key[index] = cur->_key[k];

                if (cur->_sub[k] != NULL)

                {

                    tmp->_sub[index] = cur->_sub[k];

                    cur->_sub[k] = NULL;

                    tmp->_sub[index]->_parent = tmp;

                }

                tmp->_size++;

                cur->_size--;

                index++;

            }

            if (cur->_sub[k] != NULL)

            {

                tmp->_sub[index] = cur->_sub[k];

                cur->_sub[k] = NULL;

                tmp->_sub[index]->_parent = tmp;

            }

            //父节点为空时的链接

            if (cur->_parent == NULL)

            {

                _root = new BTreeNode<K, M>;

                _root->_key[0] = cur->_key[mid];

                cur->_size--;

                _root->_sub[0] = cur;

                _root->_sub[1] = tmp;

                _root->_size++;

                 

                //链接

                tmp->_parent = _root;

                cur->_parent = _root;

                return true;

            }

            //父节点不为空时的链接

            key = cur->_key[mid];

            cur->_size--;

            cur = cur->_parent;

            sub = tmp;

        }