概念

• 紅黑樹不僅僅是一個(gè)二叉樹，必須滿足如下條件
• 1，每個(gè)節(jié)點(diǎn)不是紅色就是黑色 (深色底紋為黑色，淺色底紋為紅色)
• 2，根節(jié)點(diǎn)是黑色的
• 3，如果節(jié)點(diǎn)為紅，其子節(jié)點(diǎn)必須為黑色的
• 4，任一節(jié)點(diǎn)至NULL(樹的尾端)的任何路徑，所含的黑節(jié)點(diǎn)的數(shù)量必須相同

插入節(jié)點(diǎn)

• 分別插入 3 8 35? 75 ，他們均破壞了紅黑樹的規(guī)則，需要調(diào)整樹形，兩種方式(修改顏色 或 旋轉(zhuǎn))

?

• 產(chǎn)生不平衡的狀態(tài)，即高度相差1以上。這沒關(guān)系，因?yàn)镽B-Tree是一種弱平衡性，他是按照顏色進(jìn)行高度的限定，保證在弱平衡的前提下實(shí)現(xiàn)和AVL幾乎相等的搜尋效率?

?

由上而下的程序

• 主要的目的是為了避免情況四 “父子節(jié)點(diǎn)皆為紅色的”的情形，造成了處理上時(shí)間的瓶頸
• 實(shí)現(xiàn)一個(gè)由上到下的程序，主要目的是檢測(cè)節(jié)點(diǎn) X 的兩個(gè)孩子節(jié)點(diǎn)是不是紅色，如果都是紅色就將自己改為紅色，將孩子節(jié)點(diǎn)改為 黑色
• 如圖所示

• 出現(xiàn)新的問(wèn)題，p節(jié)點(diǎn)為紅色，考慮到父子節(jié)點(diǎn)不能同時(shí)為紅色(此時(shí)S絕對(duì)不能為紅色)，此刻就像情況一一樣需要進(jìn)行一次但旋轉(zhuǎn)并改變顏色，或者做一次雙旋轉(zhuǎn)并改變顏色
• 然后 節(jié)點(diǎn)插入就很單純了，直接插入 或者 插入后在進(jìn)行一次旋轉(zhuǎn)

RB-Tree的節(jié)點(diǎn)設(shè)計(jì)

• RB-tree有紅黑兩色 并且擁有左右兩個(gè)子節(jié)點(diǎn)
• 為了具備彈性，節(jié)點(diǎn)分為兩層，如圖所示節(jié)點(diǎn)的雙層結(jié)構(gòu)和迭代器的雙層結(jié)構(gòu)的關(guān)系?
• minmum() maximum()函數(shù) 可以清楚的看到RB-Tree作為一個(gè)二叉搜索樹，很方便查找極值。
• 考慮到RB-Tree各種操作需要上溯到其父節(jié)點(diǎn)，因此在數(shù)據(jù)結(jié)構(gòu)中安排了一個(gè)parent指針

typedef bool __rb_tree_color_type; const __rb_tree_color_type __rb_tree_red = false; //紅色為0 const __rb_tree_color_type __rb_tree_black = true; //黑色為1struct __rb_tree_node_base{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr;color_type color; //節(jié)點(diǎn)顏色 非紅即黑base_ptr parent; //RB-Tree的許多操作 都是需要父節(jié)點(diǎn)的參與base_ptr left; //指向左節(jié)點(diǎn)base_ptr right; //指向右節(jié)點(diǎn)static base_ptr minimum(base_ptr x){while (x->left != 0){//二叉搜索樹的特性//一直向左走 就會(huì)找到最小值x = x->left;}return x;}static base_ptr maximum(base_ptr x){while(x->right != 0){//二叉搜索樹的特性//一直向右走 就會(huì)找到最大值x = x->right;}return x;} };template <class Value> struct __rb_tree_node : public __rb_tree_node_base{typedef __rb_tree_node<Value>* link_type;Value value_field; //節(jié)點(diǎn)值 };

?RB-Tree的迭代器

• RB-Tree的節(jié)點(diǎn)和迭代器都使用struct完成，主要目的是struct默認(rèn)使用public，可以被外界自由取用
• 迭代器設(shè)置為雙層結(jié)構(gòu)?

• RB-Tree屬于雙向迭代器，但是不具備隨機(jī)定位的能力，其提領(lǐng)操作和成員訪問(wèn)和list十分類似。較為特殊的是前進(jìn)和后退操作。
• RB-Tree迭代器前進(jìn)操作operator++ 調(diào)用了基層的increment；RB-Tree迭代器的后退操作operator--調(diào)用了基層的decrement；

