您需要寫一種數(shù)據(jù)結構（可參考題目標題），來維護一些數(shù)，其中需要提供以下操作：

插入?x?數(shù)

刪除?x?數(shù)(若有多個相同的數(shù)，因只刪除一個)

查詢?x?數(shù)的排名(排名定義為比當前數(shù)小的數(shù)的個數(shù)?+1?)

查詢排名為?x?的數(shù)

求?x?的前驅(前驅定義為小于?x，且最大的數(shù))

求?x?的后繼(后繼定義為大于?x，且最小的數(shù)）

一、紅黑樹定義

紅黑樹的英文是“Red-Black Tree”，簡稱 R-B Tree，它是一種不嚴格的平衡二叉查找樹

二叉查找樹這一數(shù)據(jù)結構并不難，而紅黑樹之所以難是難在它是自平衡的二叉查找樹，在進行插入和刪除等可能會破壞樹的平衡的操作時，需要重新自處理達到平衡狀態(tài)。

紅黑樹是一種含有紅色和黑色節(jié)點并能自平衡的二叉查找樹，紅黑樹和其他二叉查找樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的性質，從而獲得較高的查找性能。它雖然是復雜的，但它的最壞情況運行時間也是非常良好的，并且在實踐中是高效的：它可以在 O(log n) 時間內做查找，插入和刪除，這里的 n 是樹中元素的數(shù)目。

二、紅黑樹性質

紅黑樹是一顆二叉搜索樹，它在每一個結點上增加了一個儲存位來表示結點的顏色，可以是RED或BLACK。通過對任何一條從根到葉子的簡單路徑上的各個結點的顏色進行約束，紅黑樹確保沒有一條路徑會比其他路徑長出兩倍，因而是近似平衡的。

樹中每個結點包含5個屬性：color、key、left、right、p。如果一個結點沒有子結點或父結點，則該結點相應指針屬性的值為NIL.我們可以把這些NIL視為指向二叉搜索樹的葉結點（外部結點）的指針，而把帶關鍵字的結點視為樹的內部結點。

一顆紅黑樹是滿足下面紅黑性質的二叉搜索樹：

性質1：每個結點是紅色或黑色。

性質2：根結點是黑色。

性質3：每個葉結點(NIL)是黑色的。

性質4：如果一個結點是紅色的，則它的兩個子結點都是黑色的。

性質5：對每個結點，從該結點到其后代葉結點的簡單路徑上，均包含相同數(shù)目的黑色結點。

為了便于處理紅黑樹代碼中的邊界條件，使用一個哨兵來代表NIL.對于一顆紅黑樹T，哨兵T.nil是一個與樹中普通結點有相同屬性的對象。它的color屬性為BLACK，而其他屬性p、left、right和key可以設為任意值。所有指向NIL的指針都用指向哨兵T.nil的指針替換。

結點類代碼如下

class Node{private:pair<T,V> p;int s;bool color;//0代表紅色 1代表黑色Node* Lt;Node* Rt;Node* pre;public:Node(pair<T,V> _p,int _s,bool _color,Node* _Lt = nullptr,Node* _Rt = nullptr,Node* _pre = nullptr):p(_p),s(_s),color(_color),Lt(_Lt),Rt(_Rt),pre(_pre){}Node(Node* tmp):p(tmp->p),s(tmp->s),color(tmp->color),Lt(tmp->Lt),Rt(tmp->Rt),pre(tmp->pre){}Node*& GetLt() { return Lt;}Node*& GetRt() { return Rt;}Node*& Getpre() { return pre;}T& Getdata() { return p.first;}V& Getinfo() { return p.second;}pair<T,V>* Getpair(){ return &p;}bool Getcolor() const{ return color;}int& Getsize() { return s;}void SetLt(Node*& tmp){Lt = tmp;}void SetRt(Node*& tmp){ Rt = tmp;}void Setpre(Node*& tmp){ pre = tmp;}void Setdata(T tmp){ p.first = tmp;}void Setinfo(V tmp){ p.second = tmp;} void Setcolor(bool tmp){ color = tmp;}};

三、紅黑樹的相關操作

在插入、刪除節(jié)點的過程中，性質3、性質4可能會被破壞，為了維護這些性質，必須要改變樹中某些結點的顏色以及指針結構。

指針結構的修改是通過旋轉（ratation）來完成的，分為左旋和右旋。

?

左旋以x到y(tǒng)的鏈為“支軸”進行。它使y成為該子樹新的根節(jié)點，x成為y的右孩子，y的左孩子成為x的右孩子。

左旋、右旋代碼：

void LRotate(Node* x){//左旋 Node* tmp = Rt(x); //tmp為x的右結點 x->SetRt(Lt(tmp)); //讓tmp的左結點作為x的右結點 if(Lt(tmp) != nil) Lt(tmp)->Setpre(x); tmp->Setpre(pre(x)); //讓x的父結點作為tmp的父結點 if(pre(x) == nil) root = tmp; //如果x是根結點，更新根結點為tmp else{ //如果x是左結點，則讓tmp為左結點，如果x是右結點，則讓tmp為右結點 if(Lt(pre(x)) == x) pre(x)->SetLt(tmp); else pre(x)->SetRt(tmp);}tmp->SetLt(x); //讓x作為tmp的左結點 x->Setpre(tmp); //讓tmp作為x的父結點x->Getsize() = 1;if(x->GetLt() != nil) x->Getsize() += x->GetLt()->Getsize();if(x->GetRt() != nil) x->Getsize() += x->GetRt()->Getsize(); tmp->Getsize() = x->Getsize() + 1;if(tmp->GetRt() != nil) tmp->Getsize() += tmp->GetRt()->Getsize(); } void RRotate(Node* x){Node* tmp = Lt(x);x->SetLt(Rt(tmp));if(Rt(tmp) != nil) Rt(tmp)->Setpre(x);tmp->Setpre(pre(x));if(pre(x) == nil) root = tmp;else{if(Rt(pre(x)) == x) pre(x)->SetRt(tmp);else pre(x)->SetLt(tmp);}tmp->SetRt(x);x->Setpre(tmp);x->Getsize() = 1;if(x->GetLt() != nil) x->Getsize() += x->GetLt()->Getsize();if(x->GetRt() != nil) x->Getsize() += x->GetRt()->Getsize(); tmp->Getsize() = x->Getsize() + 1;if(tmp->GetLt() != nil) tmp->Getsize() += tmp->GetLt()->Getsize(); }

紅黑樹的插入

插入結點的顏色為紅色（插入結點的顏色為黑色，可能破壞性質四，插入結點為紅色，可能破壞性質三，但修復性質三的代價比修復性質四的代價小，所以選擇插入結點的顏色為紅色）

第一步：?我們先按照二叉搜索樹樹插入節(jié)點的方式，插入節(jié)點
第二步：?為了不破壞紅黑樹的規(guī)則，我們插入節(jié)點后要對紅黑樹進行相應的調整

下面分兩種情況

第一種情況：?如果插入節(jié)點的父親是黑色節(jié)點，那么可以直接結束，不需要繼續(xù)調整了（沒有破壞紅黑樹的基本性質）
第二種情況：?如果插入節(jié)點為的父親為紅色節(jié)點，就需要進行相應的調整（性質4被破壞）

?

上圖為調整情況1：z的叔結點y是紅色的

這種情況在z.p和y都是紅色時發(fā)生。因為z.p.p是黑色的，所以將z.p和y都著為黑色，以此解決z和z.p都是紅色的問題，將z.p.p著為紅色一保持性質5。然后，把z.p.p作為新結點z來重復修正被破壞的性質，直到所有性質都滿足。指針z在樹中上移兩層。

?

情況2：z的叔結點y是黑色的且z是一個右孩子

情況3：z的叔結點y是黑色的且z是一個左孩子

在情況2和情況3中，z的叔結點y是黑色的，通過z是z.p的右孩子還是左孩子來區(qū)別這兩種情況。在情況2中，結點z是它父結點的右孩子，可以使用一個左旋來將此情形轉變?yōu)榍闆r3，此時結點z為左孩子。因為z和z.p都是紅色的，所以該旋轉對性質無影響。無論是直接進入情況3，還是通過情況2進入情況3，z的叔結點y總是是黑色的，否則就要執(zhí)行情況1。在情況3中，改變某些結點的顏色并做一次右旋，以保持性質5。這樣由于不再有兩個紅色結點相鄰，所有處理到處完畢。因為此時z.p是黑色的，無需再進行循環(huán)。

插入代碼如下：

void Insert(pair<T,V> p) {Node* y = nil;Node* x = root;Node* z = new Node(p,0,nil,nil,nil); //z為要插入的結點 while(x != nil){ //尋找插入的位置 y = x;if(p.first < x->Getdata()) x = Lt(x);else x = Rt(x);}z->Setpre(y); //讓y作為z的父結點 if(y == nil) root = z; //如果樹為空，則z為根結點 else if(z->Getdata() < y->Getdata()){ //如果z的key比y的key小，則z為y的左結點，否則為右 結點 y->SetLt(z);}else y->SetRt(z); z->SetLt(nil);z->SetRt(nil);z->Setcolor(0);FixAfterInsert(z); //插入之后的調整 } void FixAfterInsert(Node* z){while(color(z->Getpre()) == 0){ //如果z的父結點為紅色，進入循環(huán)，否則結束循環(huán) if(pre(z) == Lt(pre(pre(z)))){ //如果z的父結點是z的祖父結點的左結點 Node* y = Rt(pre(pre(z))); //y為z的叔結點 if(color(y) == 0){ //如果y結點為紅色進入情況1 pre(z)->Setcolor(1); //case1 將z的父節(jié)點的顏色改為黑色 y->Setcolor(1); //case1 將y的顏色改為黑色 pre(pre(z))->Setcolor(0); //case1 將祖父結點的顏色改為紅色 z = pre(pre(z)); //case1 將指針z上移兩層 continue; //進行下一次循環(huán) } //y結點為黑色的情況 if(z == Rt(pre(z))){ //case2 如果z是其父結點的右結點 z = pre(z); //case2 對z的父結點做左旋 LRotate(z); //case2 左旋之后z結點的key和val不變，只是右結點和父結點變了 }pre(z)->Setcolor(1); //case3 將z的父結點的顏色改為黑色 pre(pre(z))->Setcolor(0); //case3 將z的祖父結點的顏色改為紅色 RRotate(pre(pre(z))); //case3 對z的祖父結點右旋 }else{ //z的父結點是z的祖父結點的y右結點的情況，與z的父結點是z的祖父結點的y左結點的情況對稱 Node* y = Lt(pre(pre(z)));if(color(y) == 0){pre(z)->Setcolor(1); //case1y->Setcolor(1); //case1pre(pre(z))->Setcolor(0); //case1z = pre(pre(z)); //case1continue;}if(z == Lt(pre(z))){ //case2z = pre(z); //case2RRotate(z); //case2}pre(z)->Setcolor(1); //case3pre(pre(z))->Setcolor(0); //case3LRotate(pre(pre(z))); //case3}}root->Setcolor(1); //循環(huán)過程中有可能修改根結點的顏色，要保持根結點為黑色 }

紅黑樹的刪除

與插入操作相比，刪除操作要稍微麻煩一些。

首先要設計一個刪除過程中要使用到的替換函數(shù)transplant，代碼如下：

void transplant(Node* u,Node* v){if(pre(u) == nil) root = v; //如果u是根結點，則讓v為根結點 else if(u == Lt(pre(u))) pre(u)->SetLt(v); //如果u是左結點，則讓v為左結點 else pre(u)->SetRt(v); //如果u是右結點，則讓v為右結點v->Setpre(pre(u)); //讓u的父結點作為v的父結點 }

還要設計一個尋找key值最小的結點的函數(shù)minimum，代碼如下：

Node* minimum(Node* x){if(x == nil) return x;while(Lt(x) != nil){x->Getsize()--; //刪除時要維護size大小x = Lt(x);}return x; }

下面進入刪除：

刪除一個結點之后為了維護二叉搜索樹的性質，需要找一個結點來替代刪除結點的位置

第一步：?我們先按照二叉搜索樹樹刪除節(jié)點的方式，刪除節(jié)點
第二步：?為了不破壞紅黑樹的規(guī)則，我們刪除節(jié)點后要對紅黑樹進行相應的調整

下面分兩種情況：

第一種情況：刪除的結點有一個左結點或一個右結點不是葉結點，或左右結點都是葉結點。

如果左右結點都是葉結點則用葉結點替換要刪除的結點。如果刪除的結點有一個左結點或一個右結點不是葉結點，則用非葉結點替換要刪除的結點。

第二種情況：刪除的結點沒有葉結點。

用刪除結點的后繼結點替換刪除的結點，后繼結點是大于該結點且最小的結點。以刪除結點的右結點為根結點的樹中的最小結點就是刪除結點的后繼結點。由于后繼結點替代了刪除結點，后繼結點也需要有結點替代，由于后繼結點沒有左結點，則后繼結點的替代結點就是它的右結點。此時，有一種特殊情況，當刪除結點的后繼結點就是刪除結點的右結點時，后繼結點無需替代結點。

如果刪除的是黑色結點，則需要調整（破壞了性質5）。

調整的情況：

藍色表示可以是紅色也可以是黑色

?

情況1：x的兄弟結點w是紅色的

因為w必須有黑色子結點，所以可以改變w的x.p的顏色，然后對x.p做一次左旋而不違反紅黑樹的任何性質。現(xiàn)在，x的新兄弟結點是旋轉之前的w的某個子結點，其顏色為黑色。這樣就將情況1轉換為情況2、3或4處理。

當結點w為黑色時，屬于情況2、3和4；這些情況是由w的子結點的顏色來區(qū)分的。

情況2：x的兄弟結點w是黑色的，而且w的兩個子結點都是黑色的

因為w的顏色是黑色的，所以在刪除x結點時將w的顏色改為紅色，這樣B結點的左子樹和右子樹中都少了一個黑色結點。如果B結點是紅色的，則退出循環(huán)，讓B結點的顏色為黑色，補償一個黑色結點。如果B結點是黑色的，B結點無法補償一個黑色結點，則等效刪除了一個黑色結點，B結點為刪除結點的替代結點，繼續(xù)循環(huán)。

情況3：x的兄弟結點w是黑色的，w的左結點是紅色的，w的右結點是黑色的

可以交換w和w的左結點的顏色，然后對w進行右旋而不違反紅黑樹的任何性質。現(xiàn)在x的新兄弟結點w是一個有右孩子的黑色結點，這樣就將情況3轉換成了情況4。

情況4：x的兄弟結點w是黑色的，且w的右結點是紅色的

可以交換B和w的顏色，并讓E的顏色為黑色，然后對B進行一次左旋，這樣刪除x結點之后紅黑樹的性質沒有被破壞。因為旋轉前x結點的黑高等于C結點的黑高加一，所以在刪除x結點之后，B的左子樹的黑高等于右子樹的黑高。旋轉后B的黑高等于旋轉前D的黑高（旋轉后的B與旋轉前的D都有相同的子樹C）等于旋轉前E的黑高，而旋轉前E的黑高等于旋轉后E的黑高，所以旋轉后B的黑高和旋轉后E的黑高相等，旋轉前B的黑高等于旋轉前E的黑高加一，旋轉后D的黑高等于E的黑高加一，所以旋轉前B的黑高等于旋轉后D的黑高。所以紅黑樹的性質沒有被破壞。這時應該把x置為根結點，以結束循環(huán)。

刪除代碼如下：

bool Delete(Node* z){Node* y = z; //y為z的替代結點 int yoc = color(y); //記錄y的顏色 Node* x = z; //x為y的替代結點 if(Lt(z) == nil){ //z有兩個葉結點或左結點為葉結點 x = Rt(z);transplant(z,Rt(z)); //用z的右結點替換z }else if(Rt(z) == nil){ //z的右結點為葉結點 x = Lt(z);transplant(z,Lt(z)); //用z的左結點替換z }else{ //z沒有葉結點 y = minimum(Rt(z)); //讓y為z的后繼結點 yoc = color(y); //記錄y的顏色 x = Rt(y); //讓x為y的右結點 if(pre(y) == z){ //判斷特殊情況 x->Setpre(y);}else{ //當y不是z的右結點時 transplant(y,Rt(y)); //用y的右結點替換y y->SetRt(Rt(z)); //把z的右結點作為y右結點 Rt(y)->Setpre(y);}transplant(z,y); // 用y替換z y->SetLt(Lt(z)); //把z的左結點作為y的左結點 Lt(y)->Setpre(y);y->Setcolor(color(z)); //把y的顏色改為z的顏色 }delete z;if(yoc == 1){ //當刪除結點為黑色時，需要調整 FixAfterDelete(x);}return true; } bool Delete(T val){Node* tmp = this->root;while(tmp != nil){ //尋找要刪除的結點 if(tmp->Getdata() > val){tmp = tmp->GetLt();}else if(tmp->Getdata() < val){tmp = tmp->GetRt();}else break;}if(tmp == nil){ //沒有找到 return false;}else{return Delete(tmp); } } void FixAfterDelete(Node* x){while(x != root && color(x) == 1){ //當x不為根結點或x的顏色為黑色 if(Lt(pre(x)) == x){ //如果x的左結點 Node* w = Rt(pre(x)); //w是x的兄弟結點 if(color(w) == 0){ //如果w的顏色為紅色 w->Setcolor(1); //case1 讓w的顏色為黑色 pre(x)->Setcolor(0); //case1 讓x的父結點的顏色為紅色 LRotate(pre(x)); //case1 對x的父結點左旋 w = Rt(pre(x)); //case1 更新兄弟結點 }if(color(Lt(w)) == 1 && color(Rt(w)) == 1){ //如果w有兩個黑色子結點 w->Setcolor(0); //case2 //讓w的顏色為紅色 x = pre(x); //case2 //讓x為x的父節(jié)點 }else{if(color(Rt(w)) == 1){ //如果w的右結點為黑色 Lt(w)->Setcolor(1); //case3 讓w的左結點的顏色為黑色 w->Setcolor(0); //case3 讓w的顏色為紅色 RRotate(w); //case3 對w進行右旋 w = Rt(pre(x)); //case3 更新兄弟結點 }w->Setcolor(color(pre(x))); //case4 讓w和x的父結點交換顏色 pre(x)->Setcolor(1); //case4 讓x的父結點的顏色為黑色 Rt(w)->Setcolor(1); //case4 讓w的右結點的顏色為黑色 LRotate(pre(x)); //case4 對x的父結點進行左旋 x = root; //case4 讓x成為根結點，結束循環(huán) } }else{ //x是右結點的情況 與x是左結點的情況對稱 Node* w = Lt(pre(x));if(color(w) == 0){w->Setcolor(1); //case1pre(x)->Setcolor(0); //case1RRotate(pre(x)); //case1w = Lt(pre(x)); //case1}if(color(Lt(w)) == 1 && color(Rt(w)) == 1){w->Setcolor(0); //case2x = pre(x); //case2 }else{if(color(Lt(w)) == 1){Rt(w)->Setcolor(1); //case3w->Setcolor(0); //case3LRotate(w); //case3w = Lt(pre(x)); //case3}w->Setcolor(color(pre(x))); //case4pre(x)->Setcolor(1); //case4 Lt(w)->Setcolor(1); //case4 RRotate(pre(x)); //case4 x = root; //case4} }}x->Setcolor(1); }

前驅、后繼：

Node* Lt_node(Node* x){ //前驅 Node* tmp = x;if(tmp->GetLt() == nil){while(tmp->Getpre() != nil && tmp->Getpre()->GetLt() == tmp){tmp = tmp->Getpre();}tmp = tmp->Getpre();}else{tmp = tmp->GetLt();while(tmp->GetRt() != nil){tmp = tmp->GetRt();}}return tmp; } Node* Rt_node(Node* x){ //后繼 Node* tmp = x;if(tmp->GetRt() == nil){while(tmp->Getpre() != nil && tmp->Getpre()->GetRt() == tmp){tmp = tmp->Getpre();}tmp = tmp->Getpre();}else{tmp = tmp->GetRt();while(tmp->GetLt() != nil){tmp = tmp->GetLt();}}return tmp; } Node* Lfind(T key){ //key不一定在樹中，所以要分類Node* parent = nil;Node* current = root;Node* t = nil;while(current != nil){//當當前節(jié)點不為空時 尋找結點if(current->Getdata() > key){parent = current;current = current->GetLt();}else if(current->Getdata() < key){parent = current;current = current->GetRt();}else{t = Lt_node(current);break;}}if(current->Getdata() == key){ //處理同值的情況while(t->Getdata() == key){t = Lt_node(t);}return t;}if(parent->Getdata() > key){return Lt_node(parent);}else{return parent;} } Node* Rfind(T key){Node* parent = nil;Node* current = root;Node* t = nil;while(current != nil){//當當前節(jié)點不為空時 if(current->Getdata() > key){parent = current;current = current->GetLt();}else if(current->Getdata() < key){parent = current;current = current->GetRt();}else{t = Rt_node(current);break;}}if(current->Getdata() == key){while(t->Getdata() == key){t = Rt_node(t);}return t;}if(parent->Getdata() < key){return Rt_node(parent);}else{return parent;} }

尋找第k大、查找排名（相同結點不合并版本）

Node* findkth(int k,Node* p){if(p->GetLt() == nil){if(k == 1){return p;}else{return findkth(k-1,p->GetRt());}}else{if(p->GetLt()->Getsize() == k-1) return p;else if(p->GetLt()->Getsize() >= k) return findkth(k,p->GetLt());else return findkth(k-p->GetLt()->Getsize()-1,p->GetRt());} } int find_rank(T v,Node* p){if(p == nil) return 1;else if(p->Getdata() >= v) return find_rank(v,p->GetLt());else return (1 + (p->GetLt() ? p->GetLt()->Getsize() : 0 ) + find_rank(v,p->GetRt())); }

完整代碼：

#include <bits/stdc++.h> using namespace std; #define RED 0 //紅色結點 #define BLACK 1 //黑色結點 template<typename T,typename V> class redblacktree{private:class Node{private:pair<T,V> p;int s;bool color;//0代表紅色 1代表黑色Node* Lt;Node* Rt;Node* pre;public:Node(pair<T,V> _p,int _s,bool _color,Node* _Lt = nullptr,Node* _Rt = nullptr,Node* _pre = nullptr):p(_p),s(_s),color(_color),Lt(_Lt),Rt(_Rt),pre(_pre){}Node(Node* tmp):p(tmp->p),s(tmp->s),color(tmp->color),Lt(tmp->Lt),Rt(tmp->Rt),pre(tmp->pre){}Node*& GetLt() { return Lt;}Node*& GetRt() { return Rt;}Node*& Getpre() { return pre;}T& Getdata() { return p.first;}V& Getinfo() { return p.second;}pair<T,V>* Getpair(){ return &p;}bool Getcolor() const{ return color;}int& Getsize() { return s;}void SetLt(Node*& tmp){Lt = tmp;}void SetRt(Node*& tmp){ Rt = tmp;}void Setpre(Node*& tmp){ pre = tmp;}void Setdata(T tmp){ p.first = tmp;}void Setinfo(V tmp){ p.second = tmp;} void Setcolor(bool tmp){ color = tmp;}};bool color(Node* node){if(node == nil) return true;else return node->Getcolor();}void Setcolor(Node* node,bool col){node->Setcolor(col);}Node*& pre(Node* node){return node->Getpre();}Node*& Lt(Node* node){return node->GetLt();}Node*& Rt(Node* node){return node->GetRt();}void LRotate(Node* x){//左旋 Node* tmp = Rt(x); x->SetRt(Lt(tmp));if(Lt(tmp) != nil) Lt(tmp)->Setpre(x);tmp->Setpre(pre(x));if(pre(x) == nil) root = tmp;else{if(Lt(pre(x)) == x) pre(x)->SetLt(tmp);else pre(x)->SetRt(tmp);}tmp->SetLt(x);x->Setpre(tmp);x->Getsize() = 1;if(x->GetLt() != nil) x->Getsize() += x->GetLt()->Getsize();if(x->GetRt() != nil) x->Getsize() += x->GetRt()->Getsize(); tmp->Getsize() = x->Getsize() + 1;if(tmp->GetRt() != nil) tmp->Getsize() += tmp->GetRt()->Getsize();}void RRotate(Node* x){Node* tmp = Lt(x);x->SetLt(Rt(tmp));if(Rt(tmp) != nil) Rt(tmp)->Setpre(x);tmp->Setpre(pre(x));if(pre(x) == nil) root = tmp;else{if(Rt(pre(x)) == x) pre(x)->SetRt(tmp);else pre(x)->SetLt(tmp);}tmp->SetRt(x);x->Setpre(tmp);x->Getsize() = 1;if(x->GetLt() != nil) x->Getsize() += x->GetLt()->Getsize();if(x->GetRt() != nil) x->Getsize() += x->GetRt()->Getsize(); tmp->Getsize() = x->Getsize() + 1;if(tmp->GetLt() != nil) tmp->Getsize() += tmp->GetLt()->Getsize();}void transplant(Node* u,Node* v){if(pre(u) == nil) root = v;else if(u == Lt(pre(u))) pre(u)->SetLt(v);else pre(u)->SetRt(v);v->Setpre(pre(u));}Node* minimum(Node* x){if(x == nil) return x;while(Lt(x) != nil){x->Getsize()--;x = Lt(x);}return x;}Node* maximum(Node* x){if(x == nil) return x;while(Rt(x) != nil){x = Rt(x); }return x; }Node* Lt_node(Node* x){ //前驅 Node* tmp = x;if(tmp->GetLt() == nil){while(tmp->Getpre() != nil && tmp->Getpre()->GetLt() == tmp){tmp = tmp->Getpre();}tmp = tmp->Getpre();}else{tmp = tmp->GetLt();while(tmp->GetRt() != nil){tmp = tmp->GetRt();}}return tmp;}Node* Rt_node(Node* x){ //后繼 Node* tmp = x;if(tmp->GetRt() == nil){while(tmp->Getpre() != nil && tmp->Getpre()->GetRt() == tmp){tmp = tmp->Getpre();}tmp = tmp->Getpre();}else{tmp = tmp->GetRt();while(tmp->GetLt() != nil){tmp = tmp->GetLt();}}return tmp; } public:Node* root;Node* nil; redblacktree(){nil = new Node({-1,-1},0,BLACK,nil,nil,nil);root = nil;}class iterator{private:Node* _node;public:Node* Getnode(){ return _node;}iterator& operator++(){_node = _node->Rt_node();return *this;}iterator& operator--(){_node = _node->Lt_node();return *this;}iterator& operator=(iterator a){_node = a._node;return *this;}friend bool operator ==(iterator a,iterator b){return a.Getnode() == b.Getnode();}friend bool operator !=(iterator a,iterator b){return a.Getnode() != b.Getnode();}pair<T,V>* operator->(){ return _node->Getpair();} iterator(Node* __node = nullptr):_node(__node){}iterator(iterator const& iter):_node(iter._node){}}; Node* find(Node* x,T key){Node* tmp = x;while(tmp != nil){if(tmp->Getdata() > key){tmp = tmp->GetLt();}else if(tmp->Getdata() < key){tmp = tmp->GetRt();}else break;}return tmp;}Node* Lfind(T key){Node* parent = nil;Node* current = root;Node* t = nil;while(current != nil){//當當前節(jié)點不為空時 if(current->Getdata() > key){parent = current;current = current->GetLt();}else if(current->Getdata() < key){parent = current;current = current->GetRt();}else{t = Lt_node(current);break;}}if(current->Getdata() == key){while(t->Getdata() == key){t = Lt_node(t);}return t;}if(parent->Getdata() > key){return Lt_node(parent);}else{return parent;}}Node* Rfind(T key){Node* parent = nil;Node* current = root;Node* t = nil;while(current != nil){//當當前節(jié)點不為空時 if(current->Getdata() > key){parent = current;current = current->GetLt();}else if(current->Getdata() < key){parent = current;current = current->GetRt();}else{t = Rt_node(current);break;}}if(current->Getdata() == key){while(t->Getdata() == key){t = Rt_node(t);}return t;}if(parent->Getdata() < key){return Rt_node(parent);}else{return parent;}}void Insert(pair<T,V> p){Node* y = nil;Node* x = root;Node* z = new Node(p,1,RED,nil,nil,nil);while(x != nil){y = x;x->Getsize()++;if(p.first < x->Getdata()) x = Lt(x);else x = Rt(x);}z->Setpre(y);if(y == nil) root = z;else if(z->Getdata() < y->Getdata()){y->SetLt(z);}else y->SetRt(z);z->SetLt(nil);z->SetRt(nil);z->Setcolor(RED);FixAfterInsert(z);} void FixAfterInsert(Node* z){while(color(z->Getpre()) == RED){if(pre(z) == Lt(pre(pre(z)))){Node* y = Rt(pre(pre(z)));if(color(y) == RED){pre(z)->Setcolor(BLACK); //case1y->Setcolor(BLACK); //case1pre(pre(z))->Setcolor(RED); //case1z = pre(pre(z)); //case1continue;}if(z == Rt(pre(z))){ //case2z = pre(z); //case2LRotate(z); //case2}pre(z)->Setcolor(BLACK); //case3pre(pre(z))->Setcolor(RED); //case3RRotate(pre(pre(z))); //case3}else{Node* y = Lt(pre(pre(z)));if(color(y) == RED){pre(z)->Setcolor(BLACK); //case1y->Setcolor(BLACK); //case1pre(pre(z))->Setcolor(RED); //case1z = pre(pre(z)); //case1continue;}if(z == Lt(pre(z))){ //case2z = pre(z); //case2RRotate(z); //case2}pre(z)->Setcolor(BLACK); //case3pre(pre(z))->Setcolor(RED); //case3LRotate(pre(pre(z))); //case3}}root->Setcolor(BLACK);}bool Delete(Node* z){Node* y = z;int yoc = color(y);Node* x = z;if(Lt(z) == nil){x = Rt(z);transplant(z,Rt(z));}else if(Rt(z) == nil){x = Lt(z);transplant(z,Lt(z));}else{y = minimum(Rt(z));yoc = color(y);x = Rt(y);if(pre(y) == z){x->Setpre(y);}else{transplant(y,Rt(y));y->SetRt(Rt(z));Rt(y)->Setpre(y);}transplant(z,y);y->Getsize() = z->Getsize();y->SetLt(Lt(z));Lt(y)->Setpre(y);y->Setcolor(color(z));}delete z;if(yoc == BLACK){FixAfterDelete(x);}return true;}bool Delete(T val){Node* tmp = this->root;while(tmp != nil){tmp->Getsize()--;if(tmp->Getdata() > val){tmp = tmp->GetLt();}else if(tmp->Getdata() < val){tmp = tmp->GetRt();}else break;}if(tmp == nil){return false;}else{return Delete(tmp);}}void FixAfterDelete(Node* x){while(x != root && color(x) == BLACK){if(Lt(pre(x)) == x){Node* w = Rt(pre(x));if(color(w) == RED){w->Setcolor(BLACK); //case1pre(x)->Setcolor(RED); //case1LRotate(pre(x)); //case1w = Rt(pre(x)); //case1}if(color(Lt(w)) == BLACK && color(Rt(w)) == BLACK){w->Setcolor(RED); //case2x = pre(x); //case2 }else{if(color(Rt(w)) == BLACK){Lt(w)->Setcolor(BLACK); //case3w->Setcolor(RED); //case3RRotate(w); //case3w = Rt(pre(x)); //case3}w->Setcolor(color(pre(x))); //case4pre(x)->Setcolor(BLACK); //case4 Rt(w)->Setcolor(BLACK); //case4 LRotate(pre(x)); //case4 x = root; //case4} }else{Node* w = Lt(pre(x));if(color(w) == RED){w->Setcolor(BLACK); //case1pre(x)->Setcolor(RED); //case1RRotate(pre(x)); //case1w = Lt(pre(x)); //case1}if(color(Lt(w)) == BLACK && color(Rt(w)) == BLACK){w->Setcolor(RED); //case2x = pre(x); //case2 }else{if(color(Lt(w)) == BLACK){Rt(w)->Setcolor(BLACK); //case3w->Setcolor(RED); //case3LRotate(w); //case3w = Lt(pre(x)); //case3}w->Setcolor(color(pre(x))); //case4pre(x)->Setcolor(BLACK); //case4 Lt(w)->Setcolor(BLACK); //case4 RRotate(pre(x)); //case4 x = root; //case4} }}x->Setcolor(BLACK);}Node* findkth(int k,Node* p){if(p->GetLt() == nil){if(k == 1){return p;}else{return findkth(k-1,p->GetRt());}}else{if(p->GetLt()->Getsize() == k-1) return p;else if(p->GetLt()->Getsize() >= k) return findkth(k,p->GetLt());else return findkth(k-p->GetLt()->Getsize()-1,p->GetRt());}} int find_rank(T v,Node* p){if(p == nil) return 1;else if(p->Getdata() >= v) return find_rank(v,p->GetLt());else return (1 + (p->GetLt() ? p->GetLt()->Getsize() : 0 ) + find_rank(v,p->GetRt()));}Node* begin(){Node* t = root;while(t->Lt_node() != nil){t = t->Lt_node();}return t;} Node* end(){Node* t = root;while(t->Rt_node() != nil){t = t->Rt_node();}return t;} }; int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);redblacktree<int,int>* mp = new redblacktree<int,int>();int n,m,num;cin >> n;for(int i = 0;i < n; i++){cin >> m >> num;if(m == 1){mp->Insert({num,1});}else if(m == 2){mp->Delete(num);}else if(m == 3){cout << mp->find_rank(num,mp->root) << "\n";}else if(m == 4){cout << mp->findkth(num,mp->root)->Getdata() << "\n";}else if(m == 5){cout << mp->Lfind(num)->Getdata() << "\n";}else if(m == 6){cout << mp->Rfind(num)->Getdata() << "\n";}} return 0; }

treap版本的

在二叉搜索樹中，在某些情況下有可能會讓二叉搜索樹退化成一條鏈，為了解決這樣的問題，在樹的結點里加一個修正值，由樹的結點的val和fix共同決定樹的結構。fix值是隨機的。

treap就是tree + heap，其中key值滿足二叉搜索樹的性質，fix值滿足堆的性質。

插入結點操作：先從根節(jié)點開始，一步步尋找插入位置，一旦發(fā)現(xiàn)空結點就插入，插入之后，判斷當前的結點的fix值是否滿足堆的性質，如果不滿足就進行旋轉調整，旋轉時并不破壞樹的二叉搜索樹的性質，旋轉之后有可能上一層的結點的fix值的堆性質被破壞，所以要一步步向上判斷。

刪除結點操作：先尋找刪除結點的位置，找到后如果該結點沒有葉結點就直接刪除，如果該結點有一個葉結點就用葉結點去替代。如果有兩個葉結點就進行適當?shù)男D，直到該結點有一個葉結點或沒有葉結點。

完整代碼：指針實現(xiàn)版本

#include <bits/stdc++.h> using namespace std;class Treap{private:class Node{private:Node* Lt;Node* Rt;int val;int fix;int size;public:Node(int val,int fix):Lt(nullptr),Rt(nullptr),val(val),fix(fix),size(1){}Node*& GetLt(){ return Lt;}Node*& GetRt(){ return Rt;}void SetLt(Node* t){ Lt = t;}void SetRt(Node* t){ Rt = t;}int Getval(){ return val;}int Getfix(){ return fix;}int& Getsize(){ return size;}};Node*& Lt(Node* node){return node->GetLt();}Node*& Rt(Node* node){return node->GetRt();}int Getsize(Node*& p){if(p == nullptr) return 0;else return p->Getsize();}void update(Node*& p){p->Getsize() = Getsize(p->GetLt()) + Getsize(p->GetRt()) + 1;}void LRotate(Node*& p){Node* tmp = p->GetRt();p->SetRt(tmp->GetLt());tmp->SetLt(p);update(p);p = tmp;update(p);}void RRotate(Node*& p){Node* tmp = p->GetLt();p->SetLt(tmp->GetRt());tmp->SetRt(p);update(p);p = tmp;update(p);}public:Treap():root(nullptr){}Node* root;void Insert(Node*& p,int num){if(p == nullptr){p = new Node(num,rand());return;}if(num < p->Getval()){Insert(p->GetLt(),num);update(p);if(p->GetLt()->Getfix() < p->Getfix()) RRotate(p);}else{Insert(p->GetRt(),num);update(p);if(p->GetRt()->Getfix() < p->Getfix()) LRotate(p);}}void Delete(Node*& p,int num){if(p == nullptr) return;if(p->Getval() == num){if(p->GetLt() != nullptr && p->GetRt() != nullptr){if(p->GetLt()->Getfix() < p->GetRt()->Getfix()){RRotate(p);Delete(p->GetRt(),num);}else{LRotate(p);Delete(p->GetLt(),num);}update(p);}else{if(p->GetLt() == nullptr && p->GetRt() == nullptr){p = nullptr;}else{if(p->GetLt()) p = p->GetLt();else p = p->GetRt();}} }else{if(num < p->Getval()) Delete(p->GetLt(),num);else Delete(p->GetRt(),num);update(p);}}int GetRank(Node *&p,int num)//找到x的排名，=找有多少個元素小于x{if(p == nullptr) return 0;//空節(jié)點不計數(shù) if(p->Getval() >= num) return GetRank(p->GetLt(), num);//去左子樹算排名 int Lsize = 0;if(p->GetLt() != nullptr) Lsize = p->GetLt()->Getsize();return Lsize + GetRank(p->GetRt(), num) + 1;//返回排名 }int Getkth(Node *&p,int k)//找排名為k的元素 {int Lsize = 0 ;if(p->GetLt()) Lsize = p->GetLt()->Getsize();//左子樹大小 if(k == Lsize + 1) return p->Getval();//找到返回 if(k <= Lsize ) return Getkth(p->GetLt(),k);//是其左子樹的第k名 else return Getkth(p->GetRt(),k-Lsize-1);//是其右子樹的k-lsize-1名 } int Getpre(Node* p,int num){if(p == nullptr) return 0;if(p->Getval() >= num) return Getpre(p->GetLt(),num);int tmp = Getpre(p->GetRt(),num);if(tmp != 0) return tmp;else return p->Getval();}int Getsuc(Node* p,int num){if(p == nullptr) return 0;if(p->Getval() <= num) return Getsuc(p->GetRt(),num);int tmp = Getsuc(p->GetLt(),num);if(tmp != 0) return tmp;else return p->Getval();}}; int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);Treap* t = new Treap;int n,m,opt;cin >> n;for(int i = 0;i < n; i++){cin >> m >> opt;if(m == 1){t->Insert(t->root,opt);}else if(m == 2){t->Delete(t->root,opt);}else if(m == 3){cout << t->GetRank(t->root,opt)+1 << '\n';}else if(m == 4){cout << t->Getkth(t->root,opt) << '\n';}else if(m == 5){cout << t->Getpre(t->root,opt) << '\n';}else if(m == 6){cout << t->Getsuc(t->root,opt) << '\n';}}return 0; }

總結

以上是生活随笔為你收集整理的洛谷P3369 【模板】普通平衡树 红黑树实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。