紅黑樹
- 紅黑樹的概念
- 紅黑樹的性質
- 紅黑樹的結點定義
- 紅黑樹的插入
- 情況一
- 情況二
- 情況三
- 紅黑樹的查找
- 紅黑樹的驗證
- 紅黑樹的和AVL樹的比較
紅黑樹的概念
紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存盤位表示結點的顏色，可以是紅色或黑色， 通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的，如下圖：
紅黑樹的性質
- 每個結點不是紅色就是黑色
- 根節點是黑色的
- 如果一個節點是紅色的，則它的兩個孩子結點是黑色的
- 對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均 包含相同數目的黑色結點
- 每個葉子結點都是黑色的(此處的葉子結點指的是空結點)
上面的4點性質用自己的話可以總結為：(性質5不用記)
1.結點不是紅色就是黑色
2.沒有連續的紅色結點
3.每條路徑上的黑色結點的數量是一樣的
AVL樹是通過高度來控制平衡的，是嚴格平衡的，那如果新插入結點很多那么旋轉也是要付出代價的，紅黑樹通過顏色來控制平衡，但不是嚴格的平衡，它近似平衡，紅黑樹也可以達到AVL樹的效率，它最長路徑不超過最短路徑的2倍，
那為什么紅黑樹的最長路徑不超過最短路徑的2倍呢？
通過上面的性質，假設我們把紅黑樹的黑色結點單獨抽出來，從跟到葉子黑結點個數為N個
那它最短路徑就是長度為N
那它最長的路徑可能是一黑一紅
那它的長度為2N，所以它的最長路徑不超過最短路徑的2倍，則其他路徑的長度就在N-2N之間，那么紅黑樹增刪查改的效率就在logN-2logN之間，和AVL樹的logN差不多了，
紅黑樹的結點定義
紅黑樹的結點定義還是跟AVL樹一樣，定義成三叉鏈結構和KV模型，不同的則是紅黑樹用列舉加入了顏色，
enum Color
{
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;
Color _color;//該結點的顏色
RBTreeNode(const pair<K,V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_color(RED)
{}
};
紅黑樹的插入
那么我們插入結點時選擇插入黑結點還是紅結點呢？
當然是選擇插入紅結點了，選擇插入黑結點那麻煩就大了，那1條路徑上就多了1個黑結點，破壞了性質4，代價很大，插入紅結點，如果它的父親結點是黑色則不用調整，拍拍屁股走人，它的父親是紅色那我們在進行后序的處理，
總結一下：
1.插入黑色結點一定破壞性質4，調整起來會很麻煩
2.插入紅結點不一定破壞紅黑樹的性質，它的父親結點是紅色才進行調整，比插入黑結點調整起來方便，
??????????***我是分割線***??????????????
插入的邏輯：
1.找到插入結點的位置
2.插入結點
3.檢測新結點插入后是否破壞了紅黑的性質，如果破壞則需要進行處理
因為新插入結點的顏色是紅色，若它的父親結點是黑色不用調整，是紅色的話需要對紅黑樹分情況來討論，
紅黑樹調整主要看叔叔結點
下面我們根據叔叔結點的情況來具體看一下，
情況一
以下用p來代表parent結點，c代表cur為新增結點,g代表grandparent結點，u代表uncle結點，
我們還是跟AVL樹一樣畫具象圖：
1.叔叔結點存在且為紅
為什么把g變成紅色呢？如果g不變成紅色，那此時子樹上就多了1個黑結點了，
只要我們畫出具象圖，那面試時手撕紅黑樹也完全不慫，
當然還有很多種情況，那就給出抽象圖：
這種情況下cur在p的左邊還是右邊都不影響，
情況二
叔叔結點存在且為黑，新增結點是p的左邊
這是由情況一變來的，如果u存在那cur一定是黑的，不是新鄭結點，這樣才滿足紅黑樹的性質，
??????????***我是分割線***??????????????
新增結點是p的右邊
情況三
叔叔結點不存在
新增結點在parent的左邊
新增結點在parent的右邊
總結一下：
以上的情況都是父親結點在祖先結點的左邊，在祖先結點的右邊也是相同的處理方法
1.叔叔結點存在且為紅，把父親結點和叔叔結點變黑，祖先變紅繼續向上處理直到祖先是根節點
2.叔叔存在為黑，祖孫三代在一條直線上進行單旋，不在則進行雙旋
3.叔叔不存在，祖孫三代在一條直線上進行單旋，不在則進行雙旋
所以2,3的邏輯可以合在一起，分為新增結點在父親結點的左邊還是右邊處理，
下面再來簡單的說說父親結點在祖先結點的右邊
叔叔存在且為紅
此時，cur在p的左邊還是右邊沒有影響，
叔叔存在且為黑
新增結點在父親結點的右邊
新增結點在父親結點的左邊
叔叔不存在
總結一下：
1.叔叔存在且為紅,u,p變黑，g變紅繼續向上調，直到g為根結點，最后把g變黑
2.叔叔存在且為黑，祖孫3帶在一條直線上單旋，折線要雙旋
3.叔叔不存在，祖孫3帶在一條直線上單旋，折線要雙旋
??????????***我是分割線***??????????????
代碼如下：
pair<Node*, bool> insert(const pair<K, V>& kv)
{
//1.樹為空
if (_root == nullptr)
{
_root = new Node(kv);
_root->_color = BLACK;//根結點為黑色
return make_pair(_root, true);
}
//樹不為空
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
//新結點key大于當前結點往右邊
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
//新結點key小于當前結點往左邊
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(cur, false);
}
}
cur = new Node(kv);
Node* newnode = cur;
newnode->_color = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = newnode;
newnode->_parent = parent;
}
else
{
parent->_left = newnode;
newnode->_parent = parent;
}
//開始調整顏色
//父親存在且為紅
while (parent && parent->_color == RED)
{
Node* grandParent = parent->_parent;
//parent是grandParent左孩子
if (grandParent->_left == parent)
{
Node* uncle = grandParent->_right;
//叔叔存在且為紅色,父親和叔叔都調為黑色
//祖先調為紅色，如果不調那每條路徑的黑結點變了
if (uncle && uncle->_color == RED)
{
parent->_color = BLACK;
uncle->_color = BLACK;
grandParent->_color = RED;
//繼續往上調
cur = grandParent;
parent = cur->_parent;
}
else//叔叔不存在或叔叔存在且為黑
{
if (parent->_left == cur)
{ //右單旋
RotateR(grandParent);
parent->_color = BLACK;
grandParent->_color = RED;
}
else //parent->_right == cur
{
RotateL(parent);
RotateR(grandParent);
grandParent->_color = RED;
cur->_color = BLACK;
}
break;
}
}
else //parent是grandParent左孩子
{
Node* uncle = grandParent->_left;
if (uncle && uncle->_color == RED)
{
uncle->_color = BLACK;
parent->_color = BLACK;
grandParent->_color = RED;
cur = grandParent;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandParent);
parent->_color = BLACK;
grandParent->_color = RED;
}
else
{
RotateR(parent);
RotateL(grandParent);
cur->_color = BLACK;
grandParent->_color = RED;
}
break;
}
}
}
_root->_color = BLACK;
return make_pair(newnode, true);
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//先旋轉
parent->_right = subRL;
subR->_left = parent;
parent->_parent = subR;
//在改父親結點
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
//subR旋轉后可能是左右子樹2種情況
if (parentParent->_left == parent)
parentParent->_left = subR;
else
parentParent->_right = subR;
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;//記錄parent的父親結點
//subLR做parent->_left
parent->_left = subLR;
subL->_right = parent;
//同時更新動的2個節點的parent
//注意subLR還可能是空結點
if (subLR)
subLR->_parent = parent;
parent->_parent = subL;
//parent可能是單獨的樹，或者子樹,分情況
if (_root == parent)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
//還有可能parent是子樹，可能是左子樹
if (parentParent->_left == parent)
parentParent->_left = subL;
else
//也可能是右子樹
parentParent->_right = subL;
//調整subL的父親結點
subL->_parent = parentParent;
}
}
紅黑樹的查找
查找跟AVL樹的邏輯是一樣的，博主這里就不做多的講解了，
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
紅黑樹的驗證
先檢查有沒有連續的紅結點，還有紅結點的父親結點是不是黑色，這就保證了沒有連續的紅結點，還有路徑也要算，我們找1條路徑作為參考，例如最左路徑，只要有1條路徑和它的黑結點數量不同就不是紅黑樹，
bool _CheckBlance(Node* root,int blackNum, int count)
{
if (root == nullptr)
{
if (count != blackNum)
{
cout << "黑色節點的數量不相等" << endl;
return false;
}
return true;
}
if (root->_color == RED && root->_parent->_color == RED)
{
cout << "存在連續的紅色節點" << endl;
return false;
}
if (root->_color == BLACK)
{
count++;
}
return _CheckBlance(root->_left, blackNum, count)
&& _CheckBlance(root->_right, blackNum, count);
}
bool CheckBlance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_color == RED)
{
cout << "根節點是紅色的" << endl;
return false;
}
// 找最左路徑做黑色節點數量參考值
int blackNum = 0;
Node* left = _root;
while (left)
{
if (left->_color == BLACK)
{
blackNum++;
}
left = left->_left;
}
int count = 0;
return _CheckBlance(_root, blackNum, count);
}
我們來測驗一下：
沒有問題，博主也是除錯了好長時間，一定要用好除錯，
紅黑樹的和AVL樹的比較
紅黑樹的洗掉也是了解，紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的時間復雜度都是O(log2)，紅黑樹不追求絕對平衡，其只需保證最長路徑不超過最短路徑的2倍，相對而言，降低了插入和旋轉的次數，所以在經常進增刪的結構中性能比AVL樹更優，而且紅黑樹實作比較簡單，所以實際運用中紅黑樹更多，
🍁🍁博主水平有限，如有錯誤，直接留下評論即可！🍁🍁
🍁🍁紅黑樹是面試必備的，大家一起加油！🍁🍁
🍁🍁歡迎一鍵三連！ 🍁🍁
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/413427.html
標籤：其他
下一篇：資料結構--TopK問題