大師兄的數據結構學習筆記(十一）: B樹

大師兄的數據結構學習筆記(十）: 伸展樹
大師兄的數據結構學習筆記(十二）: 紅黑樹

一、關于B樹

1. 分級存儲
  • 在計算機中，為了滿足容量和訪問速度的需求，通常用內存(高速度)和硬盤(大容量)進行分級存儲。
  • 內存的訪問速度大致為納秒(ns)而硬盤位毫秒(ms)，相差5-6個數量級, 應盡可能減少對外存(硬盤)的訪問。
2. 多路搜索樹
  • 外部存儲器具備的另一特性：適合批量式訪問，即讀取物理地址連續(xù)的1000個字節(jié)和讀取幾個字節(jié)沒區(qū)別。
  • 所以，應使用時間成本相對較低的多次內存操作，替代時間成本相對較高的單次外存(硬盤)操作。
  • 為此，我們需要改造二叉搜索樹為多路搜索樹，讓子樹大于或等于兩個，讓樹由"瘦高"變"矮胖"。
  • 因此，在多路搜索樹中，各節(jié)點與其左、右孩子合并為大節(jié)點, 節(jié)點到左、右孩子的分支轉化為大節(jié)點的內部搜索。
  • 多路搜索樹在查找等搜索時，搜索每下降一層，都以大節(jié)點為單位從外存(硬盤)讀取一組關鍵碼。
3. B樹
  • 所謂m階的B樹(B-tree)，即m路的多路搜索樹(m\geq2)。
  • 每個節(jié)點最多有m個孩子。
  • 除了根節(jié)點和葉子節(jié)點外，其它每個節(jié)點至少有m/2個孩子。
  • 若根節(jié)點不是葉子節(jié)點，則至少有2個孩子。
  • 所有葉子節(jié)點都在同一層，且不包含其它關鍵字信息
  • 每個非終端節(jié)點包含n個關鍵字信息（P0,P1,…Pn, k1,…kn）
  • 關鍵字的個數n滿足: m/2-1 <= n <= m-1
  • ki(i=1,…n)為關鍵字，且關鍵字升序排序。
  • Pi(i=1,…n)為指向子樹根節(jié)點的指針。P(i-1)指向的子樹的所有節(jié)點關鍵字均小于ki，但都大于k(i-1)
  • B樹的最低搜索效率是O\log_2N

二、實現B樹

1. 節(jié)點結構
template<class T>
struct Node
{
    int count;      //統(tǒng)計
    T* key;         //關鍵值列表
    Node** child;   //子節(jié)點的列表
    bool leaf;      //是否為葉結點
};
2. BTree類
template<class T>
class BTree
{
public:
    BTree();                //構造函數
    ~BTree();               //析構函數
    bool Insert(int key);   //插入節(jié)點
    bool Delete(int key);   //刪除節(jié)點
    void Display();         //打印樹
private:
    Node<T>* search(Node<T>* pNode, int key); //查找節(jié)點
    Node<T>* AllocateNode(); //重置節(jié)點
    void SplitChild(Node<T>* pParent, Node<T>* pChild, int index);
    Node<T>* unionChild(Node<T>* pParent, Node<T>* pCLeft, Node<T>* pCRright, int index); //合并大節(jié)點
    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; //根節(jié)點
    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>
//插入節(jié)點
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>
//刪除節(jié)點
bool BTree<T>::Delete(int key)
{
    return DeleteNonHalf(root, key);
};

template<class T>
//刪除節(jié)點
void BTree<T>::Display()
{
    print(root);
};

template<class T>
// 查找節(jié)點
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>
// 重置節(jié)點
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>
//合并大節(jié)點
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) //根節(jié)點
    {
        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;
    }
}
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容