大师兄的数据结构学习笔记(十）: 伸展树
大师兄的数据结构学习笔记(十二）: 红黑树

一、关于B树

1. 分级存储

• 在计算机中，为了满足容量和访问速度的需求，通常用内存(高速度)和硬盘(大容量)进行分级存储。
• 内存的访问速度大致为纳秒(ns)而硬盘位毫秒(ms)，相差5-6个数量级, 应尽可能减少对外存(硬盘)的访问。

2. 多路搜索树

• 外部存储器具备的另一特性：适合批量式访问，即读取物理地址连续的1000个字节和读取几个字节没区别。
• 所以，应使用时间成本相对较低的多次内存操作，替代时间成本相对较高的单次外存(硬盘)操作。
• 为此，我们需要改造二叉搜索树为多路搜索树，让子树大于或等于两个，让树由"瘦高"变"矮胖"。
  
• 因此，在多路搜索树中，各节点与其左、右孩子合并为大节点, 节点到左、右孩子的分支转化为大节点的内部搜索。
• 多路搜索树在查找等搜索时，搜索每下降一层，都以大节点为单位从外存(硬盘)读取一组关键码。

3. B树

• 所谓m阶的B树(B-tree)，即m路的多路搜索树。
  
• 每个节点最多有m个孩子。
• 除了根节点和叶子节点外，其它每个节点至少有个孩子。
• 若根节点不是叶子节点，则至少有2个孩子。
• 所有叶子节点都在同一层，且不包含其它关键字信息
• 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
• 关键字的个数n满足:
• ki(i=1,…n)为关键字，且关键字升序排序。
• Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)
• B树的最低搜索效率是

二、实现B树

1. 节点结构

template<class T>
struct Node
{
    int count;      //统计
    T* key;         //关键值列表
    Node** child;   //子节点的列表
    bool leaf;      //是否为叶结点
};

2. BTree类

template<class T>
class BTree
{
public:
    BTree();                //构造函数
    ~BTree();               //析构函数
    bool Insert(int key);   //插入节点
    bool Delete(int key);   //删除节点
    void Display();         //打印树
private:
    Node<T>* search(Node<T>* pNode, int key); //查找节点
    Node<T>* AllocateNode(); //重置节点
    void SplitChild(Node<T>* pParent, Node<T>* pChild, int index);
    Node<T>* unionChild(Node<T>* pParent, Node<T>* pCLeft, Node<T>* pCRright, int index); //合并大节点
    void InsertNonfull(Node<T>* pNode, int key);
    int Max(Node<T>* pNode); //最大结点
    int min(Node<T>* pNode); //最小结点
    bool DeleteNonHalf(Node<T>* pNode, int key);
    void DellocateNode(Node<T>* pNode);
    void DeleteTree(Node<T>* pNode);
    void print(Node<T>* pNode);
private:
    Node<T>* root; //根节点
    int M; // 度数 
};

3. 方法实现

template<class T>
//构造函数
BTree<T>::BTree() :root(nullptr), M(4)
{

};

template<class T>
//析构函数
BTree<T>::~BTree()
{
    DeleteTree(root);
    delete root;
};

template<class T>
//插入节点
bool BTree<T>::Insert(int key)
{
    Node<T>* r = root;
    if (!r)
    {
        r = AllocateNode();
        r->leaf = true;
        r->count = 0;

        root = r;
    }

    if (r && r->count == (2 * M - 1))
    {
        Node<T>* s = AllocateNode();
        root = s;
        s->leaf = false;
        s->count = 0;
        s->child[1] = r;
        SplitChild(s, r, 1);
        InsertNonfull(s, key);
    }
    else
    {
        InsertNonfull(r, key);
    }

    return true;
};

template<class T>
//删除节点
bool BTree<T>::Delete(int key)
{
    return DeleteNonHalf(root, key);
};

template<class T>
//删除节点
void BTree<T>::Display()
{
    print(root);
};

template<class T>
// 查找节点
Node<T>* BTree<T>::search(Node<T>* pNode, int key)
{
    int i = 1;
    while (i <= pNode->count && key > pNode->key[i])
    {
        i++;
    }

    if (i < pNode->count && key == pNode->key[i])
        return pNode->child[i];

    if (pNode->leaf)
        return nullptr;
    else
        return search(pNode->child[i], key);
}

template<class T>
// 重置节点
Node<T>* BTree<T>::AllocateNode()
{
    Node<T>* pTemp = new Node<T>;
    pTemp->key = new T[2 * M];
    pTemp->child = new Node<T>* [2 * M + 1];

    for (int i = 0; i < 2 * M; i++)
    {
        pTemp->key[i] = 0;
        pTemp->child[i] = nullptr;
    }
    pTemp->child[2 * M] = nullptr;

    return pTemp;
}

template<class T>
void BTree<T>::SplitChild(Node<T>* pParent, Node<T>* pChild, int index)
{
    Node<T>* pChildEx = AllocateNode();
    pChildEx->leaf = pChild->leaf;
    pChildEx->count = M - 1;

    for (int j = 1; j < M; j++)
    {
        pChildEx->key[j] = pChild->key[j + M];
    }

    if (!pChild->leaf)
    {
        for (int j = 1; j <= M; j++)
            pChildEx->child[j] = pChild->child[j + M];
    }

    pChild->count = M - 1;

    for (int j = pParent->count + 1; j > index; j--)
    {
        pParent->child[j + 1] = pParent->child[j];
    }
    pParent->child[index + 1] = pChildEx;

    for (int j = pParent->count + 1; j >= index; j--)
    {
        pParent->key[j + 1] = pParent->key[j];
    }
    pParent->key[index] = pChild->key[M];
    pParent->count++;
}

template<class T>
//合并大节点
Node<T>* BTree<T>::unionChild(Node<T>* pParent, Node<T>* pCLeft, Node<T>* pCRight, int index)
{
    for (int i = 1; i < M; i++)
    {
        pCLeft->key[M + i] = pCRight->key[i];
    }
    pCLeft->key[M] = pParent->key[index];

    for (int i = 1; i <= M; i++)
    {
        pCLeft->child[M + i] = pCRight->child[i];
    }
    pCLeft->count = 2 * M - 1;

    for (int i = index; i < pParent->count; i++)
    {
        pParent->key[i] = pParent->key[i + 1];
    }

    for (int i = index + 1; i <= pParent->count; i++)
    {
        pParent->child[i] = pParent->child(i + 1);
    }
    pParent->count--;

    DellocateNode(pCRight);

    if (pParent->count == 0)
    {
        DellocateNode(root);
        root = pCLeft;
    }
    return pCLeft;
}

template<class T>
void BTree<T>::InsertNonfull(Node<T>* pNode, int key)
{
    int i = pNode->count;

    if (pNode->leaf)
    {
        while (i >= 1 && key < pNode->key[i])
        {
            pNode->key[i + 1] = pNode->key[i];
            i--;
        }

        pNode->key[i + 1] = key;
        pNode->count++;
    }
    else
    {
        while (i >= 1 && key < pNode->key[i])
        {
            i--;
        }
        i++;

        if (pNode->child[i]->count == (2 * M - 1))
        {
            SplitChild(pNode, pNode->child[i], i);
            if (key > pNode->key[i])
                i++;
        }

        InsertNonfull(pNode->child[i], key);
    }
}

template<class T>
// 最大结点
int BTree<T>::Max(Node<T>* pNode)
{
    while (!pNode->leaf)
    {
        pNode = pNode->child[pNode->count + 1];
    }
    return pNode->key[pNode->count];
}

template<class T>
//最小结点
int BTree<T>::min(Node<T>* pNode)
{
    while (!pNode->leaf)
    {
        pNode = pNode->child[1];
    }
    return pNode->key[1];
}

template<class T>
bool BTree<T>::DeleteNonHalf(Node<T>* pNode, int key)
{
    int i = 1;

    while (i <= pNode->count && key > pNode->key[i])
        i++;

    if (pNode->leaf) //如果是叶结点
    {
        if (i <= pNode->count && key == pNode->key[i])
        {
            for (int j = i; j < pNode->count; j++)
            {
                pNode->key[j] = pNode->key[j + 1];
            }
            pNode->count--;
            return true;
        }
        else
        {
            return false;
        }
    }

    if (i <= pNode->count && key == pNode->key[i]) //如果是子结点
    {
        if (pNode->child[i]->count >= M)
        {
            key = Max(pNode->child[i]);
            pNode->key[i] = key;
            return DeleteNonHalf(pNode->child[i], key);
        }
        else if (pNode->child[i + 1]->count >= M)
        {
            key = Min(pNode->child[i + 1]);
            pNode->key[i] = key;
            return DeleteNonHalf(pNode->child[i + 1], key);
        }
        else
        {
            Node<T> pChild = unionChild(pNode, pNode->child[i], pNode->child[i + 1], i);
            return DeleteNonHalf(pChild, key);
        }
    }
    else if (pNode->child[i]->count == M - 1) //根节点
    {
        if (i > 1 && pNode->child[i - 1]->count >= M)
        {
            Node<T>* pMidNode = pNode->child[i];
            Node<T>* pPreNode = pNode->child[i - 1];

            int preNode_keyCount = pPreNode->count;

            for (int j = pMidNode->count + 1; j > 1; j--)
            {
                pMidNode->key[j] = pMidNode->key[j - 1];
            }
            pMidNode->key[1] = pNode->key[i - 1];

            for (int j = pMidNode->count + 2; j > 1; j--)
            {
                pMidNode->child[j] = pMidNode->child[j - 1];
            }
            pMidNode->child[1] = pPreNode->child[preNode_keyCount + 1];
            pMidNode->count++;

            pNode->key[i - 1] = pPreNode->key[preNode_keyCount];

            pPreNode->key[preNode_keyCount] = 0;
            pPreNode->key[preNode_keyCount + 1] = nullptr;
            pPreNode->count--;

            return DeleteNonHalf(pMidNode, key);
        }
        else if (i <= pNode->count && pNode->child[i + 1]->count >= M)
        {
            Node<T>* pMidNode = pNode->child[i];
            Node<T>* pNextNode = pNode->child[i + 1];

            int nextNode_keyCount = pNextNode->count;
            int midNode_keyCount = pMidNode->count;

            pMidNode->key[midNode_keyCount + 1] = pNode->key[i];
            pMidNode->child[midNode_keyCount + 2] = pNextNode->child[1];
            pMidNode->count++;

            pNode->key[i] = pNextNode->key[i];

            for (int j = 1; j < nextNode_keyCount; j++)
            {
                pNextNode->key[j] = pNextNode->key[j + 1];
            }
            for (int j = 1; j < nextNode_keyCount;j++)
            {
                pNextNode->child[j] = pNextNode->child[j + 1];
            }
            pNextNode->count--;

            return DeleteNonHalf(pMidNode, key);
        }
        else
        {
            if (i > pNode->count)
            {
                i--;
            }
            Node<T>* pChild = unionChild(pNode, pNode->child[i], pNode->child[i + 1], i);
            return DeleteNonHalf(pChild, key);
        }
    }
    return DeleteNonHalf(pNode->child[i], key);
}

template<class T>
void BTree<T>::DellocateNode(Node<T>* pNode)
{
    delete[] pNode->key;
    delete[] pNode->child;
    delete pNode;
}

template<class T>
void BTree<T>::DeleteTree(Node<T>* pNode)
{
    if (pNode->leaf)
    {
        delete[] pNode->key;
        delete[] pNode->child;
    }
    else
    {
        for (int i = 1; i <= pNode->count + 1; i++)
        {
            DeleteTree(pNode->child[i]);
            delete pNode->child[i];
        }

        delete[] pNode->key;
        delete[] pNode->child;
    }
}

template<class T>
void BTree<T>::print(Node<T>* pNode)
{
    if (pNode->leaf)
    {
        cout << "leaf count = "<< pNode->count << ":";
        for (int i = 1; i <= pNode->count; i++)
        {
            cout << pNode->key[i] << ",";
        }
        cout << endl;
    }
    else
    {
        for (int i = 1; i <= pNode->count + 1; i++)
        {
            //cout << pNode->child[i] << endl;
            print(pNode->child[i]);
        }
        cout << "inner node count:" << pNode->count << ":";

        for (int i = 1; i < pNode->count; i++)
        {
            cout << pNode->key[i] << ",";
        }
        cout << endl;
    }
}