C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹如何實(shí)現(xiàn)

這篇文章主要介紹“C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹如何實(shí)現(xiàn)”，在日常操作中，相信很多人在C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹如何實(shí)現(xiàn)問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹如何實(shí)現(xiàn)”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

一、什么是紅黑樹

紅黑樹在表意上就是一棵每個(gè)節(jié)點(diǎn)帶有顏色的二叉搜索樹，并通過(guò)對(duì)節(jié)點(diǎn)顏色的控制，使該二叉搜索樹達(dá)到盡量平衡的狀態(tài)。所謂盡量平衡的狀態(tài)就是：紅黑樹確保沒有一條路徑比其他路徑長(zhǎng)兩倍。

和AVL樹不同的是，AVL樹是一棵平衡樹，而紅黑樹可能平衡也可能不平衡(因?yàn)槭潜M量平衡的狀態(tài))

二、紅黑樹的約定

要實(shí)現(xiàn)一棵紅黑樹，即要紅黑樹確保沒有一條路徑比其他路徑長(zhǎng)兩倍。通過(guò)對(duì)節(jié)點(diǎn)顏色的約定來(lái)實(shí)現(xiàn)這一目標(biāo)。

1.根節(jié)點(diǎn)是黑色的。

2.如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子都是黑色的。

3.對(duì)于每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代節(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)量的黑色節(jié)點(diǎn)。

實(shí)現(xiàn)了這三條顏色規(guī)則的二叉搜索樹，即也實(shí)現(xiàn)了沒有一條路徑比其他路徑長(zhǎng)兩倍，即實(shí)現(xiàn)了一棵紅黑樹。

三、紅黑樹vsAVL

1、調(diào)整平衡的實(shí)現(xiàn)機(jī)制不同

紅黑樹根據(jù)節(jié)點(diǎn)顏色(同一父節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)，所有路徑上的黑色節(jié)點(diǎn)數(shù)目一樣)，一些約定和旋轉(zhuǎn)實(shí)現(xiàn)。

AVL根據(jù)樹的平衡因子(所有節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值不超過(guò)1)和旋轉(zhuǎn)決定。

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

紅黑樹是用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，紅黑樹并不追求“完全平衡”，它只要求部分地達(dá)到平衡要求，降低了對(duì)旋轉(zhuǎn)的要求，從而提高了性能

而AVL是嚴(yán)格平衡樹(高度平衡的二叉搜索樹)，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多。所以紅黑樹的插入效率更高

3、AVL查找效率高

如果你的應(yīng)用中，查詢的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除，那么選擇AVL樹，如果查詢和插入刪除次數(shù)幾乎差不多，應(yīng)選擇紅黑樹。即，有時(shí)僅為了排序（建立-遍歷-刪除），不查找或查找次數(shù)很少，R-B樹合算一些。

四、紅黑樹的實(shí)現(xiàn)

實(shí)現(xiàn)一棵紅黑樹，本質(zhì)是實(shí)現(xiàn)它的插入函數(shù)，使插入函數(shù)可以實(shí)現(xiàn)紅黑樹的顏色約定，它的實(shí)現(xiàn)分為兩步，即先找到插入的位置，再控制平衡。插入函數(shù)返回值設(shè)計(jì)為bool，插入成功返回true，失敗返回false?？刂破胶鈺r(shí)，需要關(guān)注四個(gè)節(jié)點(diǎn)，即新插入的節(jié)點(diǎn)，它的父節(jié)點(diǎn)，它的叔叔節(jié)點(diǎn)，它的祖父節(jié)點(diǎn)。

1.找到插入的位置

當(dāng)為第一個(gè)節(jié)點(diǎn)的時(shí)候，顏色設(shè)為黑，直接插入。

當(dāng)插入的不是第一個(gè)節(jié)點(diǎn)時(shí)，顏色設(shè)為紅，需要根據(jù)二叉搜索樹的性質(zhì)找到插入位置。并實(shí)現(xiàn)三叉鏈。

        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)當(dāng)父節(jié)點(diǎn)為黑

當(dāng)父節(jié)點(diǎn)為黑的時(shí)候，由于插入的子節(jié)點(diǎn)的顏色為紅，對(duì)三個(gè)約定沒有任何影響，因此不需要調(diào)整平衡。

(2)判斷父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的位置

通過(guò)判斷父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的位置，來(lái)定義叔叔節(jié)點(diǎn)的位置，以及之后的旋轉(zhuǎn)方向的判斷。

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

