?
文章目錄
一、引言
二、紅黑樹的概念與性質(zhì)
2、1 紅黑樹的概念
2、2 紅黑樹的性質(zhì)
三、紅黑樹的定義與實(shí)現(xiàn)
3、1 紅黑樹的定義
3、2 插入新節(jié)點(diǎn)
3、2、1 默認(rèn)插入紅色節(jié)點(diǎn)
3、3?插入情況分類
3、3、1 情況一（根據(jù)顏色向上調(diào)整）
3、3、2 情況二（單次旋轉(zhuǎn)+變色）
3、3、3 情況三（兩次旋轉(zhuǎn)+變色）
3、4 插入的完整代碼實(shí)現(xiàn)
四、紅黑樹的檢驗(yàn)
五、性能分析
六、總結(jié)
???♂??作者：@Ggggggtm????♂?
???專欄：C++、數(shù)據(jù)結(jié)構(gòu)???
???標(biāo)題：紅黑樹??
????寄語：與其忙著訴苦，不如低頭趕路，奮路前行，終將遇到一番好風(fēng)景????
一、引言
? 紅黑樹是一種自平衡的二叉搜索樹，它在計(jì)算機(jī)科學(xué)中扮演著重要的角色。由于其高效的插入、刪除和查找操作，紅黑樹被廣泛應(yīng)用于各種數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)中。紅黑樹的設(shè)計(jì)旨在保持樹的平衡，從而確保各種操作的時(shí)間復(fù)雜度能夠保持在較低的范圍內(nèi)。?
?當(dāng)我們學(xué)完?AVL樹?后，我們再學(xué)紅黑樹相對來說就會簡單一點(diǎn)。紅黑樹可以看成是AVL樹的升級版。
? 本篇文章會對紅黑樹的實(shí)現(xiàn)原理進(jìn)行詳解。同時(shí)還會給出紅黑樹的C++實(shí)現(xiàn)代碼。希望本篇文章會對你有所幫助。
二、紅黑樹的概念與性質(zhì)
2、1 紅黑樹的概念
? 紅黑樹，是一種二叉搜索樹，但在每個結(jié)點(diǎn)上增加一個存儲位表示結(jié)點(diǎn)的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的。
2、2 紅黑樹的性質(zhì)
?紅黑樹也是一顆很特殊的樹，它具有如下的性質(zhì)：
- 每個結(jié)點(diǎn)不是紅色就是黑色。
- 根節(jié)點(diǎn)是黑色的 。
- 如果一個節(jié)點(diǎn)是紅色的，則它的兩個孩子結(jié)點(diǎn)是黑色的（不能有兩個連續(xù)的紅色節(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)的數(shù)量為該紅黑樹的路徑數(shù)量，且每條路徑的黑色節(jié)點(diǎn)數(shù)量相同）。
- 每個葉子結(jié)點(diǎn)都是黑色的(此處的葉子結(jié)點(diǎn)指的是空結(jié)點(diǎn))。
? 這里就有一個疑問了：為什么滿足上面的性質(zhì)，紅黑樹就能保證：其最長路徑中節(jié)點(diǎn)個數(shù)不會超過最短路徑節(jié)點(diǎn)個數(shù)的兩倍？? 根據(jù)上述的性質(zhì)三我們知道，一個路徑最短的情況下就是所有節(jié)點(diǎn)的顏色為黑色。同時(shí)最長的情況是一紅一黑交叉出現(xiàn)。但是我們不要忘記了性質(zhì)四每條路徑的黑色節(jié)點(diǎn)數(shù)量相同，那么最長的路徑就是最短的路徑兩倍了，并沒有超過兩倍。
? 通過以上的紅黑樹特性，我們可以保證紅黑樹在進(jìn)行插入、刪除等操作時(shí)，始終能夠保持樹的平衡性，從而保證了各種操作的時(shí)間復(fù)雜度始終在對數(shù)級別內(nèi)。在接下來的章節(jié)中，我們將深入探討紅黑樹的插入操作的實(shí)現(xiàn)細(xì)節(jié)，以及時(shí)間復(fù)雜度的分析，進(jìn)一步理解紅黑樹的原理和實(shí)現(xiàn)。?
三、紅黑樹的定義與實(shí)現(xiàn)
3、1 紅黑樹的定義
? 紅黑樹也是一種二叉搜索樹，它的每個節(jié)點(diǎn)包含一個關(guān)鍵字（鍵值對）、左右孩子指針和父結(jié)點(diǎn)指針。每個節(jié)點(diǎn)還包含一個記錄顏色的變量，該變量用來表示該節(jié)點(diǎn)是紅色節(jié)點(diǎn)還是黑色節(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) {} };? 表示顏色我們采用枚舉的方式，以便整篇的代碼比較整潔且易于理解。
3、2 插入新節(jié)點(diǎn)
? 紅黑樹的插入操作是通過對二叉搜索樹的基本插入操作結(jié)合顏色調(diào)整和旋轉(zhuǎn)操作來實(shí)現(xiàn)的。插入算法的概述如下：
- 首先，將插入的節(jié)點(diǎn)按照普通的二叉搜索樹插入操作，將其放置在合適的位置上。
- 將插入節(jié)點(diǎn)標(biāo)記為紅色，這樣不會違反紅黑樹的特性。
- 檢查插入節(jié)點(diǎn)的父節(jié)點(diǎn)及其祖父節(jié)點(diǎn)、叔叔節(jié)點(diǎn)等情況，根據(jù)不同的情況進(jìn)行顏色調(diào)整和旋轉(zhuǎn)操作，以保持紅黑樹的平衡性和特性。
- 最后，確保根節(jié)點(diǎn)是黑色的，以滿足紅黑樹的根節(jié)點(diǎn)特性。
? 插入操作的核心是對樹進(jìn)行顏色調(diào)整和旋轉(zhuǎn)，以確保插入后仍然滿足紅黑樹的特性。具體的左旋和右旋操作將在后續(xù)小節(jié)中詳細(xì)解釋，而插入修正過程則會對顏色調(diào)整的各種情況進(jìn)行逐步解析。通過這些操作，紅黑樹能夠在插入新節(jié)點(diǎn)時(shí)保持平衡，從而保證了各種操作的高效性能。
? 接下來，我們將逐步深入探討插入操作的具體細(xì)節(jié)，以便更好地理解紅黑樹的實(shí)現(xiàn)原理。
3、2、1 默認(rèn)插入紅色節(jié)點(diǎn)
? 在具體的學(xué)習(xí)插入操作之前，我們應(yīng)該想一下新插入的節(jié)點(diǎn)是插入紅色節(jié)點(diǎn)呢還是插入黑色節(jié)點(diǎn)呢？我們不妨自己先結(jié)合著紅黑樹的性質(zhì)思考一下。
? 試想，我們新插入的節(jié)點(diǎn)是黑色節(jié)點(diǎn)，那么就違背了上述的性質(zhì)四。那么影響的就是整棵樹。大概率需要很復(fù)雜的旋轉(zhuǎn)和調(diào)整才能恢復(fù)。假如新插入的節(jié)點(diǎn)是紅色節(jié)點(diǎn)，新插入的節(jié)點(diǎn)的父節(jié)點(diǎn)可能為黑色，也可能為紅色。當(dāng)父節(jié)點(diǎn)為黑色時(shí)，并無影響。當(dāng)父節(jié)點(diǎn)為紅色時(shí)，違背了上述的性質(zhì)三，影響的只是改父節(jié)點(diǎn)所在的子樹。
? 將新插入的節(jié)點(diǎn)設(shè)置為紅色有兩個主要原因：
保持黑色高度平衡：紅黑樹要求在任意路徑上的黑色節(jié)點(diǎn)數(shù)量是相同的，這被稱為黑色高度平衡。通過將新插入的節(jié)點(diǎn)設(shè)置為紅色，可以確保其不會破壞現(xiàn)有的黑色高度平衡。
簡化平衡調(diào)整：當(dāng)插入新節(jié)點(diǎn)后，可能會導(dǎo)致紅黑樹的性質(zhì)被破壞，需要進(jìn)行平衡調(diào)整來恢復(fù)性質(zhì)。將新節(jié)點(diǎn)設(shè)置為紅色可以簡化平衡調(diào)整的過程，因?yàn)榧t色節(jié)點(diǎn)的插入更容易適應(yīng)紅黑樹的性質(zhì)。如果將新節(jié)點(diǎn)設(shè)置為黑色，則可能需要對樹進(jìn)行更多的旋轉(zhuǎn)和重新著色操作。
? 總之，將新插入的節(jié)點(diǎn)設(shè)置為紅色有助于保持紅黑樹的平衡性和減少平衡調(diào)整的復(fù)雜性。
3、3?插入情況分類
? 我們先看如下情況，在值為1的黑色節(jié)點(diǎn)左側(cè)插入一個新節(jié)點(diǎn)：?
? 插入完之后，并不影響改紅黑樹的平衡，且滿足紅黑樹的性質(zhì)。
? 我們再看另一種情況，在值為22的紅色節(jié)點(diǎn)左側(cè)插入一個新節(jié)點(diǎn)：
? 我們發(fā)現(xiàn)，此時(shí)新插入的節(jié)點(diǎn)影響到了紅黑樹的平衡。那要是插入到值為22的紅色節(jié)點(diǎn)右側(cè)呢？或者插入到值為6的節(jié)點(diǎn)，又或者插入到值為27的節(jié)點(diǎn)，都需要我們進(jìn)行調(diào)整。由于情況太多，所以對需要進(jìn)行調(diào)整的情況進(jìn)行了分類。
? 接下來對需要調(diào)整的各種情況分類進(jìn)行詳解。
3、3、1 情況一（根據(jù)顏色向上調(diào)整）
? 具體需要調(diào)整的狀態(tài)如下圖（抽象圖）：
? 注：cur為當(dāng)前所在位置的節(jié)點(diǎn)；p（parent）為cur的父節(jié)點(diǎn)；u（uncle）為cur的叔叔節(jié)點(diǎn)；g（grandfather）為cur的祖宗節(jié)點(diǎn)。
? 我們發(fā)現(xiàn)上述的情況cur為紅，p為紅，g為黑，u存在且為紅，違背了性質(zhì)三。那怎么進(jìn)行調(diào)整呢？調(diào)整的方法很簡單：將p,u改為黑，g改為紅，然后把g當(dāng)成cur，繼續(xù)向上調(diào)整。具體如下圖：
? 如果g是根節(jié)點(diǎn)，調(diào)整完之后，需要將g改變?yōu)楹谏?。如果g是子樹，g一定有雙節(jié)點(diǎn)，且如果g的雙親是紅色，需要繼續(xù)重復(fù)此過程向上調(diào)整。?具體如下圖:
? 上圖中的cur可能是新增節(jié)點(diǎn)，也可能是更新后的節(jié)點(diǎn)，具體如下圖：
? 當(dāng)然，新增的紅色節(jié)點(diǎn)可以是任意孩子位置，?只要是滿足cur為紅，p為紅，g為黑，u存在且為紅，就劃分到這一類。?
3、3、2 情況二（單次旋轉(zhuǎn)+變色）
? 我們知道，只有p（父節(jié)點(diǎn)）是紅色時(shí)，才需要進(jìn)行調(diào)整。但是u（叔叔節(jié)點(diǎn)）不一定為紅色，也有可能為黑色，甚至u（叔叔節(jié)點(diǎn)）可能就不存在。具體如下圖：
? u的情況有兩種，不同情況對應(yīng)的情況說明：
- 如果u節(jié)點(diǎn)不存在，則cur一定是新插入節(jié)點(diǎn)，因?yàn)槿绻鹀ur不是新插入節(jié)點(diǎn)，則cur和p一定有一個節(jié)點(diǎn)的顏色是黑色，就不滿足性質(zhì)4：每條路徑黑色節(jié)點(diǎn)個數(shù)相同.
- 如果u節(jié)點(diǎn)存在，則其一定是黑色的，那么cur節(jié)點(diǎn)原來的顏色一定是黑色的，現(xiàn)在看到其是紅色的原因是因?yàn)閏ur的子樹在調(diào)整的過程中將cur節(jié)點(diǎn)的顏色由黑色改成紅色。
? 雖然u的情況有兩種，但是處理方法是一樣的。這時(shí)，只通過顏色調(diào)整是不行了。具體的調(diào)整方法是：?p為g的左孩子，cur為p的左孩子，則進(jìn)行對g進(jìn)行右單旋轉(zhuǎn)；相反， p為g的右孩子，cur為p的右孩子，則對g進(jìn)行進(jìn)行左單旋轉(zhuǎn)。p、g變色--p變黑，g變紅。具體如下圖：
3、3、3 情況三（兩次旋轉(zhuǎn)+變色）
? 當(dāng)u（叔叔節(jié)點(diǎn)）為黑色或者不存在時(shí)，cur的位置也是影響旋轉(zhuǎn)的關(guān)鍵。我們看如下情況：
? 我們發(fā)現(xiàn)直接對g（祖宗節(jié)點(diǎn)）進(jìn)行旋轉(zhuǎn)并不能很好的解決問題。那能不能先對p（父親節(jié)點(diǎn)）進(jìn)行旋轉(zhuǎn)呢？具體調(diào)整方法：p為g的左孩子，cur為p的右孩子，則針對p做左單旋轉(zhuǎn)；相反，p為g的右孩子，cur為p的左孩子，則針對p做右單旋轉(zhuǎn)。則轉(zhuǎn)換成了情況2。對p旋轉(zhuǎn)完后，具體情況如下圖：
? 那我們再進(jìn)行針對情況二的旋轉(zhuǎn)和變色不就完成了嗎！?。?
3、4 插入的完整代碼實(shí)現(xiàn)
? 當(dāng)我們理解了上述的插入和調(diào)整思路后，我們來看一下代碼的實(shí)現(xiàn)：
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; if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfater = parent->_parent; assert(grandfater); assert(grandfater->_col == BLACK); // 關(guān)鍵看叔叔 if (parent == grandfater->_left) { Node* uncle = grandfater->_right; // 情況一 : uncle存在且為紅，變色+繼續(xù)往上處理 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfater->_col = RED; // 繼續(xù)往上處理 cur = grandfater; parent = cur->_parent; }// 情況二+三：uncle不存在 + 存在且為黑 else { // 情況二：右單旋+變色 // g // p u // c if (cur == parent->_left) { RotateR(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // 情況三：左右單旋+變色 // g // p u // c RotateL(parent); RotateR(grandfater); cur->_col = BLACK; grandfater->_col = RED; } break; } } else // (parent == grandfater->_right) { Node* uncle = grandfater->_left; // 情況一 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfater->_col = RED; // 繼續(xù)往上處理 cur = grandfater; parent = cur->_parent; } else { // 情況二：左單旋+變色 // g // u p // c if (cur == parent->_right) { RotateL(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // 情況三：右左單旋+變色 // g // u p // c RotateR(parent); RotateL(grandfater); cur->_col = BLACK; grandfater->_col = RED; } break; } } } _root->_col = BLACK; return true; }
四、紅黑樹的檢驗(yàn)
? 當(dāng)我們寫完插入時(shí)，怎么判斷該樹是否符合紅黑樹呢？只是中序打印肯定是不夠的，因?yàn)?strong>中序打印只能說明該樹是二叉搜索樹。那怎么辦呢？
? 判斷最長路徑是否不大于最短路徑長度的二倍行不行呢？好像也并不行。為什么呢？那要是還有連續(xù)的紅節(jié)點(diǎn)呢？又或者每條路徑的黑色節(jié)點(diǎn)的數(shù)量不同呢？
? 我們發(fā)現(xiàn)，當(dāng)滿足性質(zhì)三和性質(zhì)四時(shí)，就會滿足最長路徑是否不大于最短路徑長度的二倍。同時(shí)再判斷一下根節(jié)點(diǎn)的顏色就行，具體代碼如下：
public: void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == RED) { cout << "根節(jié)點(diǎn)不是黑色" << endl; return false; } // 黑色節(jié)點(diǎn)數(shù)量基準(zhǔn)值 int benchmark = 0; /*Node* cur = _root; while (cur) { if (cur->_col == BLACK) ++benchmark; cur = cur->_left; }*/ return PrevCheck(_root, 0, benchmark); } private: bool PrevCheck(Node* root, int blackNum, int& benchmark) { if (root == nullptr) { //cout << blackNum << endl; //return; if (benchmark == 0) { benchmark = blackNum; return true; } if (blackNum != benchmark) { cout << "某條黑色節(jié)點(diǎn)的數(shù)量不相等" << endl; return false; } else { return true; } } if (root->_col == BLACK) { ++blackNum; } if (root->_col == RED && root->_parent->_col == RED) { cout << "存在連續(xù)的紅色節(jié)點(diǎn)" << endl; return false; } return PrevCheck(root->_left, blackNum, benchmark) && PrevCheck(root->_right, blackNum, benchmark); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); }
五、性能分析
? 紅黑樹的插入操作的平均時(shí)間復(fù)雜度是O(log n)，其中n是樹中節(jié)點(diǎn)的數(shù)量。這是因?yàn)榧t黑樹的插入操作涉及到一系列的旋轉(zhuǎn)和修正操作，但這些操作都是局部的，不會導(dǎo)致整個樹的高度增加太多。
? 需要注意的是，雖然單次插入操作的時(shí)間復(fù)雜度是O(log n)，但在一系列插入操作后，為了保持紅黑樹的平衡性，可能需要進(jìn)行多次的旋轉(zhuǎn)和修正操作。但由于這些操作的時(shí)間復(fù)雜度都是常數(shù)級別的，不會隨著插入操作的增加而顯著增加，所以整體插入操作的平均時(shí)間復(fù)雜度仍然是O(log n)。
? 紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的時(shí)間復(fù)雜度都是 O(log n) ，紅黑樹不追求絕對平衡，其只需保證最長路徑不超過最短路徑的2倍，相對而言，降低了插入和旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)，? AVL樹是另一種自平衡二叉搜索樹，與紅黑樹相比，AVL樹要求更為嚴(yán)格的平衡性，每個節(jié)點(diǎn)的左子樹和右子樹的高度差（平衡因子）不超過1。這使得AVL樹在查找操作上更快，但插入和刪除操作可能需要更多的旋轉(zhuǎn)。
六、總結(jié)
? 紅黑樹作為一種自平衡二叉搜索樹，具有良好的平衡性質(zhì)和高效的插入、刪除、查找等操作，被廣泛應(yīng)用于各種數(shù)據(jù)結(jié)構(gòu)和算法領(lǐng)域。通過合理的旋轉(zhuǎn)操作和修正過程，紅黑樹能夠保持樹的平衡，從而保證了操作的時(shí)間復(fù)雜度在可接受的范圍內(nèi)。
? 在本文中，我們深入探討了紅黑樹的原理和實(shí)現(xiàn)細(xì)節(jié)。從基本概念開始，我們介紹了紅黑樹的定義、特性，然后詳細(xì)講解了插入操作的算法和旋轉(zhuǎn)操作。接著，我們討論了刪除操作的實(shí)現(xiàn)和修正過程。通過分析插入和刪除操作的時(shí)間復(fù)雜度，我們得出了紅黑樹在各種操作下的高效性能。文章來源：http://www.zghlxwxcb.cn/news/detail-635456.html
? 總的來說，紅黑樹作為一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，在算法和計(jì)算機(jī)科學(xué)領(lǐng)域中具有重要地位。通過深入學(xué)習(xí)和理解紅黑樹的原理和實(shí)現(xiàn)，讀者不僅可以拓展自己的數(shù)據(jù)結(jié)構(gòu)知識，還能夠?yàn)榻鉀Q實(shí)際問題提供有力的工具和思路。隨著計(jì)算機(jī)科學(xué)的不斷發(fā)展，紅黑樹及其相關(guān)的優(yōu)化和擴(kuò)展將繼續(xù)在各個領(lǐng)域發(fā)揮重要作用。文章來源地址http://www.zghlxwxcb.cn/news/detail-635456.html
到了這里，關(guān)于【C++】紅黑樹的原理與實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu) - C++] 紅黑樹RBTree](https://imgs.yssmx.com/Uploads/2024/01/817663-1.png)
