做網(wǎng)站要怎么備案網(wǎng)站建設(shè)是什么
前言：本篇文章我們繼續(xù)來(lái)分享C++中的另一個(gè)復(fù)雜數(shù)據(jù)結(jié)構(gòu)——紅黑樹。
目錄
一.紅黑樹概念
二.紅黑樹性質(zhì)
三.紅黑樹實(shí)現(xiàn)
1.基本框架
2.插入
3.判斷平衡
?四.完整代碼
總結(jié)
一.紅黑樹概念
紅黑樹，是一種二叉搜索樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。 通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會(huì)比其他路徑長(zhǎng)出兩倍，因而是接近平衡的。
二.紅黑樹性質(zhì)
-
每個(gè)結(jié)點(diǎn)不是紅色就是黑色
-
根節(jié)點(diǎn)是黑色的
-
如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子結(jié)點(diǎn)是黑色的（不存在連續(xù)的紅色節(jié)點(diǎn)）?
-
對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)（每條路徑都存在相同數(shù)量的黑色節(jié)點(diǎn)）?
-
每個(gè)葉子結(jié)點(diǎn)都是黑色的(此處的葉子結(jié)點(diǎn)指的是空結(jié)點(diǎn)NULL)
如何理解紅黑樹最長(zhǎng)路徑不超過(guò)最短路徑的二倍呢？？？
- ?從性質(zhì)能夠看出，紅黑樹每一條路徑上，都有相同數(shù)量的黑色節(jié)點(diǎn)。
- 紅黑樹每條路徑上可以存在連續(xù)的黑色節(jié)點(diǎn)，但不能存在連續(xù)的紅色節(jié)點(diǎn)。
- 所以最短路徑即為全是黑色節(jié)點(diǎn)的路徑。
- 最長(zhǎng)路徑則為一黑一紅相間的路徑。
三.紅黑樹實(shí)現(xiàn)
1.基本框架
紅黑樹與AVL樹相比，多了節(jié)點(diǎn)顏色這一信息，為了實(shí)現(xiàn)這一信息，我們使用枚舉：
enum Colour
{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;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED){}
};
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;size_t _size = 0;
};同時(shí)我們多創(chuàng)建一個(gè)_size成員變量，用于記錄節(jié)點(diǎn)數(shù)量。?
2.插入
紅黑樹插入的基本步驟與二叉搜索樹和AVL樹一樣，都是按照左子節(jié)點(diǎn)比根節(jié)點(diǎn)小，右子節(jié)點(diǎn)比根節(jié)點(diǎn)大的規(guī)則，唯一不同的是，紅黑樹的插入要考慮其性質(zhì)。其中最值得注意的性質(zhì)為：
- 不存在連續(xù)的紅節(jié)點(diǎn)
- 每條路徑上的黑節(jié)點(diǎn)數(shù)相等
?其中能夠看出，第二條才是最關(guān)鍵的，因此我們每次新插入節(jié)點(diǎn)時(shí)，必須插入紅節(jié)點(diǎn)。
此時(shí)我們會(huì)面臨兩種情況：
- 父節(jié)點(diǎn)為黑色，插入即結(jié)束，無(wú)需調(diào)整。
- 父節(jié)點(diǎn)為紅色，不滿足上述性質(zhì)1，需要調(diào)整。
下面我們來(lái)看特殊情況：
父親為紅節(jié)點(diǎn)，那么只有將父節(jié)點(diǎn)變?yōu)楹谏?jié)點(diǎn)，才能夠滿足性質(zhì)。
但是如果父親變?yōu)楹诠?jié)點(diǎn)，就說(shuō)明該路徑上同樣多出一個(gè)黑節(jié)點(diǎn)，而唯一的處理手段，就是讓父親的父親，也就是爺爺節(jié)點(diǎn)，變?yōu)榧t色節(jié)點(diǎn)。
此時(shí)又存在問題，那就是關(guān)于父親的兄弟節(jié)點(diǎn)，也就是叔叔節(jié)點(diǎn)，那么叔叔節(jié)點(diǎn)存在三種情況：
- 叔叔節(jié)點(diǎn)同樣為紅色。
- 叔叔節(jié)點(diǎn)不存在。
- 叔叔節(jié)點(diǎn)為黑色。
如果叔叔節(jié)點(diǎn)為紅色，為了滿足各路徑黑節(jié)點(diǎn)數(shù)量相同，叔叔節(jié)點(diǎn)則需要和父節(jié)點(diǎn)一起變?yōu)楹谏?/span>。
如果叔叔節(jié)點(diǎn)不存在，為了滿足性質(zhì)，需要將該子樹從爺爺節(jié)點(diǎn)的位置進(jìn)行旋轉(zhuǎn)。
如果叔叔節(jié)點(diǎn)為黑色，而父節(jié)點(diǎn)為紅色，如果還要滿足性質(zhì)，說(shuō)明子節(jié)點(diǎn)原本應(yīng)為黑色，是因?yàn)榻?jīng)過(guò)了上述的調(diào)整而作為爺爺節(jié)點(diǎn)變成了紅色。此時(shí)我們仍需從爺爺節(jié)點(diǎn)的位置進(jìn)行旋轉(zhuǎn)。
分析完上述完整情況之后，還有關(guān)于新插入節(jié)點(diǎn)的兩種情況：
- 父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左子節(jié)點(diǎn)，同時(shí)新增節(jié)點(diǎn)也為父節(jié)點(diǎn)的左子節(jié)點(diǎn)，為一條斜線。
- 父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左子節(jié)點(diǎn)，但是新增節(jié)點(diǎn)也為父節(jié)點(diǎn)的有子節(jié)點(diǎn)，為一條折線。
斜線情況下，我們?cè)谛枰D(zhuǎn)時(shí)只需單旋即可；
而當(dāng)為折線時(shí)，就需要進(jìn)行雙旋，先變?yōu)樾本€，在進(jìn)行調(diào)整。
同時(shí)父節(jié)點(diǎn)也需要考慮是爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)還是右節(jié)點(diǎn)兩種情況，彼此的規(guī)則相反。
按照上邊的步驟，我們能夠得出代碼情況：
//插入bool Insert(const 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;//新增節(jié)點(diǎn)給紅色if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//parent是黑色就結(jié)束while (parent && parent->_col == RED){Node* Grandfather = parent->_parent;if (parent == Grandfather->_left){Node* uncle = Grandfather->_right;if (uncle && uncle->_col == RED)//叔叔存在且為紅，直接變色{parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;//繼續(xù)往上處理cur = Grandfather;parent = Grandfather->_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;}}else{Node* uncle = Grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;cur = Grandfather;parent = Grandfather->_parent;}else{if (cur == parent->_right){RotateL(Grandfather);Grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(Grandfather);cur->_col = BLACK;Grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}?需要考慮的情況確實(shí)很多，但如果自己畫圖認(rèn)真分析，理解起來(lái)還是易如反掌的。
3.判斷平衡
判斷紅黑樹的平衡，我們自然要從其性質(zhì)入手：
- 首先就是判斷根節(jié)點(diǎn)是否為黑色。
- 其次容易判斷的是是否有兩個(gè)相鄰的紅色節(jié)點(diǎn)，注意這里我們不去判斷一個(gè)節(jié)點(diǎn)與其子節(jié)點(diǎn)，反而去判斷一個(gè)節(jié)點(diǎn)與其父節(jié)點(diǎn)。因?yàn)?span style="color:#ff9900;">如果判斷子節(jié)點(diǎn)，則可能需要判斷兩次，而父節(jié)點(diǎn)則只需判斷一次。
- 最后就是判斷所有路徑上的黑節(jié)點(diǎn)數(shù)量是否相同。
其中前兩種都比較容易想到代碼方式，最重要的是如何比較黑節(jié)點(diǎn)的數(shù)量。
我們可以通過(guò)增加參數(shù)的方式。來(lái)記錄到達(dá)每個(gè)節(jié)點(diǎn)位置時(shí)，該路徑上出現(xiàn)過(guò)的黑節(jié)點(diǎn)的數(shù)量。而如何進(jìn)行比較，因?yàn)槊織l路徑上黑節(jié)點(diǎn)的數(shù)量都必須相同，所以我們直接記錄一下最左邊的一條路徑上黑節(jié)點(diǎn)的數(shù)量，然后求出一條路徑上的黑節(jié)點(diǎn)數(shù)之后，就進(jìn)行比較即可。
//判斷平衡bool IsBalance(){if (_root->_col == RED)return false;int refnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refnum++;cur = cur->_left;}return Check(_root, 0, refnum);}bool Check(Node* root, int BlackNum,const int refnum){if (root == nullptr){if (refnum != BlackNum){cout << "存在黑色節(jié)點(diǎn)個(gè)數(shù)不相等" << endl;return false;}cout << BlackNum << endl;return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "->存在連續(xù)的紅色節(jié)點(diǎn)" << endl;return false;}if (root->_col == BLACK)BlackNum++;return Check(root->_left, BlackNum,refnum)&& Check(root->_right, BlackNum,refnum);}?四.完整代碼
enum Colour
{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;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED){}
};
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://插入bool Insert(const 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;//新增節(jié)點(diǎn)給紅色if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//parent是黑色就結(jié)束while (parent && parent->_col == RED){Node* Grandfather = parent->_parent;if (parent == Grandfather->_left){Node* uncle = Grandfather->_right;if (uncle && uncle->_col == RED)//叔叔存在且為紅，直接變色{parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;//繼續(xù)往上處理cur = Grandfather;parent = Grandfather->_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;}}else{Node* uncle = Grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;cur = Grandfather;parent = Grandfather->_parent;}else{if (cur == parent->_right){RotateL(Grandfather);Grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(Grandfather);cur->_col = BLACK;Grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}//右單旋void RotateR(Node* parent){//定義左子節(jié)點(diǎn)Node* subL = parent->_left;//定義左子節(jié)點(diǎn)的右子節(jié)點(diǎn)Node* subLR = subL->_right;//調(diào)整parent->_left = subLR;//判空if (subLR)subLR->_parent = parent;//調(diào)整subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root)//判斷是否為根{_root = subL;_root->_parent = nullptr;}else//不是根節(jié)點(diǎn)，調(diào)整父節(jié)點(diǎn)指向{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}}//左單旋void RotateL(Node* parent){//定義右子節(jié)點(diǎn)Node* subR = parent->_right;//定義右子節(jié)點(diǎn)的左子節(jié)點(diǎn)Node* subRL = subR->_left;//調(diào)整parent->_right = subRL;//判空if (subRL)subRL->_parent = parent;//調(diào)整subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root)//判斷是否為根{_root = subR;_root->_parent = nullptr;}else//不是根節(jié)點(diǎn)，調(diào)整父節(jié)點(diǎn)指向{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}}//遍歷void InOrder(){inOrder(_root);cout << endl;}void inOrder(const Node* root){if (root == nullptr){return;}inOrder(root->_left);cout << root->_kv.first << ':' << root->_kv.second << endl;inOrder(root->_right);}//判斷平衡bool IsBalance(){if (_root->_col == RED)return false;int refnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refnum++;cur = cur->_left;}return Check(_root, 0, refnum);}bool Check(Node* root, int BlackNum,const int refnum){if (root == nullptr){if (refnum != BlackNum){cout << "存在黑色節(jié)點(diǎn)個(gè)數(shù)不相等" << endl;return false;}cout << BlackNum << endl;return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "->存在連續(xù)的紅色節(jié)點(diǎn)" << endl;return false;}if (root->_col == BLACK)BlackNum++;return Check(root->_left, BlackNum,refnum)&& Check(root->_right, BlackNum,refnum);}
private:Node* _root = nullptr;//size_t _size = 0;
};總結(jié)
關(guān)于紅黑樹的知識(shí)就分享這么多，喜歡本篇文章記得一鍵三連，我們下期再見！