紅黑樹的特點(diǎn)

• 紅黑樹，是一種二叉搜索樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是 Red或 Black。 通過對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，因而是接近平衡的.

• 紅黑樹的特點(diǎn):

  1. 節(jié)點(diǎn)顏色不是紅色就是黑色
  2. 根節(jié)點(diǎn)是黑色的
  3. 每一條路徑的黑色節(jié)點(diǎn)數(shù)目是相同的, (注意: 這里的路徑是從根節(jié)點(diǎn)到NIL(黑色)節(jié)點(diǎn))
  4. 每一條路徑不允許出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)

• 路徑是從根節(jié)點(diǎn) 到 NIL節(jié)點(diǎn)的
  

🗨?滿足上面的條件, 為啥就能保證 紅黑樹確保沒有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍呢?

• 根據(jù)上述的特點(diǎn), 我們可以得知:
  當(dāng) 每條路徑的黑色節(jié)點(diǎn)數(shù)目一定的情況下 , 最短路徑是 全黑, 最長(zhǎng)路徑是 黑紅相間的
  如果我們保證 最長(zhǎng)路徑 不超過 最短路徑的二倍就可以了
  

紅黑樹的模擬實(shí)現(xiàn)

紅黑樹的底層結(jié)構(gòu)

1. 顏色類型

// 枚舉
enum Color
{RED,BLACK
};

2. RBTreeNode類

template<class K, class V>
struct RBTreeNode
{
public:RBTreeNode(const pair<K, V> kv):_kv(kv){}public:pair<K, V> _kv;Color _color = BLACK;RBTreeNode<K, V>* _left = nullptr;RBTreeNode<K, V>* _right = nullptr;RBTreeNode<K, V>* _parent = nullptr;
};

3. RBTree類

template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public:RBTree(){}private:// 根節(jié)點(diǎn)Node*  _root = nullptr;// 記錄旋轉(zhuǎn)次數(shù)int RotateCount =  0;
}

insert的實(shí)現(xiàn)

實(shí)現(xiàn)思路

二叉搜索樹的插入邏輯 + 更新黑紅比例

bool Insert(const pair<K, V> kv)
{if (_root == nullptr){// 根節(jié)點(diǎn)是黑色的_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = _root;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 新建一個(gè)節(jié)點(diǎn), 默認(rèn)是紅色cur = new Node(kv);cur->_color = RED;// 鏈接cur 和 parentif (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更改黑紅比例// ...// ...// 更新完黑紅比例后, 就返回truereturn true;
}

🗨? 不能出現(xiàn)連續(xù)的紅色節(jié)點(diǎn) ? 我們插入節(jié)點(diǎn)給個(gè)黑色節(jié)點(diǎn)多好, 為啥還要給紅色節(jié)點(diǎn)冒風(fēng)險(xiǎn)呢?

• 
  

因?yàn)? 我們插入的節(jié)點(diǎn)顏色是 紅色, 插入的位置就有兩種可能:

1. 插入到黑色節(jié)點(diǎn)的后面 — — 正常的情況, 不需要進(jìn)行更新
2. 插入到紅色節(jié)點(diǎn)的后面 — — 出現(xiàn)連續(xù)的紅色節(jié)點(diǎn), 需要 更新這一條支路 (當(dāng)前節(jié)點(diǎn)到祖宗節(jié)點(diǎn)這一條路徑)中的黑紅比例

更新黑紅比例的邏輯

由于 插入前, 是符合紅黑樹的性質(zhì),
插入的節(jié)點(diǎn)是紅色 ? 插入后才會(huì)出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)

? 設(shè)插入的新節(jié)點(diǎn)為 cur(紅色) ,
則父親節(jié)點(diǎn) paren 為 紅色, 祖父節(jié)點(diǎn) grandfather 為 黑色 ? 這才符合 插入前符合紅黑樹的特點(diǎn), 插入后才會(huì)出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)的情況

其實(shí), 更新 當(dāng)前節(jié)點(diǎn)到 祖宗節(jié)點(diǎn)這一條路徑的 黑紅比例 的本質(zhì)是 看uncle的情況
首先, 要確定 uncle 位于grandfather的哪一側(cè) && uncle不一定存在, 但parent一定存在
? 要確定parent 位于 grandfather的那一側(cè):

1. parent 位于 grandfather的左側(cè)
2. parent 位于 grandfather的右側(cè)

其次, 才是 uncle 的存在情況 以及 顏色情況

---

1. uncle存在且為紅
   

2. uncle不存在
   如果 uncle不存在 ? cur為新增節(jié)點(diǎn)

• 如果cur不是新增節(jié)點(diǎn), 那么 parent后面的節(jié)點(diǎn)必定是黑色的, 那么就違反了 每一條路徑的黑色節(jié)點(diǎn)的個(gè)數(shù)是相同
  
  

