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