C++封裝紅黑樹(shù)以實(shí)現(xiàn)map和set方法詳解
1.源碼及框架分析
SGI-STL30版本源代碼，map和set的源代碼在map/set/stl_map.h/stl_set.h/stl_tree.h等幾個(gè)頭文件中。
map和set的實(shí)現(xiàn)結(jié)構(gòu)框架核心部分截取出來(lái)如下：
//set
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_set.h>
#include <stl_multiset.h>
//map
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_map.h>
#include <stl_multimap.h>
//stl_set.h
template<class Key,class Compare=less<Key>,class Alloc=alloc>
class set{
public:
//typedefs:
typedef Key key_type;
typedef Key value_type;
private:
typedef rb_tree<key_type,value_type,
identity<value_type>,key_compare,Alooc> rep_type;
rep_type t; //red-black tree representing set
};
//stl_map.h
template<class Key,class T,class Compare=less<Key>,class Alloc=alloc>
class map{
public:
//typedefs:
typedef Key key_type;
typedef T mappped_type;
typedef pair<const Key,T> value_type;
private:
typedef rb_tree<key_type,value_type,
selectlst<value_type>,key_compare,Alloc> rep_type;
rep_type t; //red-black tree representing map
};
//stl_tree.h
struct __rb_tree_node_base{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
};
//stl_tree.h
template<class Key,class Value,class KeyOfValue,class Compare,class Alloc=alloc>
class rb_tree{
protected:
typedef void* void_pointer;
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
typedef rb_tree_node* link_type;
typedef Key key_type;
typedef Value value_type;
public:
//insert用的是第二個(gè)模板參數(shù)左形參
pair<iterator,bool> insert_unique(const value_type& x);
//erase和find用第一個(gè)模板參數(shù)做形參
size_type erase(const key_type& x);
iterator find(const key_type& x);
protected:
size_type node_count; //keep track of size of tree
link_type header;
};
template<class Value>
struct __rb_tree_node:public __rb_tree_node_base{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};●通過(guò)下圖對(duì)框架的分析，可以看到源碼中rb_tree用了一個(gè)巧妙的泛型思想實(shí)現(xiàn)，rb_tree是實(shí)現(xiàn)key的搜索場(chǎng)景，還是key/value的搜索場(chǎng)景不是直接寫(xiě)死的，而是由第二個(gè)模板參數(shù)Value決定_rb_tree_node中存儲(chǔ)的數(shù)據(jù)類(lèi)型。
●set實(shí)例化rb_tree時(shí)第二個(gè)模板參數(shù)給的是key，map實(shí)例化rb_tree時(shí)第二個(gè)模板參數(shù)給的是pair<const key,T>，這樣一顆紅黑樹(shù)既可以實(shí)現(xiàn)key搜索場(chǎng)景的set，也可以實(shí)現(xiàn)key/value搜索場(chǎng)景的map。
●要注意，源碼里面模板參數(shù)是用T代表value，而內(nèi)部寫(xiě)的value_type不是我們?nèi)粘ey/value場(chǎng)景中說(shuō)的value，源碼中的value_type反而是紅黑樹(shù)節(jié)點(diǎn)中存儲(chǔ)的真實(shí)的數(shù)據(jù)的類(lèi)型。
●rb_tree第二個(gè)模板參數(shù)Value已經(jīng)控制了紅黑樹(shù)節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)類(lèi)型，為什么還要傳第一個(gè)模板參數(shù)Key呢？尤其是set，兩個(gè)模板參數(shù)是一樣的。要注意的是對(duì)于map和set，find/erase時(shí)的函數(shù)參數(shù)都是Key，所以第一個(gè)模板參數(shù)是傳給find/erase等函數(shù)做形參的類(lèi)型的。對(duì)于set而言?xún)蓚€(gè)參數(shù)是一樣的，但是對(duì)于map而言就完全不一樣l，map insert的pair對(duì)象，但是find和erase的是Key對(duì)象。
●這里的源碼命名風(fēng)格比較亂，set模板參數(shù)用的是Key命名，map用的是Key和T命名，而rb_tree用的又是Key和Value。
2.模擬實(shí)現(xiàn)map和set
2.1實(shí)現(xiàn)出復(fù)用紅黑樹(shù)的框架，并支持insert
●參考源碼框架，map和set復(fù)用之前我們實(shí)現(xiàn)的紅黑樹(shù)。
●以下調(diào)整，key參數(shù)用K代替，value參數(shù)用V代替，紅黑樹(shù)中的數(shù)據(jù)類(lèi)型，使用T。
●因?yàn)镽BTree實(shí)現(xiàn)了泛型不知道T參數(shù)導(dǎo)致是K，還是pair<K,V>，那么insert內(nèi)部進(jìn)行插入邏輯比較時(shí)，就沒(méi)辦法進(jìn)行比較，因?yàn)閜air的默認(rèn)支持的是key和value一起參入比較，需要時(shí)的任何時(shí)候只比較key，所以在map和set層分別實(shí)現(xiàn)一個(gè)MapKeyOfT和SetKeyOfT的仿函數(shù)傳給RBTree的KeyOfT，然后RBTree中通過(guò)KeyOfT仿函數(shù)取出T類(lèi)型對(duì)象中的key，再進(jìn)行比較。
namespace Achieve{
template<class K>
class set{
struct SetKeyOfT{
const K& operator()(const K& key){
return key;
}
};
public:
bool insert(const K& key){
return _t.Insert(key);
}
private:
RBTree<K,K,SetKeyOfT> _t;
};
}
namespace Achieve{
template<class K,class V>
class map{
struct MapKeyOfT{
const K& operator()(const pair<K,V>& key){
return key.first;
}
};
public:
bool insert(const pair<K,V>& kv){
return _t.Insert(kv);
}
private:
RBTree<K,pair<K,V>,MapKeyOfT> _t;
};
}
enum Color{
RED,BLACK
};
template<class T>
struct RBTreeNode{
//需要parent指針
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//記錄紅黑
Color _color;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
};
//實(shí)現(xiàn)步驟：
//1.實(shí)現(xiàn)紅黑樹(shù)
//2.封裝map和set框架，解決KeyOfT
//3.iterator
//4.const_iterator
//5.key不支持修改的問(wèn)題
//6.operator[]
template<class k,class T,class KeyOfT>
class RBTree{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& data){
if(!_root){
_root=new Node(data);
//根節(jié)點(diǎn)必須為黑色
_root->_color=BLACK;
return true;
}
KeyOfT kot;
Node* parent=nullptr;
Node* cur=_root;
while(cur){
if(kot(cur->_data)<kot(data)){
parent=cur;
cur=cur->_right;
}
else if(kot(cur->_data)>kot(data)){
parent=cur;
cur=cur->_left;
}
else return false;
}
//開(kāi)始插入
cur=new Node(data);
//提前記錄當(dāng)前節(jié)點(diǎn)
Node* newNode=cur;
cur->_color=RED;
if(kot(cur->_data)<kot(parent->_data))
parent->_left=cur;
else parent->_right=cur;
//父指針指向父節(jié)點(diǎn)
cur->_parent=parent;
//當(dāng)父節(jié)點(diǎn)存在，且與新插入節(jié)點(diǎn)構(gòu)成連續(xù)紅色時(shí)
while(parent&&parent->_color==RED){
Node* grandfather=parent->_parent;
//若父節(jié)點(diǎn)在爺節(jié)點(diǎn)的左邊
if(parent==grandfather->_left){
// g
//p u
Node* uncle=grandfather->_right;
//若u存在且為紅色,變色
if(uncle&&uncle->_color==RED){
parent->_color=uncle->_color=BLACK;
grandfather->_color=RED;
//將c更新到g，繼續(xù)操作
cur=grandfather;
parent=cur->_parent;
}
//此時(shí)u不存在或?yàn)楹谏?
else{
//當(dāng)插入的cur在parent的左邊
if(cur==parent->_left){
// g
// p u
//c
RotateR(grandfather);
parent->_color=BLACK;
grandfather->_color=RED;
}
//當(dāng)插入的cur在parent的右邊
else {
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
parent->_color=BLACK;
grandfather->_color=RED;
}
break;
}
}
//當(dāng)父節(jié)點(diǎn)在爺爺?shù)挠疫?
else{
// g
//u p
Node* uncle=grandfather->_left;
//若u存在且為紅色,變色
if(uncle&&uncle->_color==RED){
parent->_color=uncle->_color=BLACK;
grandfather->_color=RED;
//將c更新到g，繼續(xù)操作
cur=grandfather;
parent=cur->_parent;
}
//此時(shí)u不存在或?yàn)楹谏?
else{
//當(dāng)插入的cur在parent的右邊
if(cur==parent->_right){
// g
// u p
// c
RotateL(grandfather);
parent->_color=BLACK;
grandfather->_color=RED;
}
//當(dāng)插入的cur在parent的左邊
else {
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
parent->_color=BLACK;
grandfather->_color=RED;
}
break;
}
}
}
//根節(jié)點(diǎn)必須為黑色
_root->_color=BLACK;
return true;
}
//右單旋
void RotateR(Node* parent){
Node* subL=parent->_left;
Node* subLR=subL->_right;
parent->_left=subLR;
//鏈接父節(jié)點(diǎn)
if(subLR)
subLR->_parent=parent;
//防止找不到父結(jié)點(diǎn)的父結(jié)點(diǎn)
Node* pparent=parent->_parent;
subL->_right=parent;
parent->_parent=subL;
if(parent==_root){
_root=subL;
subL->_parent=nullptr;
}
else{
if(pparent->_left==parent)
pparent->_left=subL;
else pparent->_right=subL;
subL->_parent=pparent;
}
}
//左單旋
void RotateL(Node* parent){
Node* subR=parent->_right;
Node* subRL=subR->_left;
parent->_right=subRL;
//鏈接父節(jié)點(diǎn)
if(subRL)
subRL->_parent=parent;
//防止找不到父結(jié)點(diǎn)的父結(jié)點(diǎn)
Node* pparent=parent->_parent;
subR->_left=parent;
parent->_parent=subR;
if(pparent==nullptr){
_root=subR;
subR->_parent=nullptr;
}
else{
if(parent==pparent->_left)
pparent->_left=subR;
else pparent->_right=subR;
subR->_parent=pparent;
}
}
private:
Node* _root=nullptr;
};2.2支持iterator的實(shí)現(xiàn)
2.2.1iterator核心源代碼
struct __rb_base_iterator{
typedef __rb_tree_node_base::base_ptr base_ptr;
base_ptr node;
void increment(){
if(node->right!=){
node=node->right;
while(node->left!=0)
node=node->left;
}
else{
base_ptr y=node->parent;
while(node==y->right){
node=y;
y=y->parent;
}
if(node->right!=y)
node=y;
}
}
void decrement(){
if(node->color==__rb_tree_red&&node->parent->parent==node)
node=node->right;
else if(node->left!=0){
base_ptr y=node->left;
while(y->right!=0)
y=y->right;
node=y;
}
else {
base_ptr y=node->parent;
while(node==y->left){
node=y;
y=y->parent;
}
node=y;
}
}
};2.2.2iterator實(shí)現(xiàn)思路分析
●iterator實(shí)現(xiàn)的大框架跟list的iterator思路是一致的，用一個(gè)類(lèi)型封裝節(jié)點(diǎn)的指針，再通過(guò)重載運(yùn)算符實(shí)現(xiàn)，迭代器像指針一樣訪(fǎng)問(wèn)的行為。
●operator++和operator--的實(shí)現(xiàn)。map和set的迭代器走的是中序遍歷，左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)，那么begin()會(huì)返回中序第一個(gè)節(jié)點(diǎn)的iterator也就是10所在節(jié)點(diǎn)的迭代器。
●迭代器的++核心邏輯就是不看全局，只看局部，只考慮當(dāng)前中序局部要訪(fǎng)問(wèn)的下一個(gè)節(jié)點(diǎn)（左中右）。
●迭代器++時(shí)，若it指向的節(jié)點(diǎn)的右子樹(shù)不為空，代表當(dāng)前節(jié)點(diǎn)已經(jīng)訪(fǎng)問(wèn)完了，要訪(fǎng)問(wèn)下一個(gè)節(jié)點(diǎn)是右子樹(shù)的中序第一個(gè)，一棵樹(shù)中序第一個(gè)是最左節(jié)點(diǎn)，所以直接找右子樹(shù)的最左節(jié)點(diǎn)即可。
●迭代器++時(shí)，若it指向的節(jié)點(diǎn)的右子樹(shù)為空，代表當(dāng)前節(jié)點(diǎn)已經(jīng)訪(fǎng)問(wèn)完了且當(dāng)前節(jié)點(diǎn)所在的子樹(shù)也訪(fǎng)問(wèn)完了，要訪(fǎng)問(wèn)的下一個(gè)節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)祖先里面，所以要沿當(dāng)前節(jié)點(diǎn)到根的祖先路徑向上找。
●若當(dāng)前節(jié)點(diǎn)是父親的左，根據(jù)中序左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)，則下一個(gè)訪(fǎng)問(wèn)的節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)的父親；若下圖：it指向25，25右為空，25是30的左，所以下一個(gè)訪(fǎng)問(wèn)的節(jié)點(diǎn)就是30。
●若當(dāng)前節(jié)點(diǎn)是父親的右，根據(jù)中序左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)，當(dāng)前節(jié)點(diǎn)所在的子樹(shù)訪(fǎng)問(wèn)完了，當(dāng)前節(jié)點(diǎn)所在父親的子樹(shù)也訪(fǎng)問(wèn)完了，那么下一個(gè)訪(fǎng)問(wèn)的需要繼續(xù)往根的祖先中去找，直到找到孩子是父親左的那個(gè)祖先就是中序要訪(fǎng)問(wèn)的下一個(gè)節(jié)點(diǎn)。如下圖：it指向15，15右為空，15是10的右，15所在子樹(shù)訪(fǎng)問(wèn)完了，10所在子樹(shù)也訪(fǎng)問(wèn)完了，繼續(xù)向上找，10是18的左，那么下一個(gè)訪(fǎng)問(wèn)的節(jié)點(diǎn)就是18.
●end（）如何表示？如下圖：當(dāng)it指向50時(shí)，++it時(shí)，50是40的右，40是30的右，30是18的右，18到根沒(méi)有父親，沒(méi)有找到孩子是父親左的那個(gè)祖先，這是父親為空了，那我們就把it中的節(jié)點(diǎn)指針置為nullptr，用nullptr去充當(dāng)end。需要注意的是stl源碼空時(shí)，紅黑樹(shù)增加了一個(gè)哨兵位頭節(jié)點(diǎn)作為end（），這哨兵位頭節(jié)點(diǎn)和根互為父親，左指向最左節(jié)點(diǎn)，右指向最右節(jié)點(diǎn)。相比用nullptr作為end（），差別不大。只是--end（）判斷到節(jié)點(diǎn)時(shí)空，特殊處理以下，讓迭代器節(jié)點(diǎn)指向最右節(jié)點(diǎn)。
2.3map支持[]
●map要支持[]主要修改insert返回值，修改RBTree中的Insert返回值為pair<Iterator,bool> Insert(const T& data)
2.4Achieve::map和Achieve::set代碼實(shí)現(xiàn)
namespace Achieve{
template<class K>
class set{
struct SetKeyOfT{
const K& operator()(const K& key){
return key;
}
};
public:
//typename明確Iterator是一個(gè)類(lèi)型
typedef typename RBTree<K,const K,SetKeyOfT>::Iterator iterator;//Key不能修改，否則樹(shù)會(huì)出錯(cuò)
typedef typename RBTree<K,const K,SetKeyOfT>::ConstIterator const_iterator;
iterator begin(){
return _t.Begin();
}
iterator end(){
return _t.End();
}
const_iterator begin() const{
return _t.Begin();
}
const_iterator end() const{
return _t.End();
}
pair<iterator,bool> insert(const K& key){
return _t.Insert(key);
}
private:
RBTree<K,const K,SetKeyOfT> _t;
};
}
namespace Achieve{
template<class K,class V>
class map{
struct MapKeyOfT{
const K& operator()(const pair<K,V>& key){
return key.first;
}
};
public:
//typename明確Iterator是一個(gè)類(lèi)型
typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::Iterator iterator;//Key不能修改，否則樹(shù)會(huì)出錯(cuò)
typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::ConstIterator const_iterator;
iterator begin(){
return _t.Begin();
}
iterator end(){
return _t.End();
}
const_iterator begin() const{
return _t.Begin();
}
const_iterator end() const{
return _t.End();
}
pair<iterator,bool> insert(const pair<K,V>& kv){
return _t.Insert(kv);
}
V& operator[](const K& key){
pair<iterator,bool> ret=insert({key,V()});
return ret.first->second;
}
private:
RBTree<K,pair<const K,V>,MapKeyOfT> _t;
};
}
enum Color{
RED,BLACK
};
template<class T>
struct RBTreeNode{
//需要parent指針
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//記錄紅黑
Color _color;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
};
template<class T,class Ref,class Ptr>
struct RBIterator{
typedef RBTreeNode<T> Node;
typedef RBIterator<T,Ref,Ptr> Self;
Node* _node;
Node* _root;
RBIterator(Node* node,Node* root)
:_node(node)
,_root(root)
{}
Self operator++(){
//中序遍歷，下一個(gè)節(jié)點(diǎn)為右子樹(shù)的最小節(jié)點(diǎn)
if(_node->_right){
Node* min=_node->_right;
while(min->_left){
min=min->_left;
}
_node=min;
}
else{
//右為空，祖先里面孩子是父親左的那個(gè)祖先
Node* cur=_node;
Node* parent=cur->_parent;
while(parent&&cur==parent->_right){
cur=parent;
parent=parent->_parent;
}
_node=parent;
}
return *this;
}
Self operator--(){
if(_node==nullptr){//--end()
//--end()，特殊處理，走到中序最后一個(gè)節(jié)點(diǎn)，樹(shù)的最右節(jié)點(diǎn)
Node* rightMost=_root;
while(rightMost&&rightMost->_right){
rightMost=rightMost->_right;
}
_node=rightMost;
}
//中序遍歷，上一個(gè)節(jié)點(diǎn)為左子樹(shù)的最右節(jié)點(diǎn)
if(_node->_left){
Node* max=_node->_left;
while(max->_right){
max=max->_right;
}
_node=max;
}
else{
//孩子是父親右的那個(gè)祖先
Node* cur=_node;
Node* parent=cur->_parent;
while(parent&&cur==parent->_left){
cur=parent;
parent=parent->_parent;
}
_node=parent;
}
return *this;
}
Ref operator*(){
return _node->_data;
}
Ptr operator->(){
return &_node->_data;
}
bool operator==(const Self& s) const{
return _node==s._node;
}
bool operator!=(const Self& s) const{
return _node!=s._node;
}
};
template<class k,class T,class KeyOfT>
class RBTree{
typedef RBTreeNode<T> Node;
public:
typedef RBIterator<T,T&,T*> Iterator;
typedef RBIterator<T,const T&,const T*> ConstIterator;
Iterator Begin(){
Node* cur=_root;
while(cur&&cur->_left){
cur=cur->_left;
}
return Iterator(cur,_root);
}
ConstIterator Begin() const{
Node* cur=_root;
while(cur&&cur->_left){
cur=cur->_left;
}
return ConstIterator(cur,_root);
}
Iterator End(){
return Iterator(nullptr,_root);
}
ConstIterator End() const{
return ConstIterator(nullptr,_root);
}
RBTree()=default;
~RBTree(){
Destroy(_root);
_root=nullptr;
}
pair<Iterator,bool> Insert(const T& data){
if(!_root){
_root=new Node(data);
//根節(jié)點(diǎn)必須為黑色
_root->_color=BLACK;
return {Iterator(_root,_root),true};
}
KeyOfT kot;
Node* parent=nullptr;
Node* cur=_root;
while(cur){
if(kot(cur->_data)<kot(data)){
parent=cur;
cur=cur->_right;
}
else if(kot(cur->_data)>kot(data)){
parent=cur;
cur=cur->_left;
}
else return {Iterator(cur,_root),false};
}
//開(kāi)始插入
cur=new Node(data);
//提前記錄當(dāng)前節(jié)點(diǎn)
Node* newNode=cur;
cur->_color=RED;
if(kot(cur->_data)<kot(parent->_data))
parent->_left=cur;
else parent->_right=cur;
//父指針指向父節(jié)點(diǎn)
cur->_parent=parent;
//當(dāng)父節(jié)點(diǎn)存在，且與新插入節(jié)點(diǎn)構(gòu)成連續(xù)紅色時(shí)
while(parent&&parent->_color==RED){
Node* grandfather=parent->_parent;
//若父節(jié)點(diǎn)在爺節(jié)點(diǎn)的左邊
if(parent==grandfather->_left){
// g
//p u
Node* uncle=grandfather->_right;
//若u存在且為紅色,變色
if(uncle&&uncle->_color==RED){
parent->_color=uncle->_color=BLACK;
grandfather->_color=RED;
//將c更新到g，繼續(xù)操作
cur=grandfather;
parent=cur->_parent;
}
//此時(shí)u不存在或?yàn)楹谏?
else{
//當(dāng)插入的cur在parent的左邊
if(cur==parent->_left){
// g
// p u
//c
RotateR(grandfather);
parent->_color=BLACK;
grandfather->_color=RED;
}
//當(dāng)插入的cur在parent的右邊
else {
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
parent->_color=BLACK;
grandfather->_color=RED;
}
break;
}
}
//當(dāng)父節(jié)點(diǎn)在爺爺?shù)挠疫?
else{
// g
//u p
Node* uncle=grandfather->_left;
//若u存在且為紅色,變色
if(uncle&&uncle->_color==RED){
parent->_color=uncle->_color=BLACK;
grandfather->_color=RED;
//將c更新到g，繼續(xù)操作
cur=grandfather;
parent=cur->_parent;
}
//此時(shí)u不存在或?yàn)楹谏?
else{
//當(dāng)插入的cur在parent的右邊
if(cur==parent->_right){
// g
// u p
// c
RotateL(grandfather);
parent->_color=BLACK;
grandfather->_color=RED;
}
//當(dāng)插入的cur在parent的左邊
else {
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
parent->_color=BLACK;
grandfather->_color=RED;
}
break;
}
}
}
//根節(jié)點(diǎn)必須為黑色
_root->_color=BLACK;
return {Iterator(newNode,_root),true};
}
//右單旋
void RotateR(Node* parent){
Node* subL=parent->_left;
Node* subLR=subL->_right;
parent->_left=subLR;
//鏈接父節(jié)點(diǎn)
if(subLR)
subLR->_parent=parent;
//防止找不到父結(jié)點(diǎn)的父結(jié)點(diǎn)
Node* pparent=parent->_parent;
subL->_right=parent;
parent->_parent=subL;
if(parent==_root){
_root=subL;
subL->_parent=nullptr;
}
else{
if(pparent->_left==parent)
pparent->_left=subL;
else pparent->_right=subL;
subL->_parent=pparent;
}
}
//左單旋
void RotateL(Node* parent){
Node* subR=parent->_right;
Node* subRL=subR->_left;
parent->_right=subRL;
//鏈接父節(jié)點(diǎn)
if(subRL)
subRL->_parent=parent;
//防止找不到父結(jié)點(diǎn)的父結(jié)點(diǎn)
Node* pparent=parent->_parent;
subR->_left=parent;
parent->_parent=subR;
if(pparent==nullptr){
_root=subR;
subR->_parent=nullptr;
}
else{
if(parent==pparent->_left)
pparent->_left=subR;
else pparent->_right=subR;
subR->_parent=pparent;
}
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
Node* Find(const k& key){
Node* cur=_root;
KeyOfT kot;
while(cur){
if(kot(cur->_data)<key){
cur=cur->_right;
}
else if(kot(cur->_data>key)){
cur=cur->_left;
}
else return cur;
}
return nullptr;
}
private:
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
void Destroy(Node* root){
if(!root)
return ;
Destory(root->_left);
Destory(root->_right);
delete root;
}
private:
Node* _root=nullptr;
};以上就是C++封裝紅黑樹(shù)以實(shí)現(xiàn)map和set方法詳解的詳細(xì)內(nèi)容，更多關(guān)于C++封裝紅黑樹(shù)實(shí)現(xiàn)map和set的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要簡(jiǎn)單介紹了C++中變量的引用,是C++入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
VScode配置C語(yǔ)言環(huán)境完整版(親測(cè)可用)
這篇文章主要介紹了VScode配置C語(yǔ)言環(huán)境完整版，本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-08-08
本文粗淺比較了C語(yǔ)言中常用的幾種讀取文件的函數(shù)的效率，并給出了幾段求取某列平均值的代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多度進(jìn)步2022-02-02
棧是一種特殊的線(xiàn)性表，只允許從一端進(jìn)出數(shù)據(jù)，稱(chēng)為后進(jìn)先出，先進(jìn)后出。本文主要為大家介紹了C語(yǔ)言實(shí)現(xiàn)棧的示例代碼，感興趣的可以了解一下2022-06-06
這篇文章主要為大家介紹了C++?opencv數(shù)字圖像處理圖像平滑濾波器的使用示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
c++動(dòng)態(tài)內(nèi)存空間示例(自定義空間類(lèi)型大小和空間長(zhǎng)度)
這篇文章主要介紹了c++動(dòng)態(tài)內(nèi)存空間示例,自定義空間類(lèi)型大小和空間長(zhǎng)度,需要的朋友可以參考下2014-04-04
C++實(shí)現(xiàn)含附件的郵件發(fā)送功能