//基層迭代器 struct __rb_tree_base_iterator{typedef __rb_tree_node_base::base_ptr base_ptr;typedef std::bidirectional_iterator_tag iterator_category;typedef ptrdiff_t difference_type;base_ptr node; //用于和容器之間產(chǎn)生一個(gè)連接關(guān)系(make a reference)//以下實(shí)現(xiàn)于operator++內(nèi)，因?yàn)樵贌o(wú)其他地方會(huì)調(diào)用這個(gè)函數(shù)了void increment(){if (node->right != 0){ //如果有右節(jié)點(diǎn)，狀況一node = node->right; //就向右走while(node->left != 0){ //然后一直往左子樹前進(jìn)node = node->left; //即為答案}} else{ //沒有右節(jié)點(diǎn) 狀況二base_ptr y = node->parent;//找出父節(jié)點(diǎn)while(node == y->right){ //如果現(xiàn)行節(jié)點(diǎn)本身是個(gè)右子節(jié)點(diǎn)node = y; //需要一直上溯 直到不為右子節(jié)點(diǎn)為止y = y->parent;}if (node->right != y){ //如果此時(shí)node的右子節(jié)點(diǎn)不等于此時(shí)的父節(jié)點(diǎn)node = y; //狀況三 此時(shí)的父節(jié)點(diǎn)即為解答} //否則 此時(shí)的node即為解答 狀況四}/*以上判斷 "若此時(shí)的右子節(jié)點(diǎn)不等于此時(shí)的父節(jié)點(diǎn)"是為了應(yīng)對(duì)一種特殊的情況* 即：欲尋找的根節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，而此時(shí)根節(jié)點(diǎn)恰好沒有右子節(jié)點(diǎn)* 當(dāng)然，上述的特殊做法需要配合RB-Tree根節(jié)點(diǎn)和特殊的header之間的特殊的關(guān)系*/}//以下實(shí)現(xiàn)于operator--內(nèi)，因?yàn)樵贌o(wú)其他地方會(huì)調(diào)用這個(gè)函數(shù)了void decrement(){//狀況一//如果是紅節(jié)點(diǎn) 且 父節(jié)點(diǎn)的父節(jié)點(diǎn)等于自己 右子節(jié)點(diǎn)即為答案//狀況一 發(fā)生于node為header的時(shí)候(亦即node為end()時(shí))//注意：header的右子節(jié)點(diǎn) 即 mostright指向整棵樹的max節(jié)點(diǎn)if (node->color == __rb_tree_red && node->right->right == node){node = node->right;}//狀況二//如果有左子節(jié)點(diǎn) 令y指向左子節(jié)點(diǎn)；只有當(dāng)y有右子節(jié)點(diǎn)的時(shí)候 一直往右走 到底，最后即為答案else if (node->left!=0){base_ptr y = node->left;while (y->right != 0){y = y->right;}node = y;} else{//狀況三//既不是根節(jié)點(diǎn) 也沒有左節(jié)點(diǎn)//找出父節(jié)點(diǎn)，當(dāng)現(xiàn)行的節(jié)點(diǎn)身為左子節(jié)點(diǎn)時(shí)，一直交替往上走，直到現(xiàn)行節(jié)點(diǎn)不是左節(jié)點(diǎn)為止base_ptr y = node->parent;while(node == y->left){node = y;y = y->right;}node = y; //此時(shí)父節(jié)點(diǎn)即為答案}} };//RB-Tree的正規(guī)迭代器 template <class Value,class Ref,class Ptr> struct __rb_tree_iterator : public __rb_tree_base_iterator{typedef Value value_type;typedef Ref reference;typedef Ptr pointer;typedef __rb_tree_iterator<Value,Value&,Value*> iterator;typedef __rb_tree_iterator<Value,const Value&,const Value*> const_iterator;typedef __rb_tree_iterator<Value,Value&,Value*> self;typedef __rb_tree_node<Value>* link_type;__rb_tree_iterator(){}__rb_tree_iterator(link_type x){node = x;}__rb_tree_iterator(const iterator& it){node = it.node;}reference operator* () const {return link_type(node)->value_field; }#ifndef __SGI_STL_NO_ARROW_OPERATORreference operator->()const {return &(operator*());} #endif //__SGI_STL_NO_ARROW_OPERATORself& operator++(){increment();return *this;}self operator++(int){self tmp = *this;increment();return tmp;}self& operator--(){decrement();return *this;}self operator--(int){self tmp = *this;decrement();return tmp;}};

RB-tree數(shù)據(jù)結(jié)構(gòu)

• 使用專屬的空間配置器，每次配置一個(gè)節(jié)點(diǎn)的大小
• 也可以定義各種型別的定義，用于維護(hù)RB-Tree的三筆數(shù)據(jù)
• 定義一個(gè)仿函數(shù)用于實(shí)現(xiàn)節(jié)點(diǎn)大小的比較

?

