高级数据结构与算法 | 红黑树（Red-Black Tree）
生活随笔
收集整理的這篇文章主要介紹了
高级数据结构与算法 | 红黑树（Red-Black Tree）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 紅黑樹
- 紅黑樹的概念
- 紅黑樹的性質
- 紅黑樹與AVL樹
- 紅黑樹的實現
- 紅黑樹的節點
- 紅黑樹的插入
- 紅黑樹的查找
- 紅黑樹的驗證
- 完整代碼
紅黑樹
紅黑樹的概念
紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是紅色或者黑色。 通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。
如下圖
紅黑樹的性質
根據這幾種性質，是如何保證每一個節點的高度差不超過二倍呢？我們可以直接設想一下極端情況
對于一個結點，到其葉子所經過的最短路徑全為黑節點，最長路徑為一黑一紅交錯的路徑。
在完全遵守上面所有的性質的情況下，最大的路徑差即為下圖，也就是二倍。
紅黑樹與AVL樹
在之前的博客中，我介紹了另外一種平衡二叉樹，AVL樹，他和紅黑樹又有什么不同呢？為什么在大部分庫里，如STL、Linux內核等大部分都采用的是紅黑樹呢？
首先就來分析他們的增刪查改的效率。
因為紅黑樹保證了最大的路徑差不超過二倍，所以其在最壞情況下，增刪查改的效率是O(2logN)
而AVL樹則因為多次單旋雙旋保證了高度平衡，其最大的高度差不超過2，所以他的效率一直都是保持在O(logN)左右。
從這里來看，AVL樹的效率比紅黑樹要高上不少，幾乎接近兩倍，但是因為其單位都是logN，這里的兩倍幾乎就可以忽略了。例如要查找十億個的數據（只考慮查找），最壞情況下，AVL樹要30次，而紅黑樹要60次，雖然差距是兩倍，但是這兩倍對于計算機來說幾乎已經可以忽略不計。并且，AVL樹的高度平衡是因為其通過大量的旋轉來完成的，所以對于經常發生刪除和插入的結構，紅黑樹的效率會更優，并且紅黑樹的實現比起AVL更加容易且易于控制，所以實際中使用紅黑樹更多。
這是之前看到的一張圖，可以從上圖看到，如果是比較查找時，此時紅黑樹略低于AVL樹，但如果是插入或者刪除，則稍微高于AVL，原因就是因為AVL需要維護其高度平衡的特性，所以進行更多的旋轉，導致效率降低。
紅黑樹的實現
關于二叉搜索樹的思路，以及旋轉的思路在前兩篇中已經寫過，這里就不多贅述
數據結構 ： 二叉搜索樹的原理以及實現（C++）
數據結構 ： AVL樹的原理以及實現（C++）
紅黑樹的節點
enum Color{BLACK,RED,};template<class T>struct RBTreeNode{typedef RBTreeNode<T> Node;RBTreeNode(const T& data = T(), const Color& color = RED) : _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}Node* _left;Node* _right;Node* _parent;T _data;Color _color;};紅黑樹的節點和二叉搜索樹差不多，只是多了一個顏色，在這里我為了代碼更加直觀所以用的是枚舉
紅黑樹的插入
插入分為兩個步驟
第一步驟之前幾個博客都講過了，這里就不多說，直接講第二步驟。
首先依據紅黑樹的特性，我們要決定新增節點的顏色。
如果新插入的結點為紅色，則有可能打破了不能有連續的紅結點這一規則，而如果插入的是黑色，則又破壞了每個路徑的黑節點數量相同這一規則。如果都會破壞的話，就需要選擇一個方便修復的，而不能有連續的紅結點這一規則，只需要進行一下顏色的變換或者旋轉，就可以解決這個問題，所以新增節點都為紅色。
接著來探討插入時的各種狀況。
情況1:插入節點的父節點為黑色
此時是最優情況，因為沒有破壞任何規則，所以此時無需任何處理。
情況2：插入節點的父節點為紅色，叔叔節點也為紅色，祖父為黑色
此時的處理方法也很簡單，因為出現了連續的紅色，所以只需要進行顏色的修正即可解決。
這里將父親和叔叔變黑，祖父變紅即可解決。同時，因為祖父之上可能還有其他節點，還需要從祖父的位置繼續向上調節。
情況3：孩子為紅，父親為紅，叔叔為黑或者不存在，祖父為黑。孩子與父親呈直線狀態
這里有兩種情況
解決的方法也不難，只需要旋轉+變色處理即可
和AVL樹一樣，因為父親和孩子呈直線狀態，所以只需要單旋即可。
如果父親是祖父的左孩子，孩子是父親的左孩子，此時祖父進行右單旋
如果父親是祖父的右孩子，孩子是父親的右孩子，此時祖父進行左單旋。
此時再將祖父變紅，父親變黑，即可完成處理
情況4：孩子為紅，父親為紅，叔叔為黑或者不存在，祖父為黑。孩子與父親呈折線狀態
這種情況與上面的類似，如果此時孩子與父親處理折線狀態，就需要雙旋 + 變色處理
如果父親是祖父的左孩子，孩子是父親的右孩子，父親此時進行左單旋
如果父親是祖父的右孩子，孩子是父親的左孩子，父親此時進行右單旋。
上圖進行左單旋
此時我們發現，這個狀態和情況3有點像，所以只需要交換父親和孩子，就可以轉換為情況3
接著再按照情況3再進行一次單旋處理即可。
旋轉的思路已經講過很多次了，這里就直接給代碼，如果想了解具體思路可以點擊上面AVL樹那一篇博客
//右旋 void RotateR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//如果subLR存在，則讓他的父節點指向parent。if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//兩種情況//如果parent為根節點，則讓subL成為新的根節點if (parent == _root){_root = subL;subL->_parent = nullptr;}//如果不是根節點，則改變subL與其祖父節點的指向關系else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;} }//左旋 void RotateL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;} }紅黑樹的查找
這里的查找和二叉搜索樹一樣，就不多說了
bool Find(const std::pair<K, V>& data) {//根據二叉搜索樹的性質，從根節點出發，比根節點大則查找右子樹，比根節點小則查找左子樹Node* cur = _root;while (cur){//比根節點大則查找右子樹if (data.first > cur->_data.first){cur = cur->_right;}//比根節點小則查找左子樹else if (data.first < cur->_data.first){cur = cur->_left;}//相同則返回else{return true;}}//遍歷完則說明查找不到，返回falsereturn false; }紅黑樹的驗證
要驗證是否為紅黑樹，只需要判斷其是否滿足這三個性質。
1. 根節點必須為黑節點
2. 不存在連續的紅結點
3. 從某一節點出發到其所有的葉子節點，其中經過的黑色節點數量相等
完整代碼
#pragma once #include<iostream>namespace lee {enum Color{BLACK,RED,};template<class K, class V>struct RBTreeNode{typedef RBTreeNode<K, V> Node;RBTreeNode(const std::pair<K, V>& data = std::pair<K, V>(), const Color& color = RED): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}Node* _left;Node* _right;Node* _parent;std::pair<K, V> _data;Color _color;};template<class K, class V>class RBTree{public:typedef RBTreeNode<K, V> Node;RBTree(): _root(nullptr){}~RBTree(){destory(_root);}void _InOrderTravel(Node* root) const{if (root == nullptr)return;_InOrderTravel(root->_left);std::cout << root->_data.first << ':' << root->_data.second << std::endl;_InOrderTravel(root->_right);}void InOrderTravel() const{_InOrderTravel(_root);}void destory(Node*& root){Node* node = root;if (!root)return;destory(node->_left);destory(node->_right);delete node;node = nullptr;}//右旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//如果subLR存在，則讓他的父節點指向parent。if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//兩種情況//如果parent為根節點，則讓subL成為新的根節點if (parent == _root){_root = subL;subL->_parent = nullptr;}//如果不是根節點，則改變subL與其祖父節點的指向關系else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}bool Find(const std::pair<K, V>& data){//根據二叉搜索樹的性質，從根節點出發，比根節點大則查找右子樹，比根節點小則查找左子樹Node* cur = _root;while (cur){//比根節點大則查找右子樹if (data.first > cur->_data.first){cur = cur->_right;}//比根節點小則查找左子樹else if (data.first < cur->_data.first){cur = cur->_left;}//相同則返回else{return true;}}//遍歷完則說明查找不到，返回falsereturn false;}bool Insert(const std::pair<K, V>& data){//按照二叉搜索樹的規則先找到位置//創建根節點if (_root == nullptr){_root = new Node(data, BLACK);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (data.first > cur->_data.first){parent = cur;cur = cur->_right;}else if (data.first < cur->_data.first){parent = cur;cur = cur->_left;}else{return false;}}//新插入節點為紅色cur = new Node(data, RED);//保存插入的結點，因為后面會往上更新紅黑樹，所以cur可能會變化。Node* newNode = cur;//判斷插入位置if (cur->_data.first > parent->_data.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新紅黑樹，如果父節點的顏色為黑，則說明滿足條件，不需要處理，如果為紅，則說明不滿足，需要處理。while (parent && parent->_color == RED){Node* ppNode = parent->_parent;//如果父節點為祖父的左子樹if (ppNode->_left == parent){//此時判斷叔叔節點的狀態，紅黑樹狀態取決于叔叔Node* uncle = ppNode->_right;//第一種情況，如果叔叔節點存在且為紅，則直接把父親和叔叔變黑，祖父節點邊紅即可。然后再從祖父的位置繼續往上調整if (uncle && uncle->_color == RED){//變色uncle->_color = parent->_color = BLACK;ppNode->_color = RED;//繼續往上cur = ppNode;parent = cur->_parent;}/*叔叔節點為黑或者不存在，此時有兩種情況情況二：cur為父節點的左子樹，即直線狀態。情況三：cur為父節點的右子樹，即折線狀態。情況二單旋一次后更改顏色即可完成對于情況三，如果將其進行一次旋轉后再稍微處理，就可以轉換成情況二*/else{//因為這里的雙旋和AVL不一樣，可以不用處理平衡因子，所以如果為折線則先旋轉處理后，將其轉換為直線處理即可。//第三種情況，折線狀態，轉換為直線狀態處理if (parent->_right == cur){RotateL(parent);//單旋后再交換節點，即可變成直線狀態。std::swap(parent, cur);}//處理第二種狀態RotateR(ppNode);parent->_color = BLACK;ppNode->_color = RED;//處理完成break;}}//如果父親為祖父的右子樹else{//此時叔叔為左子樹。Node* uncle = ppNode->_left;if (uncle && uncle->_color == RED){uncle->_color = parent->_color = BLACK;ppNode->_color = RED;cur = ppNode;parent = cur->_parent;}else{if (parent->_left == cur){RotateR(parent);std::swap(cur, parent);}RotateL(ppNode);ppNode->_color = RED;parent->_color = BLACK;break;}}}//為了防止不小心把根節點改為紅色，最后手動改為黑色即可_root->_color = BLACK;return true;}/*判斷是否為紅黑樹，就是判斷其是否滿足紅黑樹的特性特性： 1.根節點必須為黑節點2.不存在連續的紅結點3.從某一節點出發到其所有的葉子節點，其中經過的黑色節點數量相等*/bool IsRBTree(){if (_root == nullptr){//空樹也是紅黑樹return true;}//違反性質1if (_root->_color != BLACK){return false;}//獲取從根節點出發的任意一條子路徑的黑色節點數，這里選取最左子樹。Node* cur = _root;size_t blackCount = 0;size_t count = 0;while (cur){if (cur->_color == BLACK){blackCount++;}cur = cur->_left;}//遞歸判斷其他路徑的黑色節點數return _IsRBTree(_root, count, blackCount);}bool _IsRBTree(Node* root, size_t count, const size_t blackCount){//此時說明已經走到葉子節點，判斷黑色節點數是否相等，不相等則違反性質3if (root == nullptr){if (count != blackCount){return false;}else{return true;}}//如果沒走完，就接著判斷其他情況//判斷性質2，如果存在連續的紅結點，則返回錯誤Node* parent = root->_parent;if (parent && root->_color == RED && parent->_color == RED){return false;}//如果當前節點為黑色，則記錄if (root->_color == BLACK){count++;}//接著遞歸判斷當前節點的所有路徑return _IsRBTree(root->_left, count, blackCount) && _IsRBTree(root->_right, count, blackCount);}private:Node* _root;}; }總結
以上是生活随笔為你收集整理的高级数据结构与算法 | 红黑树（Red-Black Tree）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 计算机网络 | IP协议相关技术与网络总
- 下一篇： C++ STL : 模拟实现STL中的关