C++資料結構之紅黑樹的實現

2022-08-07 14:00:58

一、什麼是紅黑樹

紅黑樹在表意上就是一棵每個節點帶有顏色的二元搜尋樹，並通過對節點顏色的控制，使該二元搜尋樹達到儘量平衡的狀態。所謂儘量平衡的狀態就是：紅黑樹確保沒有一條路徑比其他路徑長兩倍。

和AVL樹不同的是，AVL樹是一棵平衡樹，而紅黑樹可能平衡也可能不平衡(因為是儘量平衡的狀態)

二、紅黑樹的約定

要實現一棵紅黑樹，即要紅黑樹確保沒有一條路徑比其他路徑長兩倍。通過對節點顏色的約定來實現這一目標。

1.根節點是黑色的。

2.如果一個節點是紅色的，則它的兩個孩子都是黑色的。

3.對於每個節點，從該節點到其所有後代節點的簡單路徑上，均包含相同數量的黑色節點。

實現了這三條顏色規則的二元搜尋樹，即也實現了沒有一條路徑比其他路徑長兩倍，即實現了一棵紅黑樹。

三、紅黑樹vsAVL

1、調整平衡的實現機制不同

紅黑樹根據節點顏色(同一父節點出發到葉子節點，所有路徑上的黑色節點數目一樣)，一些約定和旋轉實現。

AVL根據樹的平衡因子(所有節點的左右子樹高度差的絕對值不超過1)和旋轉決定。

2、紅黑樹的插入效率更高

紅黑樹是用非嚴格的平衡來換取增刪節點時候旋轉次數的降低，任何不平衡都會在三次旋轉之內解決，紅黑樹並不追求“完全平衡”，它只要求部分地達到平衡要求，降低了對旋轉的要求，從而提高了效能

而AVL是嚴格平衡樹(高度平衡的二元搜尋樹)，因此在增加或者刪除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多。所以紅黑樹的插入效率更高

3、AVL查詢效率高

如果你的應用中，查詢的次數遠遠大於插入和刪除，那麼選擇AVL樹，如果查詢和插入刪除次數幾乎差不多，應選擇紅黑樹。即，有時僅為了排序（建立-遍歷-刪除），不查詢或查詢次數很少，R-B樹合算一些。

四、紅黑樹的實現

實現一棵紅黑樹，本質是實現它的插入函數，使插入函數可以實現紅黑樹的顏色約定，它的實現分為兩步，即先找到插入的位置，再控制平衡。插入函數返回值設計為bool，插入成功返回true，失敗返回false。控制平衡時，需要關注四個節點，即新插入的節點，它的父節點，它的叔叔節點，它的祖父節點。

1.找到插入的位置

當為第一個節點的時候，顏色設為黑，直接插入。

當插入的不是第一個節點時，顏色設為紅，需要根據二元搜尋樹的性質找到插入位置。並實現三叉鏈。

        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = Black;
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        cur->_col= Red;
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }

2.控制平衡

(1)當父節點為黑

當父節點為黑的時候，由於插入的子節點的顏色為紅，對三個約定沒有任何影響，因此不需要調整平衡。

(2)判斷父節點在祖父節點的位置

通過判斷父節點在祖父節點的位置，來定義叔叔節點的位置，以及之後的旋轉方向的判斷。

while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
   Node* uncle = grandfather->_right;
   //三種情況的處理
}
else
{
   Node* uncle = grandfather->_left;
   //三種情況的處理
}

首先需要使用大回圈，這個迴圈是為情況1而準備的，情況2和3直接跳出迴圈即可，因為只有情況1對上層迴圈有影響。
下面我們以父節點在祖父節點的左側為例，右側同理。

(3)叔叔節點存在且為紅

解決方案：將父節點和叔叔節點設為黑，將祖父節點設為紅。然後將祖父節點作為新節點繼續向上平衡。如果祖父節點是根節點，那麼需要再將其置為黑。

注意，這種情況和其他情況不同的是，需要將祖父節點作為新插入的節點繼續向上遍歷，這說明需要一個迴圈。而其他型別的情況直接break跳出這個迴圈即可。

//第一種情況
if (uncle && uncle->_col == Red)
{
    parent->_col = uncle->_col = Black;
    grandfather->_col = Red;
    cur = grandfather;
    parent = cur->_parent;
}

這種情況只需要控制顏色即可，但是要繼續向上迴圈。

(4)父節點為紅，叔叔不存在或存在且為黑，新插入的節點在父節點左側

解決方案：對祖父節點右旋操作，並將祖父節點置為紅，父節點置為黑。

關於旋轉的細節，我在AVL樹中有詳細的解釋：C++手撕AVL樹

//第二種情況，右單旋
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}

(5)父節點為紅，叔叔不存在或存在且為黑，新插入的節點在父節點右側

解決方案：進行雙旋，即對父節點進行左單旋，祖父節點進行右單旋。將子節點置為黑，將祖父節點置為紅。

else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}

(6)最後置黑

每一次插入都對根節點置為黑操作，因為第一種情況可能導致根節點不是黑。同時對根節點置黑也並不違反三條規定。

3.測試程式碼

當我們處理完父節點在祖父節點的左側後，處理父節點在祖父節點的右側。

全部處理之後，我們的插入程式碼就完成了，接下來要對整個樹進行測試，即對三個約定來進行測試：

1.當根節點為紅時，返回false。

2.判斷一個節點和其父節點的顏色是否都為紅，若都為紅返回false。