首先需要使用大循環(huán)，這個(gè)循環(huán)是為情況1而準(zhǔn)備的，情況2和3直接跳出循環(huán)即可，因?yàn)橹挥星闆r1對(duì)上層循環(huán)有影響。
下面我們以父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的左側(cè)為例，右側(cè)同理。

(3)叔叔節(jié)點(diǎn)存在且為紅

解決方案：將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)設(shè)為黑，將祖父節(jié)點(diǎn)設(shè)為紅。然后將祖父節(jié)點(diǎn)作為新節(jié)點(diǎn)繼續(xù)向上平衡。如果祖父節(jié)點(diǎn)是根節(jié)點(diǎn)，那么需要再將其置為黑。

注意，這種情況和其他情況不同的是，需要將祖父節(jié)點(diǎn)作為新插入的節(jié)點(diǎn)繼續(xù)向上遍歷，這說(shuō)明需要一個(gè)循環(huán)。而其他類型的情況直接break跳出這個(gè)循環(huán)即可。

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

這種情況只需要控制顏色即可，但是要繼續(xù)向上循環(huán)。

(4)父節(jié)點(diǎn)為紅，叔叔不存在或存在且為黑，新插入的節(jié)點(diǎn)在父節(jié)點(diǎn)左側(cè)

解決方案：對(duì)祖父節(jié)點(diǎn)右旋操作，并將祖父節(jié)點(diǎn)置為紅，父節(jié)點(diǎn)置為黑。

關(guān)于旋轉(zhuǎn)的細(xì)節(jié)，我在AVL樹中有詳細(xì)的解釋：C++手撕AVL樹

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

(5)父節(jié)點(diǎn)為紅，叔叔不存在或存在且為黑，新插入的節(jié)點(diǎn)在父節(jié)點(diǎn)右側(cè)

解決方案：進(jìn)行雙旋，即對(duì)父節(jié)點(diǎn)進(jìn)行左單旋，祖父節(jié)點(diǎn)進(jìn)行右單旋。將子節(jié)點(diǎn)置為黑，將祖父節(jié)點(diǎn)置為紅。

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

(6)最后置黑

每一次插入都對(duì)根節(jié)點(diǎn)置為黑操作，因?yàn)榈谝环N情況可能導(dǎo)致根節(jié)點(diǎn)不是黑。同時(shí)對(duì)根節(jié)點(diǎn)置黑也并不違反三條規(guī)定。

3.測(cè)試代碼

當(dāng)我們處理完父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的左側(cè)后，處理父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的右側(cè)。

全部處理之后，我們的插入代碼就完成了，接下來(lái)要對(duì)整個(gè)樹進(jìn)行測(cè)試，即對(duì)三個(gè)約定來(lái)進(jìn)行測(cè)試：

1.當(dāng)根節(jié)點(diǎn)為紅時(shí)，返回false。

2.判斷一個(gè)節(jié)點(diǎn)和其父節(jié)點(diǎn)的顏色是否都為紅，若都為紅返回false。

3.以最左的一條路徑上的根節(jié)點(diǎn)數(shù)量為基準(zhǔn)，通過(guò)遞歸遍歷每一條路徑上的根節(jié)點(diǎn)的數(shù)量，當(dāng)每條路徑遍歷節(jié)點(diǎn)到空時(shí)，將兩者進(jìn)行比較，如果最終結(jié)果不相等則返回false。

    bool IsBalance()
    {
        if (_root && _root->_col == Red)
        {
            cout << "根節(jié)點(diǎn)不是黑色的" << endl;
            return false;
        }
        int banchmark = 0;
        //以最右邊一條路徑為基準(zhǔn)
        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 << "黑色根節(jié)點(diǎn)數(shù)目不相等" << endl;
                return false;
            }
            return true;
        }
        if (root->_col == Red && root->_parent->_col == Red)
        {
            cout << "出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)" << 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 << "根節(jié)點(diǎn)不是黑色的" << endl;
            return false;
        }
        int banchmark = 0;
        //以最右邊一條路徑為基準(zhǔn)
        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 << "黑色根節(jié)點(diǎn)數(shù)目不相等" << endl;
                return false;
            }
            return true;
        }
        if (root->_col == Red && root->_parent->_col == Red)
        {
            cout << "出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)" << 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;
            }
        }
    }
};

到此，關(guān)于“C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹如何實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！