C++實現(xiàn)紅黑樹核心插入實例代碼
一、紅黑樹概念介紹
概念：
紅黑樹，也是一種二叉搜索樹，它是在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是紅或黑，然后通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，保證了沒有一條路徑會能超過其他路徑的倆倍，因而是近似平衡的。map和set的底層數(shù)據(jù)結(jié)構(gòu)就是用紅黑樹來封裝的。
性質(zhì)：
1.根節(jié)點是黑色的
2.不能出現(xiàn)連續(xù)的紅色節(jié)點
3. 每條路徑上有相同數(shù)量的黑色節(jié)點
4. 每個葉子(空節(jié)點)結(jié)點都是黑色
5. 每個結(jié)點不是紅色就是黑色
滿足上面的性質(zhì)，紅黑樹就能保證：最長路徑中節(jié)點個數(shù)不會超過最短路徑節(jié)點個數(shù)的2倍。
優(yōu)勢：
假設全部的黑色節(jié)點有N個 最短路徑長度是logN 整棵樹的節(jié)點數(shù)量：[N,2N]，最長路徑長度：2logN。假設10億個節(jié)點，AVL：最多查找30次左右；RB：最多查找60次左右。
綜合而言，其實對于查找大量數(shù)據(jù)30次和60次沒太大差別，而紅黑樹不要求絕對平衡，只需保證最長路徑不超過最短路徑的2倍，相對來說降低了插入和旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)。
二、紅黑樹模擬實現(xiàn)
（1）紅黑樹節(jié)點
enum Color
{
RED=0,
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 _col;
RbTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};里面同樣用三叉鏈，要有左孩子右孩子，父節(jié)點，以及pair類的類型來存儲kv兩個相同或不同類型的值(當我們使用make_pair函數(shù)創(chuàng)建一個pair對象，該函數(shù)會自動推斷參數(shù)類型)，并在里面增加一個枚舉，用來表示一個節(jié)點不是紅色就是黑色。關于構(gòu)造函數(shù)里面的顏色初始化為黑色還是紅色，在插入會講解。
（2）紅黑樹插入分析(核心)
插入和前面的AVL插入部分是一樣的，在里面如果是根節(jié)點，那就把跟點為置為黑色。
那這有一個問題就是節(jié)點構(gòu)造函數(shù)里面的一個問題：我們在申請一個新節(jié)點時，寧愿新增紅色還是黑色？
因為不管是增哪種顏色，本質(zhì)上是違反規(guī)則三還是違反規(guī)則四的問題，如果插入黑色，一定違反規(guī)則四，但它代價太大，違反規(guī)則三就不一定，因為它的父節(jié)點可能為紅色也可能為黑色，如果在黑色節(jié)點下面插入就沒影響，反之就會影響。
對于上面的做法會出現(xiàn)下面的兩大情況，第一GPC為一一條直線，第二GPC為折線。
如圖：
G為祖父節(jié)點，P為父親節(jié)點，C為當前節(jié)點，U為叔父節(jié)點
1、先解決當GPC為一條直線的時候：
（1）如果U存在且為紅色，P必須變黑，U也得變黑，左右都增加了黑，那就把G變紅,這樣久能保持黑色節(jié)點不變，因為G現(xiàn)在變成紅了，但是G的父節(jié)點如果是紅色的還得繼續(xù)處理 ，那就把G當成C節(jié)點，繼續(xù)算它的祖父，再看U，如果U是紅再把它變成黑。
它的所對應的抽象圖以及具象圖：
（2）如果U不存在或者存在且為黑又是兩種情況
如果U不存在，再增加紅節(jié)點，且有連續(xù)的紅色節(jié)點，有可能會超過它的最短路徑，只能旋轉(zhuǎn)來降高度。把P變黑，把G給P的左，再把P作為左，同時把原來的G變紅，這里就是左單旋加G和P變色。
如下例圖：
它所對應的抽象及具象圖：
如果U存在且為黑色
U存在且為黑是由第一種請況變化而來，這里發(fā)生了右單旋，P的左孩子作為G的左孩子，而G又作為P的右孩子，且P變?yōu)楹?，G變?yōu)榧t。
對于上面的U不存在或者存在為黑兩種情況進行總結(jié)： P為G的左孩子時，C為P的左孩子進行右單旋轉(zhuǎn)，如果P為G的右孩子，C為P的右孩子，進行左單旋轉(zhuǎn)。P變?yōu)楹谏珿變?yōu)榧t色。
旋轉(zhuǎn)的目的就是為了防止最長路徑超過最短路徑的2倍。GPC為一條線的時候就是左單旋轉(zhuǎn)或右單旋。
2、再解決GPC為折線的情況
（1）U存在且為黑
出現(xiàn)這種折線情況的原因是由第一種情況先變色而產(chǎn)生，然后p變成g的左，c變成p的右，c為紅，p為紅，g為黑，接著我們先以p為軸進行左旋轉(zhuǎn)進行降低高度，在以g為軸進行右旋，且g變紅，c變黑，因為這樣才能保證不出現(xiàn)連續(xù)紅結(jié)點且保證每個路徑黑色數(shù)量一樣。以上實際進行了雙旋。
（2）U不存在，直接右單旋
（3）插入代碼思路(如何快速寫插入算法)
（一）先看左面這種大情況
插入C1肯定為紅節(jié)點，P1如果是紅，就需要開始作處理：先利用三叉鏈，從P1得出G1，進入核心環(huán)節(jié)：左面的這種情況是P1是G1的左孩子時，里面又要有分兩種情況：
（1）如果是U存在且為紅，我們把P1和U變?yōu)楹?，G1變?yōu)榧t，更新C1到G1的位置，繼續(xù)往上調(diào)整；
（2）如果是U不存在或黑(是一種情況)，如果U不存在就不能變黑，而且就算存在為黑說明是一定是由繼續(xù)往上調(diào)整的那一步(情況(1))而來的即繼續(xù)往上處理，我們還是是增加了節(jié)點，就可能導致最長路徑超過最短路徑的2倍或者一直用情況(1)的方式最終導致每條路徑黑色數(shù)量不相等。這時候我們就要通過旋轉(zhuǎn)方式降低高度加變色來解決。所以在這里又分兩種：G1P1C1為直線和G1P1C1為折線：
如果是C1P1在一條直線上即C1是P1的左孩子，我們以G1為軸進行右單旋(哪邊高往哪邊降)，G1要變紅，P1要變成黑，因為G1下來了P1作為根，不能出現(xiàn)連續(xù)的紅節(jié)點P要變黑，又因為保證黑色數(shù)量相等，G1要變紅。如果是C1和P1，G1是折線的時候即C1是P1的右孩子，這時候需要先以P1為軸進行左單旋，再以G1為軸進行右單旋，最終C1做了根節(jié)點，G1是右孩子，因為P1是紅，C1是紅不能出現(xiàn)連續(xù)紅節(jié)點，需把C1變黑，但是還要保證黑色數(shù)量相等，就把G1變紅。最后結(jié)束break，只有情況(1)才會繼續(xù)向上來回處理。
（二）再看右面這種大情況
和（一）情況類似
P2是G2的右孩子，同理那旋轉(zhuǎn)方式就根上面相反。
所以我們的插入函數(shù)：
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);
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandf = parent->_parent;
if (grandf->_left == parent)
{
Node* unc = grandf->_right;
if (unc && unc->_col == RED)//u存在且為紅，變色處理
{
parent->_col = BLACK;
unc->_col = BLACK;
grandf->_col = RED;
cur = grandf;//繼續(xù)往上調(diào)整
parent = cur->_parent;
}
else//u不存在或者黑
{
if (parent->_left == cur)
{
RotateR(grandf);
parent->_col = BLACK;
grandf->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandf);
cur->_col = BLACK;
grandf->_col = RED;
}
break;
}
}
else
{
Node* unc = grandf->_left;
if (unc && unc->_col == RED)
{
parent->_col = BLACK;
unc->_col = BLACK;
grandf->_col = RED;
cur = grandf;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandf);
parent->_col = BLACK;
grandf->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandf);
cur->_col = BLACK;
grandf->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}（4）判斷平衡函數(shù)
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根節(jié)點顏色錯誤" << endl;
return false;
}
int Bsign = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++Bsign;
}
cur = cur->_left;
}
return _check(_root, 0, Bsign);
}
bool _check(Node* root, int Bnum, int Bsign)
{
if (root == nullptr)
{
if (Bnum != Bsign)
{
cout << "黑色節(jié)點數(shù)量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++Bnum;
}
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << "連續(xù)紅色節(jié)點" << endl;
return false;
}
return _check(root->_left,Bnum,Bsign) && _check(root->_right, Bnum, Bsign);
}
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}首先不能以最長路徑不超過最短路徑2倍為準則判斷平衡，它只是結(jié)果。
還是要以前面說的規(guī)則：
第一個：先檢查根是不是黑色的；
第二個：再檢查連續(xù)的紅色節(jié)點：如果是紅色的就去檢查兒子，這種方式不行，因為孩子可能不存在，可以改為它的父親，如果是紅一定有父親，如果父親為紅就存在連續(xù)紅色節(jié)點直接返回假；
還有一個：最重要的規(guī)則：判斷黑色節(jié)點的數(shù)量是否相等，我們需要先記錄一下黑色數(shù)量，我們可以先獲取一條路徑的黑色數(shù)量Bsign，然后以它為標準，如何讓每條路徑以它標準判斷是否相等？我們可以在參數(shù)里面的形參傳值Bnum，往下遞歸就會往下傳，下一層++不會影響上一層++，因為下一層是上一層的拷貝，只要有一條不相等就返回假。
（5）查找函數(shù)
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}從根開始走，如果比它大，就往右邊走，如果比它小，就往左邊走，如果相等說明找到，否則返回空。
（6）測試函數(shù)
void Test()
{
int arr[] = { 33, 22, 6, 1, 3, 5, 66, 7, 16, 14, 16, 3, 7, 11, 9, 36, 18, 14, 15 };
RbTree<int, int> t;
for (auto n : arr)
{
t.Insert(make_pair(n, n));
}
t.Inorder();
cout << endl;
cout << t.IsBalance() << endl;
cout << "高度："<<t.height() << endl;
cout << endl;
cout << "隨機數(shù)據(jù)測試:" << endl;
srand(time(0));
const size_t N = 100000;
RbTree<int, int> r;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand() + i;
r.Insert(make_pair(x, x));
}
cout << r.IsBalance() << endl;
cout <<"高度："<< r.height() << endl;
}（7）測試結(jié)果
三、紅黑樹源代碼
（1）RbTree.h
#pragma once
#include<iostream>
#include<utility>
#include<ctime>
using namespace std;
enum Color
{
RED=0,
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 _col;
RbTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
template <class K,class V>
class RbTree
{
typedef RbTreeNode<K, V> Node;
public:
~RbTree()
{
_Destroy(_root);
_root = nullptr;
}
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);
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandf = parent->_parent;
if (grandf->_left == parent)
{
Node* unc = grandf->_right;
if (unc && unc->_col == RED)//u存在且為紅，變色處理
{
parent->_col = BLACK;
unc->_col = BLACK;
grandf->_col = RED;
cur = grandf;//繼續(xù)往上調(diào)整
parent = cur->_parent;
}
else//u不存在或者黑
{
if (parent->_left == cur)
{
RotateR(grandf);
parent->_col = BLACK;
grandf->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandf);
cur->_col = BLACK;
grandf->_col = RED;
}
break;
}
}
else
{
Node* unc = grandf->_left;
if (unc && unc->_col == RED)
{
parent->_col = BLACK;
unc->_col = BLACK;
grandf->_col = RED;
cur = grandf;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandf);
parent->_col = BLACK;
grandf->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandf);
cur->_col = BLACK;
grandf->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void Inorder()
{
_InOrder(_root);
}
int height()
{
return _Height(_root);
}
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根節(jié)點顏色錯誤" << endl;
return false;
}
int Bsign = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++Bsign;
}
cur = cur->_left;
}
return _check(_root, 0, Bsign);
}
private:
void RotateL(Node* parent)//左單旋
{
Node* suR = parent->_right;//11的右孩子即22
Node* suRL = suR->_left;//11的右孩子的左孩子即b
Node* ppnode = parent->_parent;//維護父結(jié)點的父結(jié)點
parent->_right = suRL;//11右孩子鏈接b
if (suRL)//如果b不為空
suRL->_parent = parent;//更新雙親結(jié)點
suR->_left = parent;//22上提，左孩子鏈接11
parent->_parent = suR;//更新雙親結(jié)點
if (ppnode == nullptr)
{
_root = suR;
_root->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = suR;
}
else
{
ppnode->_right = suR;
}
suR->_parent = ppnode;
}
}
void RotateR(Node* parent)//右單旋
{
Node* suL = parent->_left;
Node* suLR = suL->_right;
parent->_left = suLR;
if (suLR)
suLR->_parent = parent;
Node* ppnode = parent->_parent;
suL->_right = parent;
parent->_parent = suL;
if (parent == _root)
{
_root = suL;
_root->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = suL;
}
else
{
ppnode->_right = suL;
}
suL->_parent = ppnode;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
int _Height(Node* root)
{
if (root == NULL)
return 0;
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool _check(Node* root, int Bnum, int Bsign)
{
if (root == nullptr)
{
if (Bnum != Bsign)
{
cout << "黑色節(jié)點數(shù)量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++Bnum;
}
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << "連續(xù)紅色節(jié)點" << endl;
return false;
}
return _check(root->_left,Bnum,Bsign) && _check(root->_right, Bnum, Bsign);
}
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
private:
Node* _root;
};
void Test()
{
int arr[] = { 33, 22, 6, 1, 3, 5, 66, 7, 16, 14, 16, 3, 7, 11, 9, 36, 18, 14, 15 };
RbTree<int, int> t;
for (auto n : arr)
{
t.Insert(make_pair(n, n));
}
t.Inorder();
cout << endl;
cout << t.IsBalance() << endl;
cout << "高度："<<t.height() << endl;
cout << endl;
cout << "隨機數(shù)據(jù)測試:" << endl;
srand(time(0));
const size_t N = 100000;
RbTree<int, int> r;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand() + i;
r.Insert(make_pair(x, x));
}
cout << r.IsBalance() << endl;
cout <<"高度："<< r.height() << endl;
}（2）Test.cpp
#include"RbTree.h"
int main()
{
Test();
return 0;
}總結(jié)
到此這篇關于C++實現(xiàn)紅黑樹核心插入的文章就介紹到這了,更多相關C++紅黑樹核心插入內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了C++ socket網(wǎng)絡編程實例，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-11-11
在處理一些數(shù)組的事情,所以隨手保留一下Deque容器的使用方法很有必要，接下來通過本文給大家重點介紹C++ deque容器的用法及deque和vector的區(qū)別講解，感興趣的朋友跟隨小編一起看看吧2021-05-05
這篇文章主要為大家詳細介紹了Qt實現(xiàn)蘋果狀態(tài)切換按鈕，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
這篇文章主要介紹了C++實現(xiàn)LeetCode(75.顏色排序),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了c++讀寫文件流實例，大家參考使用吧2013-12-12
如果用qt寫程序作為上位機,然后通過和usb和下位機通信的時候,就需要用到qt中的串口通信了,下面這篇文章主要給大家介紹了關于QT實現(xiàn)串口通信的相關資料,需要的朋友可以參考下2023-02-02
這篇文章主要介紹了c++傳遞函數(shù)指針和bind的示例,需要的朋友可以參考下2014-05-05
我們經(jīng)常能夠在外面看到那種滾動字幕，那么本文就拿Qt來做一個吧,本文將使用事件與定時器實現(xiàn)字幕滾動的效果，感興趣的小伙伴可以了解一下2023-06-06
這篇文章主要介紹了EasyC++自動存儲持續(xù)性，下面文章圍繞EasyC++自動存儲持續(xù)性的相關資料展開全文資料，需要的小伙伴可以參考一下下面文章的具體內(nèi)容，希望對你的學習有所幫助2021-12-12
這篇文章主要為大家詳細介紹了C語言鏈表實現(xiàn)學生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07