3.以最左的一條路徑上的根節點數量為基準，通過遞迴遍歷每一條路徑上的根節點的數量，當每條路徑遍歷節點到空時，將兩者進行比較，如果最終結果不相等則返回false。

    bool IsBalance()
    {
        if (_root && _root->_col == Red)
        {
            cout << "根節點不是黑色的" << endl;
            return false;
        }
        int banchmark = 0;
        //以最右邊一條路徑為基準
        Node* left = _root;
        while (left)
        {
            if (left->_col == Black)
            {
                ++banchmark;
            }
            left = left->_left;
        }
        int blackNum = 0;
        return _IsBalance(_root, banchmark, blackNum);
    }
    bool _IsBalance(Node* root, int banchmark, int blackNum)
    {
        if (root == nullptr)
        {
            if (banchmark != blackNum)
            {
                cout << "黑色根節點數目不相等" << endl;
                return false;
            }
            return true;
        }
        if (root->_col == Red && root->_parent->_col == Red)
        {
            cout << "出現連續的紅色節點" << endl;
            return false;
        }
        if (root->_col == Black)
        {
            ++blackNum;
        }
        return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
    }

五、完整程式碼

1.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"RBtree.h"
#include<vector>
int main()
{
    RBTree<int, int> t;
    vector<int> v;
    srand(time(0));
    int N = 100000;
    int count = 0;
    for (int i = 0; i < N; i++)
    {
        v.push_back(rand());
    }
    for (auto e : v)
    {
        pair<int,int> kv(e, e);
        t.insert(kv);
        if (t.IsBalance())
        {
            cout << "insert" << e << endl;
            count++;
            cout << count << endl;
        }
        else
        {
            cout << e << "插入失敗" << endl;
            cout << "不是平衡的" << endl;
            break;
        }
    }
}

2.RBTree.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Color
{
    Red,
    Black
};
template<class K,class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Color _col;
    RBTreeNode(pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _col(Red)
        , _kv(kv)
    {}
};
template<class K,class V>
struct RBTree
{
    typedef RBTreeNode<K, V> Node;
private:
    Node* _root;
public:
    RBTree()
        :_root(nullptr)
    {}
    bool IsBalance()
    {
        if (_root && _root->_col == Red)
        {
            cout << "根節點不是黑色的" << endl;
            return false;
        }
        int banchmark = 0;
        //以最右邊一條路徑為基準
        Node* left = _root;
        while (left)
        {
            if (left->_col == Black)
            {
                ++banchmark;
            }
            left = left->_left;
        }
        int blackNum = 0;
        return _IsBalance(_root, banchmark, blackNum);
    }
    bool _IsBalance(Node* root, int banchmark, int blackNum)
    {
        if (root == nullptr)
        {
            if (banchmark != blackNum)
            {
                cout << "黑色根節點數目不相等" << endl;
                return false;
            }
            return true;
        }
        if (root->_col == Red && root->_parent->_col == Red)
        {
            cout << "出現連續的紅色節點" << endl;
            return false;
        }
        if (root->_col == Black)
        {
            ++blackNum;
        }
        return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
    }
    //右單旋
    void RotateR(Node* parent)
    {
        Node* cur = parent->_left;
        Node* curL = cur->_left;
        Node* curR = cur->_right;
        Node* parentParent = parent->_parent;
        parent->_left = curR;
        if (curR)
            curR->_parent = parent;
        cur->_right = parent;
        parent->_parent = cur;
        if (parent == _root)
        {
            _root = cur;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = cur;
                cur->_parent = parentParent;
            }
            else if (parentParent->_right == parent)
            {
                parentParent->_right = cur;
                cur->_parent = parentParent;
            }
            else
            {
                assert(false);
            }
        }
    }
    //左單旋
    void RotateL(Node* parent)
    {
        Node* cur = parent->_right;
        Node* curL = cur->_left;
        Node* parentParent = parent->_parent;
        parent->_right = curL;
        if (curL)
            curL->_parent = parent;
        cur->_left = parent;
        parent->_parent = cur;
        if (parent == _root)
        {
            _root = cur;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = cur;
                cur->_parent = parentParent;
            }
            else if (parentParent->_right == parent)
            {
                parentParent->_right = cur;
                cur->_parent = parentParent;
            }
            else
            {
                assert(false);
            }
        }
    }
    bool insert(pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = Black;
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        cur->_col= Red;
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        while (parent && parent->_col == Red)
        {
            Node* grandfather = parent->_parent;
            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;
                //第一種情況
                if (uncle && uncle->_col == Red)
                {
                    parent->_col = uncle->_col = Black;
                    grandfather->_col = Red;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    //第二種情況，右單旋
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);
                        parent->_col = Black;
                        grandfather->_col = Red;
                    }
                    //第三種情況，左右雙旋
                    else
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = Black;
                        grandfather->_col = Red;
                    }
                    break;
                }
                _root->_col = Black;
            }
            else
            {
                Node* uncle = grandfather->_left;
                //第一種情況
                if (uncle && uncle->_col == Red)
                {
                    parent->_col = uncle->_col = Black;
                    grandfather->_col = Red;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    //第二種情況，左單旋
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        parent->_col = Black;
                        grandfather->_col = Red;
                    }
                    //第三種情況，右左雙旋
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = Black;
                        grandfather->_col = Red;
                    }
                    break;
                }
                _root->_col = Black;
            }
        }
    }
};

到此這篇關於C++資料結構之紅黑樹的實現的文章就介紹到這了,更多相關C++紅黑樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！