3. uncle存在且為黑
   
   如果uncle存在, 那么必定是 黑色 ? 那么 cur 也應(yīng)該是 黑色.
   現(xiàn)在看到的cur 是紅色的, 是由下面的更新上來的

通過上面的圖示, 我們得出 : 插入時(shí), uncle主要分為兩種情況

1. uncle存在且為紅 — — 由于更新后的頭結(jié)點(diǎn)為紅 ? 我們需要繼續(xù)向上更新下去
2. uncle不存在 或 uncle存在且為黑 — — 由于更新后的頭結(jié)點(diǎn)為黑 ? 我們不需要繼續(xù)向上更新下去

insert的完整代碼

bool Insert(const pair<K, V> kv)
{if (_root == nullptr){// 根節(jié)點(diǎn)是黑色的_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = _root;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 新建一個(gè)節(jié)點(diǎn), 默認(rèn)是紅色cur = new Node(kv);cur->_color = RED;// 鏈接cur 和 parentif (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更改黑紅比例// 父親節(jié)點(diǎn)存在且為紅, 才有機(jī)會(huì)繼續(xù)向上更新下去while (parent && parent->_color == RED){Node* grandfather = parent->_parent;// parent 為 grandfather的左側(cè)if (grandfather->_left == parent){Node* uncle = grandfather->_right;// u存在且為紅if (uncle && uncle->_color == RED){// 顏色變化grandfather->_color = RED;parent->_color = uncle->_color = BLACK;// 繼續(xù)向上調(diào)整cur = grandfather;parent = cur->_parent;}else // u不存在 或 u存在且為黑色{if (cur == parent->_left){RotateR(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;}// 更新后的頭節(jié)點(diǎn)為黑色, 不需要繼續(xù)向上更新break;}}// parent 為 grandfather的右側(cè)else if (grandfather->_right == parent){Node* uncle = grandfather->_left;// u存在且為紅if (uncle && uncle->_color == RED){// 顏色變化grandfather->_color = RED;uncle->_color = parent->_color = BLACK;// 繼續(xù)向上調(diào)整cur = grandfather;parent = cur->_parent;}// u不存在 或 u存在且為黑色else{if (parent->_right == cur){RotateL(grandfather);parent->_color = BLACK;grandfather->_color = RED;}else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}// 更新后的頭節(jié)點(diǎn)為黑色, 不需要繼續(xù)向上更新break;}}else{assert("黑紅比例失控!");}}// 有可能更新過程中會(huì)把 root更新為紅色 // && root節(jié)點(diǎn)的顏色必須為黑色// -->暴力統(tǒng)一處理根節(jié)點(diǎn)的顏色_root->_color = BLACK;return true;
}

insert的驗(yàn)證

1. 每一條路徑的 黑節(jié)點(diǎn)個(gè)數(shù)相同 ? 先找一個(gè) 基準(zhǔn)值(root的左子樹中 黑節(jié)點(diǎn)的個(gè)數(shù))
   如果后面的路徑中 有的黑節(jié)點(diǎn)的個(gè)數(shù) 跟 基準(zhǔn)值不同, 那就返回false.
2. 不能有連續(xù)的紅節(jié)點(diǎn) ? 當(dāng)前節(jié)點(diǎn)為紅節(jié)點(diǎn), 那么父親節(jié)點(diǎn)不能為紅節(jié)點(diǎn)
3. root 節(jié)點(diǎn)的顏色要為 黑色

驗(yàn)證代碼

// 外面調(diào)用接口
bool IsBalance()
{return IsBalance(_root);
}bool IsBalance(Node* root)
{if (root == nullptr)return true;// root節(jié)點(diǎn)為紅, 就直接返回falseif (root->_color != BLACK){return false;}// 基準(zhǔn)值 -- root左子樹中的黑節(jié)點(diǎn)個(gè)數(shù)int benchmark = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK)++benchmark;cur = cur->_left;}// 檢查每條路徑中黑節(jié)點(diǎn)個(gè)數(shù) && 不能出現(xiàn)連續(xù)的紅節(jié)點(diǎn)return CheckColour(root, 0, benchmark);
}bool CheckColour(Node* root, int blacknum, int benchmark)
{// 到葉子節(jié)點(diǎn), 比較路徑中黑節(jié)點(diǎn)的個(gè)數(shù) 和 基準(zhǔn)值if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_color == BLACK){++blacknum;}// 不能存在連續(xù)的紅節(jié)點(diǎn)if (root->_color == RED && root->_parent && root->_parent->_color == RED){cout << root->_kv.first << "出現(xiàn)連續(xù)紅色節(jié)點(diǎn)" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);
}

Height

// 外面調(diào)用接口
int Height()
{return Height(_root);
}int Height(Node* root)
{if (root == nullptr)return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;
}

GetRotateCount

int GetRoateCount()
{return RotateCount;
}

測(cè)試程序

void rbt_test()
{const int N = 10000000;vector<int> v;v.reserve(N);srand((unsigned int)time(NULL));for (size_t i = 0; i < N; i++){int ret = rand();v.push_back(ret);// v.push_back(i);}muyu::RBTree<int, int> rbt;for (auto e : v){rbt.Insert(make_pair(e, e));// cout << "Insert:" << e << "->" << avl.Isbalance() << endl;}cout << "紅黑樹是否達(dá)標(biāo)-> " << rbt.IsBalance() << endl;cout << "紅黑樹的高度-> " << rbt.Height() << endl;cout << "紅黑樹旋轉(zhuǎn)的次數(shù)-> " << rbt.GetRoateCount() << endl;
}int main()
{rbt_test();return 0;
}

運(yùn)行結(jié)果:

紅黑樹是否達(dá)標(biāo)-> 1
紅黑樹的高度-> 19
紅黑樹旋轉(zhuǎn)的次數(shù)-> 19119

---

源碼

#pragma once#include<iostream>using namespace std;namespace muyu
{// 枚舉enum Color{RED,BLACK};template<class K, class V>struct RBTreeNode{public:RBTreeNode(const pair<K, V> kv):_kv(kv){}public:pair<K, V> _kv;Color _color = BLACK;RBTreeNode<K, V>* _left = nullptr;RBTreeNode<K, V>* _right = nullptr;RBTreeNode<K, V>* _parent = nullptr;};template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;public:RBTree(){}void RotateL(Node* parent){++RotateCount;Node* cur = parent->_right;Node* grandfather = parent->_parent;Node* curleft = cur->_left;// 旋轉(zhuǎn)核心parent->_right = curleft;cur->_left = parent;// 更新父親// 1. parent && curleftif (curleft){curleft->_parent = parent;}parent->_parent = cur;// 2.更新curif (grandfather == nullptr){cur->_parent = nullptr;_root = cur;}else{if (grandfather->_left == parent){grandfather->_left = cur;}else{grandfather->_right = cur;}cur->_parent = grandfather;}}void RotateR(Node* parent){++RotateCount;Node* cur = parent->_left;Node* grandfather = parent->_parent;Node* curright = cur->_right;// 旋轉(zhuǎn)核心parent->_left = curright;cur->_right = parent;// 更新鏈接關(guān)系// 1. parent && currightif (curright){curright->_parent = parent;}parent->_parent = cur;// 2.更新curif (grandfather == nullptr){cur->_parent = nullptr;_root = cur;}else{if (grandfather->_left == parent){grandfather->_left = cur;}else{grandfather->_right = cur;}cur->_parent = grandfather;}}bool Insert(const pair<K, V> kv){if (_root == nullptr){// 根節(jié)點(diǎn)是黑色的_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = _root;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 新建一個(gè)節(jié)點(diǎn), 默認(rèn)是紅色cur = new Node(kv);cur->_color = RED;// 鏈接cur 和 parentif (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更改黑紅比例while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// u存在且為紅if (uncle && uncle->_color == RED){// 顏色變化grandfather->_color = RED;parent->_color = uncle->_color = BLACK;// 繼續(xù)向上調(diào)整cur = grandfather;parent = cur->_parent;}else // u不存在 或 u存在且為黑色{if (cur == parent->_left){RotateR(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}else if (grandfather->_right == parent){Node* uncle = grandfather->_left;// u存在且為紅if (uncle && uncle->_color == RED){// 顏色變化grandfather->_color = RED;uncle->_color = parent->_color = BLACK;// 繼續(xù)向上調(diào)整cur = grandfather;parent = cur->_parent;}// u不存在 或 u存在且為黑色else{if (parent->_right == cur){RotateL(grandfather);parent->_color = BLACK;grandfather->_color = RED;}else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}else{assert("黑紅比例失控!");}}// 暴力統(tǒng)一處理根節(jié)點(diǎn)的顏色_root->_color = BLACK;return true;}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_color == BLACK){++blacknum;}if (root->_color == RED && root->_parent && root->_parent->_color == RED){cout << root->_kv.first << "出現(xiàn)連續(xù)紅色節(jié)點(diǎn)" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_color != BLACK){return false;}// 基準(zhǔn)值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int GetRoateCount(){return RotateCount;}private:Node* _root = nullptr;int RotateCount = 0;};
}

---

十年磨一劍，霜刃未曾試。
今日把示君，誰有不平事。
— — 賈島《劍客》