建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
RBTree（紅黑樹）--C++-創(chuàng)新互聯(lián)
紅黑樹是滿足下面性質(zhì)的二叉搜索樹
1. 每個節(jié)點，不是紅色就是黑色的
2. 根節(jié)點是黑色的
3. 如果一個節(jié)點是紅色的，則它的兩個子節(jié)點是黑色的
4. 對每個節(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點。
#pragma once
enum Color{ RED, BLACK };
template
struct RBtreeNode
{
RBtreeNode(const K& key, const V& v, Color col = RED)
:_left(NULL)
, _right(NULL)
, _parent(NULL)
, _key(key)
, _vlaue(v)
, _col(col)
{}
RBtreeNode* _left;
RBtreeNode* _right;
RBtreeNode* _parent;
K _key;
V _vlaue;
Color _col;
};
template
class RBtree
{
typedef RBtreeNode Node;
public:
RBtree()
:_root(NULL)
{}
bool Insert(const K& key, const V& v)
{
if (_root == NULL)
{
_root = new Node(key, v, BLACK);
return true;
}
Node* parent = NULL;
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key, v, RED);
if (key < parent->_key)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//調(diào)色
while (cur != _root && parent->_col == RED)
{
Node* GrandParent = parent->_parent;
if (parent == GrandParent->_left)//往左子樹插
{
Node* uncle = GrandParent->_right;
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
GrandParent->_col = RED;
cur = GrandParent;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
_RotateL(parent);
swap(cur, parent);
}
_RotateR(GrandParent);
parent->_col = BLACK;
GrandParent->_col = RED;
}
}
else//往右子樹插
{
Node*uncle = GrandParent->_left;
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
GrandParent->_col = RED;
cur = GrandParent;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
_RotateR(parent);
swap(cur, parent);
}
_RotateL(GrandParent);
parent->_col = BLACK;
GrandParent->_col = RED;
}
}
}
_root->_col = BLACK;
return true;
}
bool IsBalanceTree()
{
return _IsBalance(_root);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
protected:
int _Height(Node* root)
{
if (root == NULL)
{
return 0;
}
int left = _Height(root->_left) + 1;
int right = _Height(root->_right) + 1;
return (left > right) ? left : right;
}
bool _IsBalance(Node* root)
{
if (root == NULL)
{
return true;
}
int left = _Height(root->_left);
int right = _Height(root->_right);
int bf = abs(left - right);
if (bf > 1)
{
return false;
}
return _IsBalance(root->_left) && _IsBalance(root->_right);
}
void _RotateL(Node* parent)
{
Node *subR = parent->_right;
Node *subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
subR->_parent = parent->_parent;
parent->_parent = subR;
parent = subR;
//連爸爸:)
if (parent->_parent == NULL)
{
_root = parent;
}
else
{
if (parent->_parent->_key < parent->_key)
{
parent->_parent->_right = parent;
}
else
{
parent->_parent->_left = parent;
}
}
}
void _RotateR(Node* parent)
{
Node *subL = parent->_left;
Node *subLR = subL->_right;
parent->_left = subLR;
if (subLR != NULL)
{
subLR->_parent = parent;
}
subL->_right = parent;
subL->_parent = parent->_parent;
parent->_parent = subL;
parent = subL;
if (parent->_parent == NULL)
{
_root = parent;
}
else
{
if (parent->_parent->_key < parent->_key)
{
parent->_parent->_right = parent;
}
else
{
parent->_parent->_left = parent;
}
}
}
void _InOrder(Node*& root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
protected:
Node* _root;
};
void TestRBTree1()
{
RBtree t1;
int a[10] = { 5, 2, 9, 6, 7, 3, 4, 0, 1, 8 };
for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i)
{
t1.Insert(a[i], i);
t1.InOrder();
}
cout << "IsBalanceTree ? "<< t1.IsBalanceTree() << endl;
} 另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
分享標題：RBTree（紅黑樹）--C++-創(chuàng)新互聯(lián)
當前網(wǎng)址：http://fisionsoft.com.cn/article/ijipi.html