template<class T,class Alloc> class simple_alloc{ public:static T* allocate(std::size_t n){return 0==n?0:(T*)Alloc::allocate(n * sizeof(T));}static T* allocate(void){return (T*)Alloc::allocate(sizeof (T));}static void deallocate(T* p,size_t n){if (n!=0){Alloc::deallocate(p,n * sizeof(T));}}static void deallocate(T* p){Alloc::deallocate(p,sizeof(T));} };namespace Chy{template <class T>inline T* _allocate(ptrdiff_t size,T*){std::set_new_handler(0);T* tmp = (T*)(::operator new((std::size_t)(size * sizeof (T))));if (tmp == 0){std::cerr << "out of memory" << std::endl;exit(1);}return tmp;}template<class T>inline void _deallocate(T* buffer){::operator delete (buffer);}template<class T1,class T2>inline void _construct(T1 *p,const T2& value){new(p) T1 (value); //沒看懂}template <class T>inline void _destroy(T* ptr){ptr->~T();}template <class T>class allocator{public:typedef T value_type;typedef T* pointer;typedef const T* const_pointer;typedef T& reference;typedef const T& const_reference;typedef std::size_t size_type;typedef ptrdiff_t difference_type;template<class U>struct rebind{typedef allocator<U>other;};pointer allocate(size_type n,const void * hint = 0){return _allocate((difference_type)n,(pointer)0);}void deallocate(pointer p,size_type n){_deallocate(p);}void construct(pointer p,const T& value){_construct(p,value);}void destroy(pointer p){_destroy(p);}pointer address(reference x){return (pointer)&x;}const_pointer const_address(const_reference x){return (const_pointer)&x;}size_type max_size()const{return size_type(UINT_MAX/sizeof (T));}}; }template <class Key,class Value,class KeyOfValue,class Compare,class 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 simple_alloc<rb_tree_node,Alloc>rb_tree_node_allocator;typedef __rb_tree_color_type color_type; public:typedef Key key_type;typedef Value value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef rb_tree_node* link_type;typedef std::size_t size_type;typedef std::ptrdiff_t difference_type; protected:link_type get_node(){return rb_tree_node_allocator::allocate();}void put_node(link_type p){return rb_tree_node_allocator::deallocate(p);}link_type create_node(const value_type& x){link_type tmp = get_node(); //配置空間__STL_TRY{Chy::allocator<Key>::construct(&tmp->value_field,x);//構(gòu)造內(nèi)容};__STL_UNWIND(put_node(tmp));return tmp;}link_type clone_node(link_type x){//復(fù)制一個(gè)節(jié)點(diǎn)的顏色和數(shù)值link_type tmp = create_node(x->value_field);tmp->color = x->color;tmp->left = 0;tmp->right = 0;return tmp;}void destroy_node(link_type p){Chy::allocator<Key>::destroy(&p->value_field); //析構(gòu)內(nèi)容put_node(p); //釋放內(nèi)存} protected://RB-tree只使用三筆數(shù)據(jù)表現(xiàn)size_type node_count; //追蹤記錄樹的大小 (節(jié)點(diǎn)的數(shù)量)link_type header; //實(shí)現(xiàn)上的小技巧Compare key_compare; //節(jié)點(diǎn)之間的鍵值大小的比較準(zhǔn)則. 應(yīng)該會(huì)是一個(gè)function object//以下三個(gè)函數(shù)用于方便獲取header的成員link_type& root() const{return (link_type&)header->parent;}link_type& left_most() const{return (link_type&)header->left;}link_type& right_most() const{return (link_type&)header->right;}//以下六個(gè)函數(shù)用于方便獲得節(jié)點(diǎn)x的成員static link_type& left(link_type x){ return(link_type&)x->left;}static link_type& right(link_type x){ return(link_type&)x->right;}static link_type& parent(link_type x){ return(link_type&)x->parent;}static reference value(link_type x){ return x->value_field;}static const Key& key(link_type x){ return KeyOfValue()(value(x));}static color_type& color(link_type x){return (color_type&) (x->color);}//獲取極大值和極小值 node class有實(shí)現(xiàn)此功能static link_type minimum(link_type x){return (link_type) __rb_tree_node_base::minimum(x);}static link_type maximum(link_type x){return (link_type) __rb_tree_node_base::maximum(x);}//迭代器typedef __rb_tree_iterator<value_type,reference,pointer>iterator; private:iterator __insert(base_ptr x,base_ptr y,const value_type& v);link_type __copy(link_type x,link_type p);void __erase(link_type x);void clear() {if (node_count != 0) {__erase(root());left_most() = header;root() = 0;right_most() = header;node_count = 0;}}void init(){header = get_node(); //產(chǎn)生一個(gè)節(jié)點(diǎn)空間 令header指向它c(diǎn)olor(header) = __rb_tree_red;//令header為紅色 用于區(qū)分header和root,在iterator的operator++中root() == 0;left_most() = header; //令header的左子節(jié)點(diǎn)等于自己right_most() = header; //令header的右子節(jié)點(diǎn)等于自己} public://allocation / deallocationrb_tree(const Compare& comp = Compare()): node_count(0),key_compare(comp){init();}~rb_tree(){clear();put_node(header);}rb_tree<Key,Value,KeyOfValue,Compare,Alloc>&operator==(const rb_tree<Key,Value,KeyOfValue,Compare,Alloc>&x); public://accessorsCompare key_comp() const {return key_compare;}iterator begin() {return left_most();} //RB樹的起頭為最左(最小)節(jié)點(diǎn)處iterator end(){return header;} //RB樹的終點(diǎn)為header所指處bool empty() const {return node_count == 0;}size_type size() const {return node_count;}size_type max_size() const {return size_type (-1);} public://insert/erase//將x插入到RB-Tree中 (保持節(jié)點(diǎn)的獨(dú)一無(wú)二)std::pair<iterator,bool> insert_unique(const value_type& x);//將x插入到RB-Tree中 (允許節(jié)點(diǎn)數(shù)值重復(fù))iterator insert_equal(const value_type& x); };

RB-Tree的構(gòu)造和內(nèi)存管理

• 邊界情況的考慮，也就是走到根節(jié)點(diǎn)的時(shí)候需要有特殊的處理
• SGI STL為根節(jié)點(diǎn)載設(shè)計(jì)了一個(gè)父節(jié)點(diǎn) 名為header。每當(dāng)插入節(jié)點(diǎn)的時(shí)候，不僅僅需要按照紅黑樹的規(guī)則進(jìn)行調(diào)整，還需要維護(hù)header的正確性，使其父節(jié)點(diǎn)執(zhí)行根節(jié)點(diǎn)，左子節(jié)點(diǎn)指向最小節(jié)點(diǎn)、右子節(jié)點(diǎn)指向最大節(jié)點(diǎn)

?RB-Tree的元素操作

• 元素的插入和搜尋。插入元素的鍵值是否可以重復(fù)作為區(qū)分
• 用戶需要明確設(shè)定所謂的KeyOfValue仿函數(shù)

?

完整代碼

#include <iostream>#ifdef __STL_USE_EXCEPTIONS #define __STL_TRY try #define __STL_UNWIND(action) catch(...) { action; throw; } #else #define __STL_TRY #define __STL_UNWIND(action) #endiftypedef bool __rb_tree_color_type; const __rb_tree_color_type __rb_tree_red = false; //紅色為0 const __rb_tree_color_type __rb_tree_black = true; //黑色為1struct __rb_tree_node_base{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr;color_type color; //節(jié)點(diǎn)顏色 非紅即黑base_ptr parent; //RB-Tree的許多操作 都是需要父節(jié)點(diǎn)的參與base_ptr left; //指向左節(jié)點(diǎn)base_ptr right; //指向右節(jié)點(diǎn)static base_ptr minimum(base_ptr x){while (x->left != 0){//二叉搜索樹的特性//一直向左走 就會(huì)找到最小值x = x->left;}return x;}static base_ptr maximum(base_ptr x){while(x->right != 0){//二叉搜索樹的特性//一直向右走 就會(huì)找到最大值x = x->right;}return x;} };template <class Value> struct __rb_tree_node : public __rb_tree_node_base{typedef __rb_tree_node<Value>* link_type;Value value_field; //節(jié)點(diǎn)值 };//基層迭代器 struct __rb_tree_base_iterator{typedef __rb_tree_node_base::base_ptr base_ptr;typedef std::bidirectional_iterator_tag iterator_category;typedef ptrdiff_t difference_type;base_ptr node; //用于和容器之間產(chǎn)生一個(gè)連接關(guān)系(make a reference)//以下實(shí)現(xiàn)于operator++內(nèi)，因?yàn)樵贌o(wú)其他地方會(huì)調(diào)用這個(gè)函數(shù)了void increment(){if (node->right != 0){ //如果有右節(jié)點(diǎn)，狀況一node = node->right; //就向右走while(node->left != 0){ //然后一直往左子樹前進(jìn)node = node->left; //即為答案}} else{ //沒有右節(jié)點(diǎn) 狀況二base_ptr y = node->parent;//找出父節(jié)點(diǎn)while(node == y->right){ //如果現(xiàn)行節(jié)點(diǎn)本身是個(gè)右子節(jié)點(diǎn)node = y; //需要一直上溯 直到不為右子節(jié)點(diǎn)為止y = y->parent;}if (node->right != y){ //如果此時(shí)node的右子節(jié)點(diǎn)不等于此時(shí)的父節(jié)點(diǎn)node = y; //狀況三 此時(shí)的父節(jié)點(diǎn)即為解答} //否則 此時(shí)的node即為解答 狀況四}/*以上判斷 "若此時(shí)的右子節(jié)點(diǎn)不等于此時(shí)的父節(jié)點(diǎn)"是為了應(yīng)對(duì)一種特殊的情況* 即：欲尋找的根節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，而此時(shí)根節(jié)點(diǎn)恰好沒有右子節(jié)點(diǎn)* 當(dāng)然，上述的特殊做法需要配合RB-Tree根節(jié)點(diǎn)和特殊的header之間的特殊的關(guān)系*/}//以下實(shí)現(xiàn)于operator--內(nèi)，因?yàn)樵贌o(wú)其他地方會(huì)調(diào)用這個(gè)函數(shù)了void decrement(){//狀況一//如果是紅節(jié)點(diǎn) 且 父節(jié)點(diǎn)的父節(jié)點(diǎn)等于自己 右子節(jié)點(diǎn)即為答案//狀況一 發(fā)生于node為header的時(shí)候(亦即node為end()時(shí))//注意：header的右子節(jié)點(diǎn) 即 mostright指向整棵樹的max節(jié)點(diǎn)if (node->color == __rb_tree_red && node->right->right == node){node = node->right;}//狀況二//如果有左子節(jié)點(diǎn) 令y指向左子節(jié)點(diǎn)；只有當(dāng)y有右子節(jié)點(diǎn)的時(shí)候 一直往右走 到底，最后即為答案else if (node->left!=0){base_ptr y = node->left;while (y->right != 0){y = y->right;}node = y;} else{//狀況三//既不是根節(jié)點(diǎn) 也沒有左節(jié)點(diǎn)//找出父節(jié)點(diǎn)，當(dāng)現(xiàn)行的節(jié)點(diǎn)身為左子節(jié)點(diǎn)時(shí)，一直交替往上走，直到現(xiàn)行節(jié)點(diǎn)不是左節(jié)點(diǎn)為止base_ptr y = node->parent;while(node == y->left){node = y;y = y->right;}node = y; //此時(shí)父節(jié)點(diǎn)即為答案}} };//RB-Tree的正規(guī)迭代器 template <class Value,class Ref,class Ptr> struct __rb_tree_iterator : public __rb_tree_base_iterator{typedef Value value_type;typedef Ref reference;typedef Ptr pointer;typedef __rb_tree_iterator<Value,Value&,Value*> iterator;typedef __rb_tree_iterator<Value,const Value&,const Value*> const_iterator;typedef __rb_tree_iterator<Value,Value&,Value*> self;typedef __rb_tree_node<Value>* link_type;__rb_tree_iterator(){}__rb_tree_iterator(link_type x){node = x;}__rb_tree_iterator(const iterator& it){node = it.node;}reference operator* () const {return link_type(node)->value_field; }#ifndef __SGI_STL_NO_ARROW_OPERATORreference operator->()const {return &(operator*());} #endif //__SGI_STL_NO_ARROW_OPERATORself& operator++(){increment();return *this;}self operator++(int){self tmp = *this;increment();return tmp;}self& operator--(){decrement();return *this;}self operator--(int){self tmp = *this;decrement();return tmp;}};template<class T,class Alloc> class simple_alloc{ public:static T* allocate(std::size_t n){return 0==n?0:(T*)Alloc::allocate(n * sizeof(T));}static T* allocate(void){return (T*)Alloc::allocate(sizeof (T));}static void deallocate(T* p,size_t n){if (n!=0){Alloc::deallocate(p,n * sizeof(T));}}static void deallocate(T* p){Alloc::deallocate(p,sizeof(T));} };namespace Chy{template <class T>inline T* _allocate(ptrdiff_t size,T*){std::set_new_handler(0);T* tmp = (T*)(::operator new((std::size_t)(size * sizeof (T))));if (tmp == 0){std::cerr << "out of memory" << std::endl;exit(1);}return tmp;}template<class T>inline void _deallocate(T* buffer){::operator delete (buffer);}template<class T1,class T2>inline void _construct(T1 *p,const T2& value){new(p) T1 (value); //沒看懂}template <class T>inline void _destroy(T* ptr){ptr->~T();}template <class T>class allocator{public:typedef T value_type;typedef T* pointer;typedef const T* const_pointer;typedef T& reference;typedef const T& const_reference;typedef std::size_t size_type;typedef ptrdiff_t difference_type;template<class U>struct rebind{typedef allocator<U>other;};pointer allocate(size_type n,const void * hint = 0){return _allocate((difference_type)n,(pointer)0);}void deallocate(pointer p,size_type n){_deallocate(p);}void construct(pointer p,const T& value){_construct(p,value);}void destroy(pointer p){_destroy(p);}pointer address(reference x){return (pointer)&x;}const_pointer const_address(const_reference x){return (const_pointer)&x;}size_type max_size()const{return size_type(UINT_MAX/sizeof (T));}}; }template <class Key,class Value,class KeyOfValue,class Compare,class 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 simple_alloc<rb_tree_node,Alloc>rb_tree_node_allocator;typedef __rb_tree_color_type color_type; public:typedef Key key_type;typedef Value value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef rb_tree_node* link_type;typedef std::size_t size_type;typedef std::ptrdiff_t difference_type; protected:link_type get_node(){return rb_tree_node_allocator::allocate();}void put_node(link_type p){return rb_tree_node_allocator::deallocate(p);}link_type create_node(const value_type& x){link_type tmp = get_node(); //配置空間__STL_TRY{Chy::allocator<Key>::construct(&tmp->value_field,x);//構(gòu)造內(nèi)容};__STL_UNWIND(put_node(tmp));return tmp;}link_type clone_node(link_type x){//復(fù)制一個(gè)節(jié)點(diǎn)的顏色和數(shù)值link_type tmp = create_node(x->value_field);tmp->color = x->color;tmp->left = 0;tmp->right = 0;return tmp;}void destroy_node(link_type p){Chy::allocator<Key>::destroy(&p->value_field); //析構(gòu)內(nèi)容put_node(p); //釋放內(nèi)存} protected://RB-tree只使用三筆數(shù)據(jù)表現(xiàn)size_type node_count; //追蹤記錄樹的大小 (節(jié)點(diǎn)的數(shù)量)link_type header; //實(shí)現(xiàn)上的小技巧Compare key_compare; //節(jié)點(diǎn)之間的鍵值大小的比較準(zhǔn)則. 應(yīng)該會(huì)是一個(gè)function object//以下三個(gè)函數(shù)用于方便獲取header的成員link_type& root() const{return (link_type&)header->parent;}link_type& left_most() const{return (link_type&)header->left;}link_type& right_most() const{return (link_type&)header->right;}//以下六個(gè)函數(shù)用于方便獲得節(jié)點(diǎn)x的成員static link_type& left(link_type x){ return(link_type&)x->left;}static link_type& right(link_type x){ return(link_type&)x->right;}static link_type& parent(link_type x){ return(link_type&)x->parent;}static reference value(link_type x){ return x->value_field;}static const Key& key(link_type x){ return KeyOfValue()(value(x));}static color_type& color(link_type x){return (color_type&) (x->color);}//獲取極大值和極小值 node class有實(shí)現(xiàn)此功能static link_type minimum(link_type x){return (link_type) __rb_tree_node_base::minimum(x);}static link_type maximum(link_type x){return (link_type) __rb_tree_node_base::maximum(x);}//迭代器typedef __rb_tree_iterator<value_type,reference,pointer>iterator; public:iterator __insert(base_ptr x,base_ptr y,const value_type& v);link_type __copy(link_type x,link_type p);void __erase(link_type x);void clear() {if (node_count != 0) {__erase(root());left_most() = header;root() = 0;right_most() = header;node_count = 0;}}void init(){header = get_node(); //產(chǎn)生一個(gè)節(jié)點(diǎn)空間 令header指向它c(diǎn)olor(header) = __rb_tree_red;//令header為紅色 用于區(qū)分header和root,在iterator的operator++中root() == 0;left_most() = header; //令header的左子節(jié)點(diǎn)等于自己right_most() = header; //令header的右子節(jié)點(diǎn)等于自己} public://allocation / deallocationrb_tree(const Compare& comp = Compare()): node_count(0),key_compare(comp){init();}~rb_tree(){clear();put_node(header);}rb_tree<Key,Value,KeyOfValue,Compare,Alloc>&operator==(const rb_tree<Key,Value,KeyOfValue,Compare,Alloc>&x); public://accessorsCompare key_comp() const {return key_compare;}iterator begin() {return left_most();} //RB樹的起頭為最左(最小)節(jié)點(diǎn)處iterator end(){return header;} //RB樹的終點(diǎn)為header所指處bool empty() const {return node_count == 0;}size_type size() const {return node_count;}size_type max_size() const {return size_type (-1);} public://insert/erase//將x插入到RB-Tree中 (保持節(jié)點(diǎn)的獨(dú)一無(wú)二)std::pair<iterator,bool> insert_unique(const value_type& x);//將x插入到RB-Tree中 (允許節(jié)點(diǎn)數(shù)值重復(fù))iterator insert_equal(const value_type& x);//尋找鍵值為k的節(jié)點(diǎn)iterator find(const value_type& k); };//插入新的數(shù)值 節(jié)點(diǎn)鍵值允許重復(fù) //注意：返回的是一個(gè)RB-Tree的迭代器，指向的是新增的節(jié)點(diǎn) template <class Key,class Value,class KeyOfValue,class Compare,class Alloc> typename rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::iteratorrb_tree<Key,Value,KeyOfValue,Compare,Alloc>::insert_equal(const value_type &v) {link_type y = header;link_type x = root(); //根節(jié)點(diǎn)開始while(x != 0){ //根節(jié)點(diǎn)開始 從上往下尋找適當(dāng)?shù)牟迦牍?jié)點(diǎn)y = x;//如果當(dāng)前根節(jié)點(diǎn)比 輸入的v大，則轉(zhuǎn)向左邊，否則轉(zhuǎn)向右邊x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);}//x為新值插入點(diǎn) y為插入點(diǎn)的父節(jié)點(diǎn) v為新值return __insert(x,y,v); }//插入新的數(shù)值 節(jié)點(diǎn)鍵值不允許重復(fù) //注意：返回結(jié)果是pair類型，第一個(gè)元素是一個(gè)RB-Tree的迭代器，指向的是新增的節(jié)點(diǎn)；第二個(gè)參數(shù)表示插入成功與否 template <class Key,class Value,class KeyOfValue,class Compare,class Alloc> std::pair<typename rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::iterator,bool> rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::insert_unique(const value_type &v) {link_type y = header;link_type x = root(); //從根節(jié)點(diǎn)開始bool comp = true;while(x != 0){ //從根節(jié)點(diǎn)開始 往下尋找適當(dāng)?shù)牟迦朦c(diǎn)y = x;comp = key_compare(KeyOfValue()(v), key(x)); //v鍵值小于目前節(jié)點(diǎn)的鍵值x = comp ? left(x) : right(x); //遇"大"則向左 遇"小"則向右}//離開while循環(huán)之后 y所指的即 插入點(diǎn)之父節(jié)點(diǎn)（此時(shí)它必為葉子結(jié)點(diǎn)）iterator j = iterator(y); //迭代器j指向插入點(diǎn)的父節(jié)點(diǎn)yif (comp){//如果while循環(huán)時(shí)候，判定comp的數(shù)值，如果comp為真(表示遇到大的元素，將插入左側(cè))//如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是最左側(cè)的節(jié)點(diǎn)//x為插入點(diǎn)，y為插入節(jié)點(diǎn)的父節(jié)點(diǎn)，v表示新值if (j == begin()){return std::pair<iterator,bool>(__insert(x,y,v), true);} else{//插入節(jié)點(diǎn)的父節(jié)點(diǎn)不是最左側(cè)的節(jié)點(diǎn)//調(diào)整j 回頭準(zhǔn)備測(cè)試--j;}if (key_compare(key(j.node),KeyOfValue()(v))){//小于新值（表示遇到小的數(shù)值，將插在右側(cè)）return std::pair<iterator,bool>(__insert(x,y,v), true);}}//至此 表示新值一定和樹中的鍵值重復(fù) 就不應(yīng)該插入新的數(shù)值return std::pair<iterator,bool>(j, false); }//真正的插入執(zhí)行程序 __insert() template <class Key,class Value,class KeyOfValue,class Compare,class Alloc> typename rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::iterator rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::__insert(base_ptr x_, base_ptr y_, const value_type &v) {//參數(shù)x_為新的插入點(diǎn) 參數(shù)y_為插入點(diǎn)的父節(jié)點(diǎn) 參數(shù)v為新值link_type x = (link_type)x_;link_type y = (link_type)y_;link_type z ;//key_compare 是鍵值大小的比較準(zhǔn)則，應(yīng)該是一個(gè)function objectif (y == header||x != 0||key_compare(KeyOfValue()(v),key(x))){z = create_node(v); //產(chǎn)生一個(gè)新的節(jié)點(diǎn)//當(dāng)y即為header的時(shí)候，leftmost = z;if (y == header){root() = z;right_most() = z;} else if (y == left_most()){//y為最左節(jié)點(diǎn)//維護(hù)leftmost() 使其永遠(yuǎn)指向最左節(jié)點(diǎn)left_most() = z;} else{z = create_node(v);//產(chǎn)生一個(gè)新的節(jié)點(diǎn)//讓新節(jié)成為插入點(diǎn)的父節(jié)點(diǎn)y的右子節(jié)點(diǎn)right(y) = z;if (y == right_most()){ //維護(hù)rightmost()讓其永遠(yuǎn)指向最右的節(jié)點(diǎn)right_most() = z;}}parent(z) = y; //設(shè)定新節(jié)點(diǎn)的父節(jié)點(diǎn)left(z) = 0; //設(shè)定新節(jié)點(diǎn)的左子節(jié)點(diǎn)right(z) = 0; //設(shè)定新節(jié)點(diǎn)的右子節(jié)點(diǎn)//修改顏色//參數(shù)一為新增節(jié)點(diǎn) ；參數(shù)二 為root__rb_tree_rebalance(z,header->parent);++node_count;//返回一個(gè)迭代器 指向新的節(jié)點(diǎn)return iterator(z);} }//全局函數(shù) //新節(jié)點(diǎn)必須為紅色，如果插入出父節(jié)點(diǎn)同樣為紅色，就需要進(jìn)行樹形旋轉(zhuǎn) inline void __rb_tree_rotate_left(__rb_tree_node_base* x,__rb_tree_node_base*& root){//x為旋轉(zhuǎn)點(diǎn)__rb_tree_node_base* y = x->right;//令y為旋轉(zhuǎn)點(diǎn)的右子節(jié)點(diǎn)x->right = y->left;if (y->left != 0){//回馬槍設(shè)定父親節(jié)點(diǎn)y->left->parent = x;}y->parent = x->parent;//令y完全替代x的地位 (需要將x對(duì)其父節(jié)點(diǎn)的關(guān)系完全接收回來(lái))if (x == root){root = y; //x為根節(jié)點(diǎn)} else if (x == x->parent->left){x->parent->left = y; //x為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)} else{x->parent->right = y; //x為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)}y->left = x;x->parent = y; }//全局函數(shù) //新節(jié)點(diǎn)必須為紅色，如果插入出父節(jié)點(diǎn)同樣為紅色，就需要進(jìn)行樹形旋轉(zhuǎn) inline void __rb_tree_rotate_right(__rb_tree_node_base* x,__rb_tree_node_base*& root){//x為旋轉(zhuǎn)點(diǎn)__rb_tree_node_base* y = x->left; //y為旋轉(zhuǎn)點(diǎn)的左子節(jié)點(diǎn)x->left = y->right;if (y->right != 0){y->right->parent = x;}y->parent = x->parent;//令y完全替代x的地位if(x == root){root = y;} else if (x == x->parent->right){x->parent->right = y;} else{x->parent->left = y;}y->parent = x;x->parent = y; }//調(diào)整RB_tree 插入節(jié)點(diǎn)之后，需要進(jìn)行調(diào)整(顏色/翻轉(zhuǎn))從而滿足要求 inline void __rb_tree_balance(__rb_tree_node_base* x,__rb_tree_node_base*& root){x->color = __rb_tree_red; //新節(jié)點(diǎn)的顏色必須是紅色的while(x!=root && x->parent->color == __rb_tree_red){//父節(jié)點(diǎn)為紅色的//父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的左子節(jié)點(diǎn)if (x->parent == x->parent->parent->left){//令y為伯父節(jié)點(diǎn)__rb_tree_node_base* y = x->parent->right;if (y && y->color == __rb_tree_red){ //伯父節(jié)點(diǎn)存在 且為紅x->parent->color = __rb_tree_black;//更改父節(jié)點(diǎn)的顏色為黑y->color = __rb_tree_black;//更改父節(jié)點(diǎn)的顏色為黑x->parent->parent->color = __rb_tree_red;//更改祖父節(jié)點(diǎn)的顏色為紅x = x->parent->parent;} else{//無(wú)伯父節(jié)點(diǎn) 或者伯父節(jié)點(diǎn)的顏色為黑if (x == x->parent->right){//新節(jié)點(diǎn)為父節(jié)點(diǎn)的右子節(jié)點(diǎn)x = x->parent;//第一次參數(shù)為左旋節(jié)點(diǎn)__rb_tree_rotate_left(x,root);}x->parent->color = __rb_tree_black;//改變顏色x->parent->parent->color = __rb_tree_red;//第一次參數(shù)為右旋節(jié)點(diǎn)__rb_tree_rotate_right(x->parent->parent,root);}} else{//父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的右子節(jié)點(diǎn)__rb_tree_node_base* y = x->parent->parent->left; //令y為伯父節(jié)點(diǎn)if (y && y->color == __rb_tree_red){ //存在伯父節(jié)點(diǎn)，且為紅x->parent->color = __rb_tree_black;//更改父節(jié)點(diǎn)為黑y->color = __rb_tree_black;//更改伯父節(jié)點(diǎn)為黑x->parent->parent->color = __rb_tree_red; //更改祖父節(jié)點(diǎn)為紅x = x->parent->parent; //準(zhǔn)備繼續(xù)往上層檢查} else{//無(wú)伯父節(jié)點(diǎn) 或者伯父節(jié)點(diǎn) 為黑if (x == x->parent->left){//新節(jié)點(diǎn) 為 父節(jié)點(diǎn)的左子節(jié)點(diǎn)x = x->parent;__rb_tree_rotate_right(x,root); //第一參數(shù)為右旋轉(zhuǎn)點(diǎn)}x->parent->color = __rb_tree_black;//改變顏色x->parent->parent->color = __rb_tree_red;//第一參數(shù)為左旋點(diǎn)__rb_tree_rotate_left(x->parent->parent,root);}}} //while結(jié)束root->color = __rb_tree_black; }//元素查找程序 template <class Key,class Value,class KeyOfValue,class Compare,class Alloc> typename rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::iterator rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::find(const value_type &k) {link_type y = header; //last node which is not less than klink_type x = root(); //current nodewhile(x != 0){//key_compare 是節(jié)點(diǎn)大小的比較準(zhǔn)則 function objectif (!key_compare(key(x),k)){//進(jìn)行到這里 表示x的數(shù)值大于k 。遇到大的數(shù)值向左走y = x,x = left(x);} else{x = right(x);}}iterator j = iterator (y);return (j == end() || key_compare(k,key(j.node))) ? end() : j; }

參考鏈接

• STL源碼：紅黑樹_Sunshine的專欄-CSDN博客

總結(jié)

以上是生活随笔為你收集整理的STL源码剖析 关联式容器 红黑树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。