C++?STL容器詳解之紅黑樹部分模擬實(shí)現(xiàn)
一、紅黑樹的概念
紅黑樹（Red Black Tree），是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，是一種二叉搜索樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。 通過對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會(huì)比其他路徑長出倆倍，因而是接近平衡的。
二、紅黑樹的性質(zhì)
1. 每個(gè)結(jié)點(diǎn)不是紅色就是黑色；
2. 根節(jié)點(diǎn)是黑色的；
3. 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子結(jié)點(diǎn)是黑色的；
4. 對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑上，均 包含相同數(shù)目的黑色結(jié)點(diǎn)；
5. 每個(gè)葉子結(jié)點(diǎn)都是黑色的(此處的葉子結(jié)點(diǎn)指的是空結(jié)點(diǎn))；
滿足上面的性質(zhì)，紅黑樹就能保證其最長路徑中節(jié)點(diǎn)個(gè)數(shù)不會(huì)超過最短路徑節(jié)點(diǎn)個(gè)數(shù)的兩倍。
三、紅黑樹節(jié)點(diǎn)的定義
enum Colour //紅黑樹顏色枚舉
{
RED,
BLACK,
};
template<class K, class V>
struct RBTreeNode //節(jié)點(diǎn)結(jié)構(gòu)體
{
RBTreeNode<K, V>* _left; //左子樹
RBTreeNode<K, V>* _right; //右子樹
RBTreeNode<K, V>* _parent; //父節(jié)點(diǎn)
pair<K, V> _kv;
Colour _col;
RBTreeNode(const pair<K, V>& kv) //構(gòu)造函數(shù)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
插入時(shí)默認(rèn)為紅色節(jié)點(diǎn)，因?yàn)榧t色可能會(huì)破壞規(guī)則3，黑色一定會(huì)破壞規(guī)則4，所以默認(rèn)紅色。
四、紅黑樹結(jié)構(gòu)?
為了后續(xù)實(shí)現(xiàn)關(guān)聯(lián)式容器簡(jiǎn)單，紅黑樹的實(shí)現(xiàn)中增加一個(gè)頭結(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)必須為黑色，為了與根節(jié)點(diǎn)進(jìn)行區(qū)分，將頭結(jié)點(diǎn)給成黑色，并且讓頭結(jié)點(diǎn)的 parent 域指向紅黑樹的根節(jié)點(diǎn)，left域指向紅黑樹中最小的節(jié)點(diǎn)，right域指向紅黑樹中最大的節(jié)點(diǎn)，如下:
五、 紅黑樹的插入操作
紅黑樹是在二叉搜索樹的基礎(chǔ)上加上其平衡限制條件，因此紅黑樹的插入可分為兩步：
1. 按照二叉搜索的樹規(guī)則插入新節(jié)點(diǎn)：
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return make_pair(_root, true);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
Node* newNode = new Node(kv);
newNode->_col = RED;
if (parent->_kv.first > kv.first)
{
parent->_left = newNode;
newNode->_parent = parent;
}
else
{
parent->_right = newNode;
newNode->_parent = parent;
}
cur = newNode;
while (parent && parent->_col == RED) //違反規(guī)則三
{
}
_root->_col = BLACK; //插入結(jié)束再次將根變?yōu)楹?
return make_pair(cur, true);
}
2. 檢測(cè)新節(jié)點(diǎn)插入后，紅黑樹的性質(zhì)是否造到破壞
因?yàn)樾鹿?jié)點(diǎn)的默認(rèn)顏色是紅色，因此：如果其雙親節(jié)點(diǎn)的顏色是黑色，沒有違反紅黑樹任何性質(zhì)，則不需要調(diào)整；但當(dāng)新插入節(jié)點(diǎn)的雙親節(jié)點(diǎn)顏色為紅色時(shí)，就違反了性質(zhì)三不能有連在一起的紅色節(jié)點(diǎn)，此時(shí)需要對(duì)紅黑樹分情況來討論：
cur為當(dāng)前節(jié)點(diǎn)，p為父節(jié)點(diǎn)，g為祖父節(jié)點(diǎn)，u為叔叔節(jié)點(diǎn)
情況一：cur為紅，p為紅，g為黑，u存在且為紅
如果g是根節(jié)點(diǎn)，調(diào)整完成后，需要將g改為黑色，如果g是子樹，g一定有父節(jié)點(diǎn)，且如果為紅色呃，繼續(xù)向上調(diào)整。
將p,u改為黑，g改為紅，然后把g當(dāng)成cur，繼續(xù)向上調(diào)整 。
情況二: cur為紅，p為紅，g為黑，u不存在/u為黑
u的情況有兩種：
1.如果u節(jié)點(diǎn)不存在，則cur一定是新插入節(jié)點(diǎn)，因?yàn)槿绻鹀ur不是新插入節(jié)點(diǎn)，則cur和p一定有一個(gè)節(jié)點(diǎn)的顏色是黑色，就不滿足性質(zhì)4：每條路徑黑色節(jié)點(diǎn)個(gè)數(shù)相同。
2.如果u節(jié)點(diǎn)存在，則其一定是黑色的，那么cur節(jié)點(diǎn)原來的顏色一定是黑色的，現(xiàn)在看到其是紅色的原因是因?yàn)閏ur的子樹在調(diào)整的過程中將cur節(jié)點(diǎn)的顏色由黑色改成紅色。
p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋轉(zhuǎn)；
p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋轉(zhuǎn)。
p變黑，g變紅。
情況三: cur為紅，p為紅，g為黑，u不存在/u為黑
需要進(jìn)行雙旋。
代碼實(shí)現(xiàn)：
while (parent && parent->_col == RED) //違反規(guī)則三
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) //左半邊
{
Node* uncle = parent->_right;
if (uncle && uncle->_col == red) //情況一
{
uncle->_col = BLACK;
grandfather->_col = RED;
parent->_col = BLACK;
cur = grandfather; //迭代
parent = cur->_parent;
}
else //情況2.3
{
if (cur == parent->_left) //單側(cè)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break; //黑色數(shù)量無變化，不需要向上
}
}
else // parent == grandfather->_right
{
Node* uncle = parent->_left;
if (uncle && uncle->_col == red) //情況一
{
uncle->_col = BLACK;
grandfather->_col = RED;
parent->_col = BLACK;
cur = grandfather; //迭代
parent = cur->_parent;
}
else //情況2.3
{
if (cur == parent->_right) //單側(cè)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
六、代碼
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Colour //紅黑樹顏色枚舉
{
RED,
BLACK,
};
template<class K, class V>
struct RBTreeNode //節(jié)點(diǎn)結(jié)構(gòu)體
{
RBTreeNode<K, V>* _left; //左子樹
RBTreeNode<K, V>* _right; //右子樹
RBTreeNode<K, V>* _parent; //父節(jié)點(diǎn)
pair<K, V> _kv;
Colour _col;
RBTreeNode(const pair<K, V>& kv) //構(gòu)造函數(shù)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
private:
Node* _root;
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentP = parent->_parent;
if (subLR) //左子樹的右子樹連接到父的右
subLR->_parent = parent;
parent->_left = subLR;
subL->_right = parent;
parent->_parent = subL;
// 如果parent是根節(jié)點(diǎn)，根新指向根節(jié)點(diǎn)的指針
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
// 如果parent是子樹，可能是其雙親的左子樹，也可能是右子樹
if (parentP->_left == parent)
parentP->_left = subL;
else
parentP->_right = subL;
subL->_parent = parentP;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentP = parent->_parent;
if (subRL)
subRL->_parent = parent;
parent->_right = subRL;
subR->_left = parent;
parent->_parent = subR;
// 如果parent是根節(jié)點(diǎn)，根新指向根節(jié)點(diǎn)的指針
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
// 如果parent是子樹，可能是其雙親的左子樹，也可能是右子樹
if (parentP->_left == parent)
parentP->_left = subR;
else
parentP->_right = subR;
subR->_parent = parentP;
}
}
void _Destory(Node* root)
{
if (root == nullptr)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
public:
RBTree()
:_root(nullptr)
{}
~RBTree()
{
_Destory(_root);
_root = nullptr;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return make_pair(_root, true);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
Node* newNode = new Node(kv);
newNode->_col = RED;
if (parent->_kv.first > kv.first)
{
parent->_left = newNode;
newNode->_parent = parent;
}
else
{
parent->_right = newNode;
newNode->_parent = parent;
}
cur = newNode;
while (parent && parent->_col == RED) //違反規(guī)則三
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) //左半邊
{
Node* uncle = parent->_right;
if (uncle && uncle->_col == red) //情況一
{
uncle->_col = BLACK;
grandfather->_col = RED;
parent->_col = BLACK;
cur = grandfather; //迭代
parent = cur->_parent;
}
else //情況2.3
{
if (cur == parent->_left) //單側(cè)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break; //黑色數(shù)量無變化，不需要向上
}
}
else // parent == grandfather->_right
{
Node* uncle = parent->_left;
if (uncle && uncle->_col == red) //情況一
{
uncle->_col = BLACK;
grandfather->_col = RED;
parent->_col = BLACK;
cur = grandfather; //迭代
parent = cur->_parent;
}
else //情況2.3
{
if (cur == parent->_right) //單側(cè)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK; //插入結(jié)束再次將根變?yōu)楹?
return make_pair(newNode, true);
}
};
總結(jié)
本文對(duì)紅黑樹進(jìn)行了介紹，并對(duì)構(gòu)造，插入，查找進(jìn)行了模擬實(shí)現(xiàn)。
以上就是C++ STL容器詳解之紅黑樹部分模擬實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++ STL紅黑樹實(shí)現(xiàn)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C語言簡(jiǎn)單實(shí)現(xiàn)銀行ATM存取款功能
這個(gè)是大一時(shí)期寫的。大四的時(shí)候整理了一下（本人C語言學(xué)的也不太好）。肯定很多不足和存在漏洞的地方、僅供借鑒、僅供借鑒，代碼中有大量注釋，新手看起來也沒有困難2021-11-11
C/C++常用函數(shù)易錯(cuò)點(diǎn)分析
這篇文章主要介紹了C/C++常用函數(shù)易錯(cuò)點(diǎn)分析,包含了memset、sizeof、getchar三個(gè)常用函數(shù)的分析,需要的朋友可以參考下2014-08-08
處理時(shí)間是編程中經(jīng)常遇到的問題，C語言中提供了一些時(shí)間處理函數(shù)，在此記錄下一些基本的用法。下面這篇文章主要給大家介紹了C語言中關(guān)于時(shí)間的基本用法的相關(guān)資料，需要的朋友可以參考借鑒，感興趣的朋友們來一起看看吧。2017-01-01
教你使用Matlab制作圖形驗(yàn)證碼生成器(app designer)
這篇文章主要和大家分享如何利用Matlab制作一款圖形驗(yàn)證碼生成器，文中的實(shí)現(xiàn)步驟講解詳細(xì)，感興趣的小伙伴可以跟隨小編動(dòng)手試一試2022-02-02
這篇文章主要介紹了c++函數(shù)重載的相關(guān)知識(shí)，文章講解的非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06
C語言學(xué)習(xí)之標(biāo)識(shí)符的使用詳解
C語言標(biāo)識(shí)符是用于表示變量、函數(shù)、常量、類型等程序元素的名稱，這篇文章將通過一些簡(jiǎn)單的示例為大家介紹一下C語言標(biāo)識(shí)符的使用，需要的可以參考一下2023-05-05
C語言實(shí)現(xiàn)交換排序算法(冒泡,快速排序)的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用C語言實(shí)現(xiàn)交換排序算法(冒泡排序、快速排序)，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-07-07
這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)簡(jiǎn)單的TCP通信，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
UE4 Unlua 調(diào)用異步藍(lán)圖節(jié)點(diǎn)AIMoveTo函數(shù)示例詳解
這篇文章主要為大家介紹了UE4 Unlua 調(diào)用AIMoveTo函數(shù)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09
這篇文章主要為大家詳細(xì)介紹了C語言線性表之雙鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02