一.RBTree(紅黑樹)前言
創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比大悟網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式大悟網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋大悟地區(qū)。費(fèi)用合理售后完善，10余年實(shí)體公司更值得信賴。
map和set容器的底層使用的紅黑樹,?set只存儲(chǔ)值,?map存儲(chǔ)鍵值對(duì)
為了體現(xiàn)復(fù)用思想,?紅黑樹存儲(chǔ)類型統(tǒng)一為K/T模型,?如果是set實(shí)現(xiàn)T則傳K,?map實(shí)現(xiàn)T則傳pair
再通過仿函數(shù)KeyOfT來(lái)取到T中的K類型對(duì)象key
注: 以下只是模擬實(shí)現(xiàn)的迭代器/插入功能
重慶分公司
重慶分公司
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
enum Color
{
RED,
BLACK
};
templatestruct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
Color _col;
T _val;
//構(gòu)造
RBTreeNode(const T& val)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)//默認(rèn)添加的新節(jié)點(diǎn)為紅色
, _val(val)
{}
};
templatestruct Iterator
{
typedef RBTreeNodeNode;
typedef IteratorSelf;
Iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
//return &(_node->_val);
return &(*Iterator(_node));
}
bool operator==(const Self& val)const
{
return _node == val._node;
}
bool operator!=(const Self& val)const
{
return _node != val._node;
}
//前置++
Self& operator++()
{
if (_node->_right != nullptr)
{
//找右節(jié)點(diǎn)為根節(jié)點(diǎn)的最左節(jié)點(diǎn)
Node* left = _node->_right;
while (left->_left != nullptr)
{
left = left->_left;
}
_node = left;
}
else
{
Node* parent = _node->_parent;
Node* cur = _node;
//如果當(dāng)前是父的左,說明還沒走過,下一步要走到父;
//如果當(dāng)前是父的右,說明已經(jīng)走過了,下一步循環(huán)判斷父是爺?shù)淖筮€是右,重復(fù)這個(gè)過程
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
//出循環(huán)說明1.parent為nullptr說明到了end()2.當(dāng)前是父的左
//結(jié)論:下一步都要走到parent
_node = parent;
}
return *this;
}
//前置--
//與前置++邏輯逆置
Self& operator--()
{
if (_node->_left != nullptr)
{
Node* right = _node->_left;
while (right->_right != nullptr)
{
right = right->_right;
}
_node = right;
}
else
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Node* _node;
};
templateclass RBTree
{
public:
typedef RBTreeNodeNode;
typedef Iteratoriterator;
iterator begin()
{
Node* cur = root;
while (cur && cur->_left != nullptr)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
pairinsert(const T& val)
{
KeyOfT key;
if (root == nullptr)
{
//如果此時(shí)為空樹
root = new Node(val);
//將根節(jié)點(diǎn)修正為黑色
root->_col = BLACK;
return make_pair(iterator(root), true);
}
Node* cur = root;
Node* parent = nullptr;//cur的父節(jié)點(diǎn)
while (cur)
{
if (key(cur->_val) >key(val))
{
parent = cur;
cur = cur->_left;
}
else if (key(cur->_val)< key(val))
{
parent = cur;
cur = cur->_right;
}
else
{
//如果插入的節(jié)點(diǎn)是重復(fù)值, 則插入失敗
return make_pair(iterator(cur), false);
}
}
cur = new Node(val);
if (key(parent->_val) >key(cur->_val))
{
parent->_left = cur;
}
else if (key(parent->_val)< key(cur->_val))
{
parent->_right = cur;
}
cur->_parent = parent;
//以上為插入節(jié)點(diǎn)
//-------------------------------------------------------
//以下為調(diào)整為紅黑樹
//因?yàn)槟J(rèn)插入的節(jié)點(diǎn)為紅色,所以如果出現(xiàn)了兩個(gè)連續(xù)為紅的節(jié)點(diǎn)就需要處理
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
Node* uncle = nullptr;
//確定叔叔節(jié)點(diǎn)的位置
if (grandfather->_left == parent)
{
uncle = grandfather->_right;
}
else//grandfather->_right == parent
{
uncle = grandfather->_left;
}
//將分為三種情況
//1.父節(jié)點(diǎn)為紅,叔叔節(jié)點(diǎn)存在且為紅(變色 + 向上迭代)
//2/3.父節(jié)點(diǎn)為紅,叔叔節(jié)點(diǎn)不存在或者存在且為黑(旋轉(zhuǎn) + 變色)
if (uncle && uncle->_col == RED)//情況一
{
//父變黑,叔叔變黑,祖父變紅->向上迭代
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else//情況二/三
{
//情況二
// g
// p u
// c
if (uncle == grandfather->_right && cur == parent->_left)
{
//右單旋
RotateR(grandfather);
//
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
// g
// u p
// c
else if (uncle == grandfather->_left && cur == parent->_right)
{
//左單旋
RotateL(grandfather);
//
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
//情況三
// g
// u p
// c
else if (uncle == grandfather->_left && cur == parent->_left)
{
//左雙旋
RotateRL(grandfather);
//
grandfather->_col = RED;
cur->_col = BLACK;
break;
}
// g
// p u
// c
else if (uncle == grandfather->_right && cur == parent->_right)
{
//右雙旋
RotateLR(grandfather);
//
grandfather->_col = RED;
cur->_col = BLACK;
break;
}
else
{
cout<< "不存在這種情況"<< endl;
exit(-1);
}
}
}
root->_col = BLACK;
return make_pair(iterator(cur), true);
}
void inorder()
{
_inorder(root);
}
bool isRBTree()
{
if (root->_col == RED)
{
cout<< "出錯(cuò): 根節(jié)點(diǎn)為紅"<< endl;
return false;
}
//判斷是否有連續(xù)紅節(jié)點(diǎn),且每條路徑的黑節(jié)點(diǎn)是否相等
int benchmark = 0;//算出最左路徑的黑節(jié)點(diǎn)個(gè)數(shù)
Node* cur = root;
while (cur)
{
if (cur->_col == BLACK)
{
++benchmark;
}
cur = cur->_left;
}
return _isRBTree(root, 0, benchmark);
}
private:
//四種旋轉(zhuǎn)
void RotateL(Node* prev)
{
Node* subR = prev->_right;
Node* subRL = subR->_left;
Node* ppNode = prev->_parent;
prev->_right = subRL;
if (subRL)
{
subRL->_parent = prev;
}
subR->_left = prev;
prev->_parent = subR;
if (root == prev)
{
root = subR;
}
else
{
if (ppNode->_left == prev)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
}
subR->_parent = ppNode;
}
void RotateR(Node* prev)
{
Node* subL = prev->_left;
Node* subLR = subL->_right;
Node* ppNode = prev->_parent;
subL->_right = prev;
prev->_parent = subL;
prev->_left = subLR;
if (subLR)
{
subLR->_parent = prev;
}
if (root == prev)
{
root = subL;
}
else
{
if (ppNode->_left == prev)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
}
subL->_parent = ppNode;
}
void RotateRL(Node* prev)
{
//先右旋, 再左旋
RotateR(prev->_right);
RotateL(prev);
}
void RotateLR(Node* prev)
{
//先左旋, 再右旋
RotateL(prev->_left);
RotateR(prev);
}
void _inorder(Node* root)
{
if (root)
{
_inorder(root->_left);
cout<< root->_kv.first<< "--"<< root->_kv.second<< endl;
_inorder(root->_right);
}
}
bool _isRBTree(Node* root, int blackNum, int benchmark)
{
if (root == nullptr)//走到空節(jié)點(diǎn)
{
if (benchmark == blackNum)
{
//for debug
//cout<< blackNum<< endl;
return true;
}
else
{
//for debug
//cout<< blackNum<< endl;
cout<< "不是所有路徑的黑色節(jié)點(diǎn)個(gè)數(shù)都相同"<< endl;
return false;
}
}
if (root->_col == BLACK)
{
++blackNum;
}
//判斷是否有連續(xù)的紅節(jié)點(diǎn)
if (root->_col == RED && root->_parent->_col == RED)
{
cout<< "出現(xiàn)了連續(xù)的紅色節(jié)點(diǎn)"<< endl;
return false;
}
return _isRBTree(root->_left, blackNum, benchmark)
&& _isRBTree(root->_right, blackNum, benchmark);
}
Node* root = nullptr;
}; #define _CRT_SECURE_NO_WARNINGS 1
#include"RBTree.h"
templateclass Set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename RBTree::iterator iterator;
pairinsert(const K& key)
{
return _t.insert(key);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree_t;
}; #define _CRT_SECURE_NO_WARNINGS 1
#include"RBTree.h"
templateclass Map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair& kv)
{
return kv.first;
}
};
typedef typename RBTree, MapKeyOfT>::iterator iterator;
pairinsert(const pair& kv)
{
return _t.insert(kv);
}
V& operator[](const K& key)
{
pairret = insert(make_pair(key, V()));
return ret.first->second;
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree, MapKeyOfT>_t;
}; 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
