紅黑樹又稱二叉搜索樹，它主要是通過紅和黑兩種顏色（red、black）來標(biāo)識節(jié)點。通過對任何一條從根節(jié)點到葉子節(jié)點路徑上的節(jié)點顏色進(jìn)行約束，紅黑樹保證最長路徑不超過最短路徑的兩倍，所以說：紅黑樹是近似于平衡的。
創(chuàng)新互聯(lián)專注于企業(yè)成都營銷網(wǎng)站建設(shè)、網(wǎng)站重做改版、廣信網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5高端網(wǎng)站建設(shè)、商城網(wǎng)站定制開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為廣信等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。
■下面是紅黑樹的主要特點：
（1）紅黑樹的根節(jié)點是黑色的。
（2）紅黑樹中若一個節(jié)點是紅色的，則它的兩個子節(jié)點必須是黑色的。
（3）紅黑樹中從該節(jié)點到后代葉節(jié)點的路徑上，黑色節(jié)點數(shù)目是相同的。
◆紅黑樹的應(yīng)用：
C++庫、linux內(nèi)核、java庫等
◆紅黑樹與AVL樹的區(qū)別：
紅黑樹和AVL樹都是高效的平衡搜索樹，時間復(fù)雜度都是O(lgN);
紅黑樹對平衡的要求不是特別高，它只需要滿足最長路徑不超過最短路徑的兩倍，所以性能相對較高。
■下面是紅黑樹中節(jié)點結(jié)構(gòu)：
重慶分公司
重慶分公司
enum color //枚舉節(jié)點的兩種顏色
{
RED,
BLACK,
};
template
struct RBTreeNode
{
color _col;
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
K _key;
V _value;
RBTreeNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
, _col(RED) //顏色必須插入的是紅色，因為要保證黑色節(jié)點的個數(shù)是平衡的
{ }
}; ■下面分析紅黑樹的插入情況：
（1）
（2）
（3）
■下面是主要的代碼：
#pragma once
//實現(xiàn)紅黑樹的基本功能
/*
1.紅黑樹中的節(jié)點只能是紅色或者黑色
2.紅黑樹的根節(jié)點為黑色
3.紅黑樹的左、右子樹的黑色節(jié)點個數(shù)是相同的
4.紅黑樹中紅色節(jié)點的兩個孩子節(jié)點必須都為黑色節(jié)點
*/
enum color //枚舉節(jié)點的兩種顏色
{
RED,
BLACK,
};
template
struct RBTreeNode
{
color _col;
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
K _key;
V _value;
RBTreeNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
, _col(RED) //顏色必須插入的是紅色，因為要保證黑色節(jié)點的個數(shù)是平衡的
{ }
};
template
class RBTree
{
typedef RBTreeNode Node;
public:
RBTree()
:_root(NULL)
{}
bool Insert(const K& key, const V& value)
{
if (_root == NULL) //根節(jié)點為空的情況，必須將根節(jié)點置為黑色
{
_root = new Node(key, value);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
break;
}
}
//尋找到數(shù)據(jù)該插入的位置
if (parent->_key < key)
{
Node* tmp = new Node(key, value);
parent->_right = tmp;
tmp->_parent = parent;
}
else if (parent->_key > key)
{
Node* tmp = new Node(key, value);
parent->_left = tmp;
tmp->_parent = parent;
}
//處理(如果父節(jié)點為黑色，則不用對樹進(jìn)行調(diào)整，樹保持紅黑樹的狀態(tài))
while(cur != _root && parent->_col == RED)
//插入的不是根節(jié)點，且父節(jié)點的顏色為紅
{
Node* grandFather = parent->_parent;
if (parent == grandFather->_left)
{
Node* uncle = grandFather->_right;
//情況一：需要將祖父節(jié)點置為紅色，將父親節(jié)點和叔叔節(jié)點置為黑色，
//下次直接從祖父節(jié)點向上進(jìn)行調(diào)整
if (uncle != NULL && uncle->_col == RED)
{
grandFather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
cur = grandFather;
parent = cur->_parent;
}
else
{
//情況二：需要先進(jìn)行右單旋，然后將父親節(jié)點置為黑色，祖父節(jié)點置為紅色
//情況三：需要先進(jìn)行左單旋，然后就會轉(zhuǎn)化為情況二
if (cur == parent->_right && parent->_right != NULL) //情況三左、右
{
_RotateL(parent);
}
parent->_col = BLACK;
grandFather->_col = RED;
_RotateR(grandFather);
}
}
else //父親節(jié)點為祖父節(jié)點的右節(jié)點
{
Node* uncle = grandFather->_left;
//情況一：需要將祖父節(jié)點置為紅色，將父親節(jié)點和叔叔節(jié)點置為黑色，
//下次直接從祖父節(jié)點向上進(jìn)行調(diào)整
if (uncle != NULL && uncle->_col == RED)
{
grandFather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
cur = grandFather;
parent = cur->_parent;
}
else
{
//情況二：需要先進(jìn)行左單旋，然后將父親節(jié)點置為黑色，祖父節(jié)點置為紅色
//情況三：需要進(jìn)行右單旋，然后就會轉(zhuǎn)化為情況二
if (cur == parent->_left && parent->_left != NULL)//情況三右、左
{
_RotateR(parent);
}
parent->_col = BLACK;
grandFather->_col = RED;
_RotateL(grandFather);
}
}
}
_root->_col = BLACK;
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool Check() //檢查是否為紅黑樹
{
int countBlack = 0;
Node* cur = _root;
while (cur->_left != NULL) //統(tǒng)計一條路徑上的黑色節(jié)點的數(shù)目
{
if (cur->_col == BLACK)
{
countBlack++;
}
cur = cur->_left;
}
return _Check(_root, 0, countBlack);
}
protected:
bool _Check(Node* root, int blackNum, int curBalanceNum)
{
if (root == NULL)
{
return false;
}
if (root->_parent != NULL && root->_col == BLACK)
{
if (root->_parent->_col == RED)
{
return true;
}
}
if (root->_left == NULL && root->_right == NULL) //遞歸到葉子節(jié)點是的黑色節(jié)點數(shù)目是否相等
{
if (blackNum == curBalanceNum)
{
return true;
}
else
{
return false;
}
}
return _Check(root->_left, blackNum++, curBalanceNum)
&& _Check(root->_right, blackNum++, curBalanceNum);
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key <<":"<_col<_right);
}
void _RotateL(Node*& parent) //左單旋
{
Node* SubR = parent->_right; //新建兩個節(jié)點指針
Node* SubRL = SubR->_left;
parent->_right = SubRL; //進(jìn)行調(diào)整
if (SubRL)
{
SubRL->_parent = parent;
}
SubR->_left = parent;
SubR->_parent = parent->_parent;
parent->_parent = SubR;
parent = SubR;
if (parent->_parent == NULL) //parent為根節(jié)點的情況
{
_root = parent;
}
else //parent不為根節(jié)點
{
Node* ppNode = parent->_parent;
if (ppNode->_key > parent->_key)
{
ppNode->_left = parent;
}
else
{
ppNode->_right = parent;
}
}
}
void _RotateR(Node*& parent) //右單旋
{
Node* SubL = parent->_left; //新建兩個節(jié)點指針
Node* SubLR = SubL->_right;
parent->_left = SubLR; //進(jìn)行調(diào)整
if (SubLR)
{
SubLR->_parent = parent;
}
SubL->_right = parent;
SubL->_parent = parent->_parent;
parent->_parent = SubL;
parent = SubL;
if (parent->_parent == NULL) //parent為根節(jié)點的情況
{
_root = parent;
}
else //parent不為根節(jié)點
{
Node* ppNode = parent->_parent;
if (ppNode->_key > parent->_key)
{
ppNode->_left = parent;
}
else
{
ppNode->_right = parent;
}
}
}
protected:
Node* _root;
};
void Test()
{
RBTree ht;
ht.Insert(5, 1);
ht.Insert(9, 1);
ht.Insert(3, 1);
ht.Insert(1, 1);
ht.Insert(8, 1);
ht.Insert(2, 1);
ht.Insert(4, 1);
ht.Insert(6, 1);
ht.Insert(7, 1);
ht.InOrder();
cout<
本文題目：二叉搜索樹—RBTree（紅黑樹）
轉(zhuǎn)載注明：http://weahome.cn/article/ihpeeh.html
