一、結點類與紅黑樹類：
（一）結點類基本資料成員：
1.左右子結點指標域
2.父結點指標域，方便回訪父結點
3.有序 前驅 / 后繼 指標域，迭代訪問元素，提供一種順序存盤的假象
4.結點顏色，利用紅黑規則，保持樹的平衡，
（二）結點類的基本成員函式：
兩個多載的建構式，構造紅色的新結點
（三）紅黑樹類基本資料成員：
1.頭結點：保存一個據點，用來維系根節點與公用空結點
2.根結點：是紅黑樹的起始位置
3.空結點：作為所有空指標域的指向，一棵樹只有一個
4.全域前驅、后繼結點：用來使紅黑樹線索化，變得可迭代
（四）紅黑樹類基本成員函式（面向內部）：
1.中序遞回構造線索
2.結點左旋、右旋操作
3.插入后修正紅黑樹
4.移除后修正紅黑樹
5.移植（替換）結點
6.子樹最大、最小結點
（五）紅黑樹類基本成員函式（面向用戶）：
1.建構式，構造空樹
2.空樹判斷
3.插入元素
4.移除元素
5.搜索元素
6.獲取起始、終止迭代器、元素最大值、元素最小值
7.遞回遍歷
8.迭代器遍歷
1 class RBTree; 2 enum Color{RED=0,BLACK=1}; 3 template<typename T> 4 class RBnode{ 5 friend class RBTree<T>; 6 public: 7 typedef RBnode<T>* rb_iterator; 8 private: 9 typedef RBnode<T>* Nodeptr; 10 public: 11 Nodeptr left,right,parent; 12 Nodeptr prior,next; 13 Color color; 14 public: 15 T val; 16 public://新結點都是紅結點 17 RBnode(T value){left=right=parent=this;val=value;color=RED;} 18 RBnode(T value, Nodeptr l, Nodeptr r):val(value),left(l),right(r){parent=this,color=RED;} 19 }; 20 template<typename T> 21 class RBTree{ 22 friend class RBnode<T>; 23 private: 24 typedef RBnode<T>* Nodeptr; 25 public: 26 typedef RBnode<T>* rb_iterator; 27 private: 28 Nodeptr header; 29 Nodeptr root; 30 Nodeptr nlnode; 31 Nodeptr _prior; 32 Nodeptr _next; 33 public: 34 RBTree(){ 35 header=new RBnode<T>(0); 36 nlnode=new RBnode<T>(-1); 37 nlnode->color = header->color = BLACK; 38 root=nlnode; 39 root->parent=header; 40 root->left=root->right=nlnode; 41 header->left=nlnode; 42 header->right=root; 43 nlnode->parent=nlnode; 44 header->next = nlnode; 45 header->prior = nlnode; 46 } 47 public: 48 bool isEmpyty(); 49 void Insert(T x); 50 void Insert(Nodeptr); 51 bool remove(T x); 52 bool remove(Nodeptr x); 53 Nodeptr search(T x); 54 T getMax(); 55 T getMin(); 56 rb_iterator begin(){return header->next;} 57 rb_iterator end(){return header;} 58 void inorderWalk(Nodeptr p) const ; 59 void LORvisit(); 60 void Iterator_visit(rb_iterator start, rb_iterator over) { 61 rb_iterator temp = start; 62 while(temp != over){ 63 cout << temp->val << ' '; 64 temp = temp->next; 65 } 66 } 67 private: 68 void LOR(); 69 void LOR(Nodeptr c); 70 void LeftRotate(Nodeptr x); 71 void RightRotate(Nodeptr x); 72 void Fix_up_insert(Nodeptr x); 73 void Fix_up_remove(Nodeptr x); 74 void Transplante(Nodeptr old, Nodeptr neo); 75 Nodeptr BranchMax(Nodeptr x); 76 Nodeptr BranchMin(Nodeptr x); 77 void LORvisit(Nodeptr c); 78 };
二、功能函式實作
（一）空樹判斷：
1 template<typename T> 2 bool RBTree<T>::isEmpyty(){ 3 return root == nlnode; 4 }
（二）插入結點：先把傳入的元素進行封裝，變成結點，再插入
template<typename T> void RBTree<T>::Insert(T x){ Nodeptr n=new RBnode<T>(x, nlnode, nlnode); Insert(n); } template<typename T> void RBTree<T>::Insert(Nodeptr x){ Nodeptr first,second; first = second = root; if(root == nlnode){ root = x; header->right = x; x->parent = header; x->color = BLACK; return; } while(first!=nlnode){ second = first; if(first->val > x->val){ first = first->left; }else if(first->val < x->val){ first = first->right; }else{ return ; } } x->parent = second; if(second->val > x->val){ second->left = x; }else{ second->right = x; } Fix_up_insert(x); LOR(); }
（三）左旋與右旋
1 template<typename T> 2 void RBTree<T>::LeftRotate(Nodeptr x){ 3 if(x->right == nlnode)//無右子樹不可左旋,避免錯誤操作將樹旋空 4 return; 5 Nodeptr x_r=x->right; 6 x->right = x_r->left; 7 if(x_r->left!=nlnode)//避免破壞空節點的特性：父結點指向自身 8 x_r->left->parent = x; 9 x_r->parent = x->parent; 10 if(x_r->parent == header){//根節點 11 root = x_r; 12 }else if(x->parent->left == x){//更新父結點 13 x->parent->left = x_r; 14 }else if(x->parent->right == x){ 15 x->parent->right = x_r; 16 } 17 x_r->left = x; 18 x->parent = x_r; 19 } 20 template<typename T> 21 void RBTree<T>::RightRotate(Nodeptr x){ 22 if(x->left == nlnode)//無右子樹不可左旋,避免錯誤操作將樹旋空 23 return; 24 Nodeptr x_l=x->left; 25 x->left = x_l->right; 26 if(x_l->right!=nlnode)//避免破壞空節點的特性：父結點指向自身 27 x_l->right->parent = x; 28 x_l->parent = x->parent; 29 if(x_l->parent == header){//根節點 30 root = x_l; 31 }else if(x->parent->right == x){//更新父結點 32 x->parent->right = x_l; 33 }else if(x->parent->left == x){ 34 x->parent->left = x_l; 35 } 36 x_l->right = x; 37 x->parent = x_l; 38 }
（四）插入后修正
1 template<typename T> 2 void RBTree<T>::Fix_up_insert(Nodeptr x){ 3 while(x->parent->color==RED){//首先滿足沒有連續的紅色結點 4 if(x->parent == x->parent->parent->left){ 5 if(x->parent->parent->right->color == RED){//case 1: son --red,dad&dad's brother --red 6 x->parent->parent->right->color = x->parent->color = BLACK; 7 x->parent->parent->color = RED; 8 x = x->parent->parent; 9 } 10 else{ 11 if(x == x->parent->right){//case 2:inner side,son --red,dad --red 12 x = x->parent; 13 LeftRotate(x); 14 } 15 x->parent->parent->color = RED;//case 3:outer side,son --red,dad --red 16 x->parent->color = BLACK; 17 x = x->parent; 18 RightRotate(x->parent->parent); 19 } 20 } 21 else{ 22 if(x->parent->parent->left->color == RED){//case 1: son --red,dad&dad's brother --red 23 x->parent->parent->left->color = x->parent->color = BLACK; 24 x->parent->parent->color = RED; 25 x = x->parent->parent; 26 } 27 else{ 28 if(x == x->parent->left){//case 2:inner side,son --red,dad --red 29 x = x->parent; 30 LeftRotate(x); 31 } 32 x->parent->parent->color = RED;//case 3:outer side,son --red,dad --red 33 x->parent->color = BLACK; 34 x = x->parent; 35 RightRotate(x->parent->parent); 36 } 37 } 38 } 39 root->color=BLACK; 40 }
（五）尋找元素：
1 template<typename T> 2 RBnode<T>* RBTree<T>::search(T x){ 3 Nodeptr temp = root; 4 while(temp!=nlnode){ 5 if(temp->val > x){ 6 temp = temp->left; 7 }else if(temp->val < x){ 8 temp = temp->right; 9 }else{ 10 return temp; 11 } 12 } 13 return nlnode; 14 }
（六）移植(替換)結點：
1 template<typename T> 2 void RBTree<T>::Transplante(Nodeptr old, Nodeptr neo){ 3 if(old->parent == header){ 4 header->right = neo; 5 root = neo; 6 }else if(old->parent->left == old){ 7 old->parent->left = neo; 8 }else if(old->parent->right == old){ 9 old->parent->right = neo; 10 } 11 neo->parent = old->parent; 12 }
（七）子樹最大最小結點：
1 template<typename T> 2 RBnode<T>* RBTree<T>::BranchMax(Nodeptr x){ 3 if(x == nlnode) 4 return x; 5 Nodeptr temp=x; 6 while(temp->right!=nlnode){ 7 temp=temp->right; 8 } 9 return temp; 10 } 11 template<typename T> 12 RBnode<T>* RBTree<T>::BranchMin(Nodeptr x){ 13 if(x == nlnode) 14 return x; 15 Nodeptr temp=x; 16 while(temp->left!=nlnode){ 17 temp=temp->left; 18 } 19 return temp; 20 }
（八）移除結點：
1 template<typename T> 2 bool RBTree<T>::remove(T x){ 3 Nodeptr target = search(x); 4 if(target == nlnode){ 5 LOR(); 6 return false;} 7 return remove(target); 8 } 9 template<typename T> 10 bool RBTree<T>::remove(Nodeptr x){ 11 Nodeptr a = x; 12 Nodeptr b = nlnode; 13 Color a_OriCo = a->color; 14 if(x->left==nlnode){//case 1:with one kid or no one 15 b = x->right; 16 Transplante(x, x->right); 17 }else if(x->right==nlnode){ 18 b = x->left; 19 Transplante(x, x->left); 20 }else{ 21 Nodeptr a=BranchMin(x->right); 22 a_OriCo = a->color; 23 b = a->right; 24 if(a->parent == x){//case 2:replace node is son of x 25 b->parent = a;//case nlnode 26 }else{ 27 Transplante(a, a->right);//a break away from there 28 a->right = x->right; 29 a->right->parent = a; 30 } 31 Transplante(x, a);//用新結點分支替換舊結點分支 32 a->left = x->left; 33 a->left->parent = a; 34 a->color = x->color; 35 } 36 delete x; 37 if(a_OriCo == BLACK){//case 3:違背紅黑規則，路徑黑結點數不同 38 Fix_up_remove(b); 39 } 40 LOR();//構建迭代聯系，懶得寫就直接從頭構建了，這里應該仿造雙鏈表洗掉結點來寫 41 }
（九）洗掉后修正
1 template<typename T> 2 void RBTree<T>::Fix_up_remove(Nodeptr x){ 3 Nodeptr z = nlnode; 4 while(x!=root&&x->color==BLACK){ 5 if(x == x->parent->left){ 6 z=x->parent->right; 7 if(z->color == RED){//case 1:x's brather --red 8 z->color=BLACK; 9 x->parent->color = RED; 10 LeftRotate(x->parent);//利用紅色來保持黑一致 11 z = x->parent->right;//update x's brother 12 }//case 2:x&x's brother sons color same 13 if(z->left->color==BLACK && z->right->color==BLACK){ 14 z->color = RED;//保持與x顏色一致，因為是兄弟結點 15 x = x->parent;//向上調整 16 } 17 else { 18 if(z->right->color==BLACK) {//z:x's brother 19 z->color = RED;//case 3:z left--red,right--black 20 z->left->color = BLACK; 21 RightRotate(z); 22 z = x->parent->right; 23 } 24 //case 4:adjust x and z 25 //將樹平衡高度，保持了原父結點位置的顏色 26 z->color = x->parent->color; 27 x->parent->color = BLACK; 28 z->right->color = BLACK; 29 LeftRotate(x->parent); 30 break; 31 } 32 } 33 else { 34 z=x->parent->left; 35 if(z->color == RED){//case 1:x's brather --red 36 z->color=BLACK; 37 x->parent->color = RED; 38 this->RightRotate(x->parent);//利用紅色來保持黑一致 39 z = x->parent->left;//update x's brother 40 }//case 2:x&x's brother sons color same 41 if(z->right->color==BLACK && z->left->color==BLACK){ 42 z->color = RED;//保持與x顏色一致，因為是兄弟結點 43 x = x->parent;//向上調整 44 } 45 else { 46 if(z->left->color==BLACK) {//z:x's brother 47 z->color = RED;//case 3:z left--red,right--black 48 z->right->color = BLACK; 49 LeftRotate(z); 50 z = x->parent->left; 51 } 52 //case 4:adjust x and z 53 //將樹平衡高度，保持了原父結點位置的顏色 54 z->color = x->parent->color; 55 x->parent->color = BLACK; 56 z->left->color = BLACK; 57 RightRotate(x->parent); 58 break; 59 } 60 } 61 } 62 root->color = BLACK;//保持根為黑 63 }
（十）獲取最大最小元素：
1 template<typename T> 2 T RBTree<T>::getMax(){ 3 return header->prior->val; 4 } 5 template<typename T> 6 T RBTree<T>::getMin(){ 7 return header->next->val; 8 }
（十一）迭代構造線索
1 template<typename T> 2 void RBTree<T>::LOR(){ 3 _prior = _next = header; 4 LOR(root); 5 _next->next=header; 6 header->prior=_next; 7 } 8 template<typename T> 9 void RBTree<T>::LOR(Nodeptr c){ 10 if(c->left != nlnode){ 11 LOR(c->left); 12 } 13 _prior = _next; 14 _next = c; 15 _prior->next=_next; 16 _next->prior=_prior; 17 if(c->right != nlnode){ 18 LOR(c->right); 19 } 20 }
（十二）遞回遍歷與迭代遍歷：
1 template<typename T> 2 void RBTree<T>::LORvisit(){ 3 LORvisit(root); 4 cout << endl; 5 } 6 template<typename T> 7 void RBTree<T>::LORvisit(Nodeptr c){ 8 if(c->left != nlnode){ 9 LORvisit(c->left); 10 } 11 cout << c->val << ' '; 12 if(c->right != nlnode){ 13 LORvisit(c->right); 14 } 15 } 16 void Iterator_visit(rb_iterator start, rb_iterator over) { 17 rb_iterator temp = start; 18 while(temp != over){ 19 cout << temp->val << ' '; 20 temp = temp->next; 21 } 22 }
三、紅黑樹測驗：
1 #include <iostream> 2 #include <stdlib.h> 3 #include "templateRBTree.h" 4 using namespace std; 5 6 int main() 7 { 8 RBTree<int> rb; 9 for(int i=0;i < 10;++i) 10 rb.Insert(rand()%20); 11 cout << "create RBTree: "; 12 rb.LORvisit(); 13 RBTree<int>::rb_iterator itr=rb.begin(); 14 cout << "visit tree by iterator: " << endl; 15 rb.Iterator_visit(itr, rb.end()); 16 cout << endl; 17 cout << "the max of tree: " << rb.getMax() << endl; 18 cout << "the min of tree: " << rb.getMin() << endl; 19 for(int i=0;i<10;++i) 20 rb.remove(i); 21 cout << "remove x<10: "; 22 rb.LORvisit(); 23 cout << "the max of tree: " << rb.getMax() << endl; 24 cout << "the min of tree: " << rb.getMin() << endl; 25 itr=rb.begin(); 26 cout << "visit tree by iterator: " << endl; 27 rb.Iterator_visit(itr, rb.end()); 28 return 0; 29 }
結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/103912.html
標籤：其他