4.1 二叉搜索樹

BinNode* search (const T &e , BinNode* _hot, BinNode* x){
    while(true){
        if(!x) {return x;}
        else if(e<x->data){
            _hot=x;
            x=x->lc;
        }
        else if(e>x->data){
            _hot=x;
            x=x->rc;
        }
        else if(e==x->data){
            return x;
        }
    }
}
BinNode* search(const T &e){
    return search(e, _root,_hot);
}

BinNode * insert(const T &e){
    BinNode* x=search(e);
    if(x) return x;//duplicated
    x= new BinNode*(e,_hot);
    _size++;
    updateHeightAbove(x);
    return x;
}

BinNode * remove(const T &e){
    BinNode * x=search(e);
    BinNode* succ;
    if(!x) return false;
    if(!x->rc){
        succ=x=x->lc
    }
    else if((!x->lc)){
        succ=x=x->rc;
    }
    else{
        BinNode w=x;
        w=w.succ();
        swap(x->data,w->data);
        BinNode *u =w->parent;
        ((u==x)?u->rc:u->lc)=succ=w->rc;//w only has rc
    }
    _hot=w->parent;//father of deleted elem;
    if(succ) succ->parent =_hot;
    delete w->data;
    delete ->w;
    _size--;
    updateHeightAbove(_hot);
    return succ;
}

4.2 控制樹高 ，制造平衡二叉搜索樹

zig右旋
zag左旋
不改變中序遍歷順序崇棠，
通過增加局部限制询刹，保證平衡性沐兰，紅黑樹通過根節(jié)點到葉子節(jié)點黑節(jié)點數相同來保證。AVL樹通過兄弟節(jié)點高度差不大于1來保證比原。
保證了單次動態(tài)修改后最多只有l(wèi)ogn 出失去平衡，在logn時間內改回來锨侯。

4.2 AVL樹

控制平衡因子<2保證（左右子樹高度差）

Balanced (x){return stature(x->lc)==stature(x->rc);}//ideal
BalFac(x){ return stature(x->lc)-stature(x->rc);}
AVLBal(x){return (-2<BalFac(x))&&(BalFac(x)<2);}

remove（x）后僅單個節(jié)點失衡，insert后多個節(jié)點失衡
失衡節(jié)點集中UT（x）深滚，高度不低于x的祖父，從x向上搜索，首個失衡節(jié)點即為

既然g（x）由于x引入而失衡皂贩，所以g（x）的孩子p， p的孩子v都沒有失衡,可由g（x）找到p和v

tallerChild(x) {stature(x->lc)>stature(x->rc)?(x->lc):(
    stature(x->lc)<stature(x->rc)?x->rc:(
        IsLChild(*(x))?x->lc:x->rc;//與父親同側者 zig/zag
    )
)
}

p、v在一側挤聘，采取單旋手段
單旋 g（x）插入右子樹邊高，zag（g（x））
g（x）插入左邊子樹高， zig（g（x）） 可調整平衡

雙旋g（x）p v
左右键闺，zag（p），zig（g）
右左畅铭，zig（p），zag（g）

insert(const T& e){
    BinNode* x=search(e);
    if(x) return x;
    BinNode* xx= x =new BinNode(e, _hot); _size++;
    //_hot增高炉擅，_hot的父親有可能失衡
    for (BinNode *g=_hot;g;g=g->parent){//從x之父向上搜索
       if(!AVLBalanced(g)){//即找到g（x）//第一個失衡的祖先
           //從g往下找兩次較高孩子莹汤，若同樣高抹竹，取與父親同側（單旋）
           //g->parent->self
           FromParentTo(*g)=rotateAt(tallerChild(tallerChild(g)));//采用3+4算法，使其恢復平衡
           break;
       }
       else{
           updateHeight(g);//g不失衡袄琳，高度也可能增加//插入調整局部，更新高度避免每次全局調整
       }
    }
    return xx;//返回新節(jié)點
}

與插入操作不同夯秃，刪除后介陶，失衡節(jié)點僅一個g（x），其高度與失衡前相同国撵，g（x）有可能是x父親
沿著parent指針上行，可找到g（x）环础，g（x）另一側必有非空孩子p，-取p較高孩子為v（相同取同側）//同側調一次，不同側調兩次

• 單旋
  設g（x）平衡因子為2（左側高（-2對稱）） fac（p）非負時，即同側谓罗，調整g即可使得g恢復平衡

  
  
  image.png

• 雙旋
  fac（p）為負時胯舷，即不同側炊汹，需要先調整p，再調整g（雙旋）
  g調整完成后，g的高度有可能降低，導致祖先失衡（當g為高祖先的短分枝時）稱為失衡傳播殊轴，可沿著parent繼續(xù)向前，重復調整

  
  
  image.png
  
  

  在此過程中的任一時刻， 至多只有一個失衡的節(jié)點;高層的某一節(jié)點由平衡轉為失衡塑悼，只可能發(fā)生在下層失衡節(jié)點恢復平 衡之后馍佑。因此崇众，可沿parent指針逐層遍歷所有祖先诫钓，每找到一個失衡的祖先節(jié)點问拘，即可套用以 上方法使之恢復平衡

remove(const T& e){
    BinNode* x=search(e); if(!e) return false;
    removeAt(x,_hot); _size--;//依然是二叉搜索樹
    for(BinNode* g=_hot;g;g=g->parent){
        if(!AVLBalanced(*g)){
            g=FromParentTo(g)=rotateAt(tallerChild(tallerChild(g)));
        }
        updateHeight(g);
    }
    return true;
}

統(tǒng)一平衡算法：
根據失衡節(jié)點調整其左右孩子位置關系，分別做單選和雙旋操作寞忿，代碼量大而復雜辖佣。將導致調試困難。
可將失衡節(jié)點子樹統(tǒng)一劃分為四個子樹T0世蔗、T1、T2朗兵、T3
重新排列后中序遍歷結果應該是T0 a T1 b T2 c T3污淋，四顆子樹彼此高度差不超過一層//實際上覆蓋了單旋和雙旋大所有情況。
重構過程僅涉及3個節(jié)點和4顆樹余掖。故稱為3+4重構connnect34

image.png

connnect34(BinNode* a, BinNode *b, BinNode *c, BinNode *T1, BinNode * T2, BinNode* T3, BinNode* T4){
    a->lc=T0;
    if(T0) T0->parent=a;
    a->rc=T1;
    if(T1) T1->parent=a;
    updateHeight(a);
    c->lc=T2;
    if(T2) T2->parent=c;
    c->rc=T3;
    if(T3) T3->parent=c;
    updateHeight(c);
    b->lc=a;
    a->parent=b;
    b->rc=c;
    c->parent=b;
    update(b);
    return b;
}

旋轉變換統(tǒng)一算法

rotateAt(BinNode *v){
BinNode* p=v->parent; BinNode *g=p->parent;
if(IsLChild(*p)){//zig (zig(g))
    if(IsLChild(*v)){//zig-zig
        p->parent=g->parent;
        return connect34(v,p,g,v->lc,v->rc,p->rc,g->rc);
    }
    else{//zig-zag   (zag(p))
    v->parent=g->parent;
    return connect(p,v,g,p->lc,v->lc,v->rc,g->rc);
    }
}
else{//zag
    if(IsRChild(*v)){//zag-zag
        p->parent=g->parent;
        connect34(g,p,v,g->lc,p->lc,v->lc,v->rc);
    }
    else{//zag-zig
        v->parent=g->parent;
        connect34(g,v,p,g->lc,v->lc,v->rc,p->rc);
    }
}

}

4.2伸展樹 Splay

無需維護樹高、平衡因子盐欺，不需要嚴格保證平衡狀態(tài)赁豆。分攤效率高
按照最常用優(yōu)先，引入伸展樹
根據數據局部性1.被訪問過的節(jié)點更容易被訪問 2.下一個被訪問節(jié)點在上一個周圍
只需將訪問完成節(jié)點調整到根附近冗美，保證前后等價即可魔种。加快訪問速度

一種直接的方法：訪問一個節(jié)點后，以他的父親節(jié)點為中心旋轉墩衙，直到成為樹根
無論查找或插 入务嫡，甚至“刪除”都可通過3次旋轉，將該樹等價變換為以E為根的另一棵二叉搜索樹漆改。

image.png

• 最壞情況
  不難驗證心铃，若從空樹開始依次插入關鍵碼{ 1, 2, 3, 4, 5 }，且其間采用如上調整策略挫剑，
  則可得到如圖8.2(a)所示的二叉搜索樹去扣。接下來，若通過search()接口樊破，再由小到大地依次訪 問各節(jié)點一次愉棱，則該樹在各次訪問之后的結構形態(tài)將如圖(b~f)所示。

  
  
  image.png
  
  

  隨著節(jié)點E的逐層上升哲戚，兩側子樹的結構也不斷地調整奔滑，故這一過程也稱作伸展(splaying)， 而采用這一調整策略的二叉搜索樹也因此得名顺少。不過朋其，為實現真正意義上的伸展樹王浴，還須對以上 策略做點微妙而本質的改進。之所以必須改進梅猿，是因為目前的策略仍存在致命的缺陷--對于很多訪問序列氓辣，單次訪問的分攤時間復雜度在極端情況下可能高達o(n)。

一般地袱蚓，若節(jié)點總數為n钞啸，則旋轉操作的總次數應為:

如此分攤下來，每次訪問平均需要O(n)時間喇潘。很遺憾体斩，這一效率不僅遠遠低于AVL樹，而且甚至 與原始的二叉搜索樹的最壞情況相當响蓉。而事實上硕勿，問題還遠不止于此。

對于規(guī)模為任意n的伸展樹枫甲， 只要按關鍵碼單調的次序源武，周期性地反復進行查找，則無論總的訪問次數m >> n有多大想幻，就分 攤意義而言粱栖，每次訪問都將需要O(n)時間!
那么，這類最壞的訪問序列能否回避?具體地脏毯，又應該如何回避?

雙層伸展：

為克服上述伸展調整策略的缺陷闹究，一種簡便且有效的方法就是:將逐層伸展改為雙層伸展。 具體地食店，每次都從當前節(jié)點v向上追溯兩層(而不是僅一層)渣淤，并根據其父親p以及祖父g的相對 位置，進行相應的旋轉吉嫩。以下分三類情況价认，分別介紹具體的處理方法。

• zig-zig（zag-zag）
  針對這種情況自娩，首先以節(jié)點g為軸做順時針旋轉zig(g)用踩，其效果如圖(b)所示。然后忙迁，再以p
  為軸做順時針旋轉zig(p)脐彩，其效果如圖(c)所示。如此連續(xù)的兩次zig旋轉姊扔，合稱zig-zig調整

  
  
  image.png

• zig-zag（zag-zig）
  針對這種情況惠奸，首先以節(jié)點p為軸做順時針旋轉zig(p)，其效果如(b)所示恰梢。然后佛南，再以g
  為軸做逆時針旋轉zag(g)证九，其效果如圖(c)所示。如此zig旋轉再加zag旋轉共虑，合稱zig-zag調整。同樣地呀页，另一完全對稱的情形--v是p的右孩子妈拌，而p是g的左孩子則可通過zag旋轉再
  加zig旋轉實現調整，合稱zag-zig操作

  
  
  image.png
  
  

  -zig/zag
  若v最初的深度為奇數蓬蝶，則經 過若干次雙層調整至最后一次調整時尘分，v的父親p即是 樹根r。將v的左丸氛、右子樹記作X和Y培愁，節(jié)點p = r的另 一子樹記作Z。

  
  
  image.png
• 效果與效率
  綜合以上各種情況缓窜，每經過一次雙層調整操作定续，節(jié)點v都會上升兩層。若v的初始深度depth(v)為偶數禾锤，則最終v將上升至樹根私股。若depth(v)為奇數，則當v上升至深度為1時恩掷，不妨最后再相應 地做一次zig或zag單旋操作倡鲸。無論如何，經過depth(v)次旋轉后黄娘，v最終總能成為樹根峭状。

重新審視圖8.2的最壞實例不難發(fā)現，這一訪問序列導致?(n)平均單次訪問時間的原因逼争， 可以解釋為:在這一可持續(xù)重復的過程中优床，二叉搜索樹的高度始終不小于n/2;而且，至少有 一半的節(jié)點在接受訪問時氮凝，不僅沒有如最初設想的那樣靠近樹根羔巢，而且反過來恰恰處于最底層。 從樹高的角度看罩阵，問題根源也可再進一步地解釋為:在持續(xù)訪問的過程中竿秆，樹高依算術級數逐步 從n - 1遞減至n/2，然后再逐步遞增回到n - 1

• 效果
  稍作對比不難看出稿壁，就調整之后的局部結構而言幽钢，zig-zag和zag-zig調整與此前的逐層伸 展完全一致(亦等效于AVL樹的雙旋調整)，而zig-zig和zag-zag調整則有所不同傅是。事實上匪燕， 后者才是雙層伸展策略優(yōu)于逐層伸展策略的關鍵所在蕾羊。以如圖8.6(b)所示的二叉搜索樹為例， 在find(1)操作之后采用逐層調整策略與雙層調整策略的效果帽驯，分別如圖(a)和圖(c)所示龟再。

  
  
  image.png
  
  

  可見，最深節(jié)點(1)被訪問之后再經過雙層調整尼变，不僅同樣可將該節(jié)點伸展至樹根利凑，而且 同時可使樹的高度接近于減半。就樹的形態(tài)而言嫌术，雙層伸展策略可“智能”地“折疊”被訪問的 子樹分支哀澈，從而有效地避免對長分支的連續(xù)訪問

這就意味著，即便節(jié)點v的深度為O(n)度气，雙層 伸展策略既可將v推至樹根割按，亦可令對應分支的長度以幾何級數(大致折半)的速度收縮。

image.png

一旦這類“壞”節(jié)點 被“碰觸”到磷籍，經過隨后的雙層伸展适荣，其對應的分支都會收縮至長度大致折半。于是择示，即便每次 都“惡意地”試圖訪問最底層節(jié)點束凑，最壞情況也不會持續(xù)發(fā)生

在改用“雙 層伸展”策略之后，伸展樹的單次操作均可在分攤的O(logn)時間內完成

#include "../BST/BST.h" //基亍BST實現Splay
template <typename T> class Splay : public BST<T> { //由BST派生癿Splay樹模板類 protected:
BinNodePosi(T) splay(BinNodePosi(T) v); //將節(jié)點v伸展至根 public:
BinNodePosi(T) & search(const T& e); //查找(重寫) BinNodePosi(T) insert(const T& e); //插入(重寫) bool remove(const T& e); //初除(重寫)
};

需強調的是栅盲，與一般的二叉搜索樹不同汪诉，伸展
樹的查找也會引起整樹的結構調整，故search()操作也需重寫

template <typename NodePosi> inline //在節(jié)點*p不*lc(可能為空)間建立父(左)子關系
void attachAsLChild(NodePosi p, NodePosi lc) { p->lChild = lc; if (lc) lc->parent = p; }

template <typename NodePosi> inline //在節(jié)點*p不*rc(可能為空)間建立父(右)子關系
void attachAsRChild(NodePosi p, NodePosi rc) { p->rChild = rc; if (rc) rc->parent = p; }

template <typename T> //Splay樹伸展算法:從節(jié)點v出収逐局伸展
BinNodePosi(T) Splay<T>::splay(BinNodePosi(T) v) { //v為因最近訪問而需伸展的節(jié)點位置
 if ( !v ) return NULL; BinNodePosi(T) p; BinNodePosi(T) g; //*v的父親與祖父
    while ( ( p = v->parent ) && ( g = p->parent ) ) { //自下而上谈秫，反復對*v做雙層伸展
       BinNodePosi(T) gg = g->parent; //每輪之后*v都以原曾祖父（great-grand parent）為父
       if ( IsLChild ( *v ) )
          if ( IsLChild ( *p ) ) { //zig-zig
             attachAsLChild ( g, p->rc ); attachAsLChild ( p, v->rc );
             attachAsRChild ( p, g ); attachAsRChild ( v, p );
          } else { //zig-zag
             attachAsLChild ( p, v->rc ); attachAsRChild ( g, v->lc );
             attachAsLChild ( v, g ); attachAsRChild ( v, p );
          }
       else if ( IsRChild ( *p ) ) { //zag-zag
          attachAsRChild ( g, p->lc ); attachAsRChild ( p, v->lc );
          attachAsLChild ( p, g ); attachAsLChild ( v, p );
       } else { //zag-zig
          attachAsRChild ( p, v->lc ); attachAsLChild ( g, v->rc );
          attachAsRChild ( v, g ); attachAsLChild ( v, p );
       }
       if ( !gg ) v->parent = NULL; //若*v原先的曾祖父*gg不存在扒寄，則*v現在應為樹根
       else //否則，*gg此后應該以*v作為左或右孩子
          ( g == gg->lc ) ? attachAsLChild ( gg, v ) : attachAsRChild ( gg, v );
       updateHeight ( g ); updateHeight ( p ); updateHeight ( v );
    } //雙層伸展結束時拟烫，必有g == NULL该编，但p可能非空
    if ( p = v->parent ) { //若p果真非空，則額外再做一次單旋
       if ( IsLChild ( *v ) ) { attachAsLChild ( p, v->rc ); attachAsRChild ( v, p ); }
       else                   { attachAsRChild ( p, v->lc ); attachAsLChild ( v, p ); }
       updateHeight ( p ); updateHeight ( v );
    }
    v->parent = NULL; return v;
 } //調整之后新樹根應為被伸展的節(jié)點硕淑，故返回該節(jié)點的位置以便上層函數更新樹根

• 查找算法的實現 在伸展樹中查找任一關鍵碼e的過程

template <typename T> BinNodePosi(T) & Splay<T>::search(const T& e) { //在伸展樹中查找兲鍵碼e BinNodePosi(T) p = searchIn(_root, e, _hot = NULL);
_root = splay((p ? p : _hot)); //將最后一個被詎問癿節(jié)點伸展至根
return _root;
} //不其它BST不同课竣，無諱查找成功不否，_root都指向最后被詎問癿節(jié)點

首先置媳，調用二叉搜索樹的通用算法searchIn()(代碼7.3)嘗試查找具有關鍵碼e的節(jié)點于樟。 無論查找是否成功，都繼而調用splay()算法拇囊，將查找終止位置處的節(jié)點伸展到樹根迂曲。

• 插入
  為將節(jié)點插至伸展樹中，固然可以調用二叉搜索樹的標準插入算法BST::insert()寥袭，再通過雙層伸展路捧，將新插入的節(jié)點提升至樹根关霸。
  然而，以上接口Splay::search()已集成了splay()伸展功能杰扫，故查找返回后队寇，樹根節(jié)點 要么等于查找目標(查找成功)，要么就是_hot章姓，而且恰為擬插入節(jié)點的直接前驅或直接后繼 (查找失敗)英上。因此，不妨改用如下方法實現Splay::insert()接口啤覆。

  
  
  image.png

• 刪除
  為從伸展樹中刪除節(jié)點，固然也可以調用二叉搜索樹標準的節(jié)點刪除算法BST::remove() (190頁代碼7.6)惭聂，再通過雙層伸展窗声，將該節(jié)點此前的父節(jié)點提升至樹根。
  然而辜纲，同樣鑒于Splay::search()已集成了splay()伸展功能笨觅，且在成功返回后，樹根節(jié) 點恰好就是待刪除節(jié)點耕腾。因此见剩，亦不妨改用如下方法實現Splay::remove()接口。

  
  
  image.png

4.4 B-樹

實踐證明扫俺，分級存儲才是行之有效的方法苍苞。在由內存與外存(磁盤)組成的二級存儲系統(tǒng)中， 數據全集往往存放于外存中狼纬，計算過程中則可將內存作為外存的高速緩存羹呵，存放最常用數據項的 復本。借助高效的調度算法疗琉，如此便可將內存的“高速度”與外存的“大容量”結合起來冈欢。

• 多路搜索樹
  當數據規(guī)模大到內存已不足以容納時，常規(guī)平衡二叉搜索樹的效率將大打折扣盈简。其原因在于凑耻，
  查找過程對外存的訪問次數過多。

比如可以兩層為間隔柠贤，將各節(jié)點與其左香浩、右孩子合并為“大節(jié)點”: 原節(jié)點及其孩子的共三個關鍵碼予以保留;孩子節(jié)點原有的四個分支也予以保留并按中序遍歷次 序排列;節(jié)點到左、右孩子的分支轉化為“大節(jié)點”內部的搜索种吸，在圖中表示為水平分支弃衍。如此 改造之后，每個“大節(jié)點”擁有四個分支坚俗，故稱作四路搜索樹镜盯。
這一策略還可進一步推廣岸裙，比如以三層為間隔，將各節(jié)點及其兩個孩子速缆、四個孫子合并為含 有七個關鍵碼降允、八個分支的“大節(jié)點”，進而得到八路搜索樹艺糜。一般地剧董，以k層為間隔如此重組， 可將二叉搜索樹轉化為等價的2^k路搜索樹破停，統(tǒng)稱多路搜索樹(multi-way search tree)翅楼。

image.png

實際上，在此時的搜索每下降一層真慢，都以“大節(jié)點” 為單位從外存讀取一組(而不再是單個)關鍵碼毅臊。更為重要的是，這組關鍵碼在邏輯上與物理上 都彼此相鄰黑界，故可以批量方式從外存一次性讀出管嬉，且所需時間與讀取單個關鍵碼幾乎一樣。

• 多路平衡搜索樹
  m階B -tree朗鸠，所謂m階B-樹4(B-tree)蚯撩，即m路平衡搜索樹(m >2)

  
  
  image.png

#include "../vector/vector.h"
#define BTNodePosi(T) BTNode<T>* //B-樹節(jié)點位置
template <typename T> struct BTNode { //B-樹節(jié)點模板類 // 成員(為簡化描述起見統(tǒng)一開放，讀者可根據需要迕一步封裝)
BTNodePosi(T) parent; //父節(jié)點
Vector<T> key; //兲鍵碼向量
Vector<BTNodePosi(T)> child; //孩子向量(其長度總比key夗一)
// 極造函數(注意:BTNode叧能作為根節(jié)點創(chuàng)建烛占，而且刜始時有0個兲鍵碼和1個空孩子指針) BTNode() { parent = NULL; child.insert(0, NULL); }
BTNode(T e, BTNodePosi(T) lc = NULL, BTNodePosi(T) rc = NULL) {
parent = NULL; //作為根節(jié)點胎挎，而且刜始時
key.insert(0, e); //叧有一個關鍵碼，以及 
child.insert(0, lc); child.insert(1, rc); //兩個孩子
 if (lc) lc->parent = this; if (rc) rc->parent = this;
}
};

#include "BTNode.h" //引入B-樹節(jié)點類 2
3 template <typename T> class BTree { //B-樹模板類
4 protected:
5 int _size; //存放癿兲鍵碼總數
6 int _order; //B-樹癿階次忆家，至少為3——創(chuàng)建時指定呀癣，一般丌能修改
7 BTNodePosi(T) _root; //根節(jié)點
8 BTNodePosi(T) _hot; //BTree::search()最后詎問癿非空(除非樹空)癿節(jié)點位置
9 void solveOverflow(BTNodePosi(T)); //因揑入而上溢乀后癿分裂處理
10 void solveUnderflow(BTNodePosi(T)); //因初除而下溢乀后癿合幵處理
11 public:
12 BTree(int order = 3) : _order(order), _size(0) //極造函數:默訃為最低癿3階
13 { _root = new BTNode<T>(); }
14 ~BTree() { if (_root) release(_root); } //枂極函數:釋放所有節(jié)點
15 int const order() { return _order; } //階次
16 int const size() { return _size; } //觃模
17 BTNodePosi(T) & root() { return _root; } //樹根
18 bool empty() const { return !_root; } //刞空
19 BTNodePosi(T) search(const T& e); //查找
20 bool insert(const T& e); //揑入
21 bool remove(const T& e); //初除
22 }; //BTree

• 關鍵碼查找

template <typename T> BTNodePosi(T) BTree<T>::search(const T& e) { //在B-樹中查找兲鍵碼e BTNodePosi(T) v = _root; _hot = NULL; //從根節(jié)點出収
while (v) { //逐局查找
Rank r = v->key.search(e); //在弼前節(jié)點中，找刡丌大亍e癿最大兲鍵碼
if ((0 <= r) && (e == v->key[r])) return v; //成功:在弼前節(jié)點中命中目標兲鍵碼
_hot = v; v = v->child[r + 1]; //否則弦赖，轉入對應子樹(_hot指向其父)——需做I/O项栏，最費時間
} //返里在向量內是二分查找，但對通常癿_order可直接頇序查找 return NULL; //失敗:最終抵達外部節(jié)點
}

與二叉搜索樹類似蹬竖，B-樹的每一次查找過程中沼沈，在每一高度上至多訪問 一個節(jié)點。這就意味著币厕，對于高度為h的B-樹列另，外存訪問不超過O(h - 1)次。

存有N個關鍵碼的m階B-樹的高度h = O(logmN)

• 上溢與分裂
  一般地旦装，剛發(fā)生上溢的節(jié)點页衙，應恰好含有m個關鍵碼。若取s = ?m/2?，則它們依次為:
  { k0, ..., ks-1; ks; ks+1, ..., km-1 } 可見店乐，以ks為界艰躺，可將該節(jié)點分前、后兩個子節(jié)點眨八，且二者大致等長腺兴。于是，可令關鍵碼ks
  上升一層廉侧，歸入其父節(jié)點(若存在)中的適當位置页响，并分別以這兩個子節(jié)點作為其左、右孩子段誊。 這一過程闰蚕，稱作節(jié)點的分裂(split)。

  
  
  image.png

template <typename T> //兲鍵碼揑入后若節(jié)點上溢连舍，則做節(jié)點分裂處理 void BTree<T>::solveOverflow(BTNodePosi(T) v) {
if (_order >= v->child.size()) return; //逑弻基:弼前節(jié)點幵未上溢
Rank s = _order / 2; //軸點(此時應有_order = key.size() = child.size() - 1) BTNodePosi(T) u = new BTNode<T>(); //注意:新節(jié)點已有一個空孩子
for (Rank j = 0; j < _order - s - 1; j++) { //v右側癿_order-s-1個孩子及兲鍵碼分裂為右側節(jié)點u
u->child.insert(j, v->child.remove(s + 1)); //逐個秱勱效率低 u->key.insert(j, v->key.remove(s + 1)); //此策略可改迕
 9}
10 u->child[_order - s - 1] = v->child.remove(s + 1); //秱勱v最靠右癿孩子

• 刪除
  為從B-樹中刪除關鍵碼e陪腌，也首先需要調用search(e)查找e所屬的節(jié)點。倘若查找失敗烟瞧， 則說明關鍵碼e尚不存在，刪除操作即告完成

 template <typename T> bool BTree<T>::remove(const T& e) { //從BTree樹中初除關鍵碼e 
BTNodePosi(T) v = search(e); if (!v) return false; //確訃目標兲鍵碼存在
Rank r = v->key.search(e); //確定目標兲鍵碼在節(jié)點v中的秩(由上染簇，肯定合法)
if (v->child[0]) { //若v非葉子参滴，則e的后繼必然為葉子節(jié)點
BTNodePosi(T) u = v->child[r+1]; //在右子樹中一直向左，即可 
while (u->child[0]) u = u->child[0]; //找出e的后繼 
v->key[r] = u->key[0]; v = u; r = 0; //并與之交換位置
} //至此锻弓，v必然位于最底局砾赔，且其中第r個兲鍵碼就是待初除者
v->key.remove(r); v->child.remove(r + 1); _size--; //初除e，以及其下兩個外部節(jié)點solveUnderflow(v); //如有必要青灼，需做旋轉戒合幵
return true;

• 下溢與合并
  由上暴心，在m階B-樹中，剛發(fā)生下溢的節(jié)點V必恰好包含m/2 - 2個關鍵碼和m/2 - 1個分 支杂拨。以下將根據其左专普、右兄弟所含關鍵碼的數目，分三種情況做相應的處置弹沽。

  
  
  image.png
  
  
  image.png
  
  
  image.png

在經如此合并而得新節(jié)點中檀夹，關鍵碼總數應為:
(m/2 -1)+1+(m/2 -2) = 2*（m/2） -2<= m-1 故原節(jié)點V的下溢缺陷得以修復，而且同時也不致于反過來引發(fā)上溢策橘。

接下來炸渡，還須檢查父節(jié)點P關鍵碼y的刪除可能致使該節(jié)點出現下溢。好在丽已，即便如此蚌堵， 也盡可套用上述三種方法繼續(xù)修復節(jié)點P。當然，修復之后仍可能導致祖父節(jié)點以及更高層節(jié)點 的下溢這種現象稱作下溢的傳遞吼畏。特別地督赤，當下溢傳遞至根節(jié)點且其中不再含有任何關鍵碼 時，即可將其刪除并代之以其唯一的孩子節(jié)點宫仗，全樹高度也隨之下降一層够挂。

與上溢傳遞類似地，每經過一次下溢修復藕夫，新下溢節(jié)點的高度都必然上升一層

image.png

如前所述孽糖，若下溢現象持續(xù)傳播至樹根，且樹根當時僅含一個關鍵碼毅贮。于是办悟，在其僅有的兩 個孩子被合并、僅有的一個關鍵碼被借出之后滩褥，原樹根將退化為單分支節(jié)點病蛉。對這一特殊情況， 需刪除該樹根瑰煎，并以剛合并而成的節(jié)點作為新的樹根??整樹高度也隨之降低一層铺然。

image.png

4.5紅黑樹

伸展樹實現簡便、無需修改節(jié)點 結構酒甸、分攤復雜度低魄健，但可惜最壞情況下的單次操作需要O(n)時間，故難以適用于核電站插勤、醫(yī) 院等對可靠性和穩(wěn)定性要求極高的場合沽瘦。反之，7.4節(jié)的AVL樹盡管可以保證最壞情況下的單次 操作速度农尖，但需在節(jié)點中嵌入平衡因子等標識;更重要的是析恋，刪除操作之后的重平衡可能需做多 達O(logn)次旋轉，從而頻繁地導致全樹整體拓撲結構的大幅度變化盛卡。

紅黑樹即是針對后一不足的改進助隧。通過為節(jié)點指定顏色，并巧妙地動態(tài)調整滑沧，紅黑樹可保證: 在每次插入或刪除操作之后的重平衡過程中喇颁，全樹拓撲結構的更新僅涉及常數個節(jié)點。盡管最壞 情況下需對多達O(logn)個節(jié)點重染色嚎货，但就分攤意義而言僅為O(1)個

當然橘霎，為此首先需在AVL樹“適度平衡”標準的基礎上，進一步放寬條件殖属。實際上姐叁，紅黑樹 所采用的“適度平衡”標準，可大致表述為:任一節(jié)點左、右子樹的高度外潜，相差不得超過兩倍原环。

由紅、黑兩色節(jié)點組成的二叉搜索樹若滿足以下條件处窥，即為紅黑樹5(red-black tree):

image.png

其中嘱吗，條件(1)和(2)意味著紅節(jié)點均為內部節(jié)點，且其父節(jié)點及左滔驾、右孩子必然存在谒麦。另 外，條件(3)意味著紅節(jié)點之父必為黑色哆致，因此樹中任一通路都不含相鄰的紅節(jié)點绕德。

由此可知颅夺，在從根節(jié)點通往任一節(jié)點的沿途命满，黑節(jié)點都不少于紅節(jié)點。除去根節(jié)點本身朝蜘，沿 途所經黑節(jié)點的總數稱作該節(jié)點的黑深度(black depth)--根節(jié)點的黑深度為0胞此，其余依此 類推臣咖。故條件(4)亦可等效地理解和描述為“所有外部節(jié)點的黑深度統(tǒng)一”。
由條件(4)可進一步推知漱牵，在從任一節(jié)點通往其任一后代外部節(jié)點的沿途夺蛇，黑節(jié)點的總數亦 必相等。除去(黑色)外部節(jié)點布疙，沿途所經黑節(jié)點的總數稱作該節(jié)點的黑高度(black height)。 如此愿卸，所有外部節(jié)點的黑高度均為0灵临，其余依此類推。

• (2,4)-樹
  紅黑樹與四階B-經適當轉換之后趴荸，二者相互等價
  此時儒溉，若將原紅黑樹的節(jié)點視作關鍵碼，沿水平方向相 鄰的每一組(父子至多三個)節(jié)點即恰好構成4階B-樹的一個節(jié)點发钝。

image.png

關鍵碼也被賦予了對應的顏色顿涣。對照紅黑 樹的條件，(2,4)-樹中的每個節(jié)點應包含且僅包含一個黑關鍵碼酝豪，同時紅關鍵碼不得超過兩個涛碑。 而且，若某個節(jié)點果真包含兩個紅關鍵碼孵淘，則黑關鍵碼的位置必然居中蒲障。

image.png

包含n個內部節(jié)點的紅黑樹T的高度h也不致超 過O(logn)。更嚴格地有:
log2(n+1) <=h <=2?log2(n+1)

#include "../BST/BST.h" //基亍BST實現RedBlack
template <typename T> class RedBlack : public BST<T> { //RedBlack樹模板類 protected:
void solveDoubleRed(BinNodePosi(T) x); //雙紅修正
void solveDoubleBlack(BinNodePosi(T) x); //雙黑修正 int updateHeight(BinNodePosi(T) x); //更新節(jié)點x癿高度
public:
BinNodePosi(T) insert(const T& e); //揑入(重寫) bool remove(const T& e); //初除(重寫)
}

可見，這里直接沿用了二叉搜索樹標準的查找算法search()揉阎，并根據紅黑樹的重平衡規(guī)則 與算法庄撮，重寫了insert()和remove()接口;新加的兩個內部功能接口solveDoubleRed()和 solveDoubleBlack()，分別用于在節(jié)點插入或刪除之后恢復全樹平衡毙籽。其具體實現稍后介紹洞斯。
預留的兩個成員 變量height和color
可借助輔助宏來檢查節(jié)點的顏 色以及判定是否需要更新(黑)高度記錄，如此可大大簡化相關算法的描述坑赡。

#define IsBlack(p) (!(p) || (RB_BLACK == (p)->color)) //外部節(jié)點也規(guī)作黑節(jié)點 #define IsRed(p) (!IsBlack(p)) //非黑即紅
#define BlackHeightUpdated(x) ( \
(stature((x).lChild) == stature((x).rChild)) && \
((x).height == (IsRed(&x) ? stature((x).lChild) : stature((x).lChild) + 1)) \ ) //RedBlack高度更新條件

1 template <typename T> int RedBlack<T>::updateHeight(BinNodePosi(T) x) { //更新紅黑樹節(jié)點高度 
2 x->height = max(stature(x->lChild), stature(x->rChild)); //孩子一般黑高度相等烙如，除非出現雙黑 
3 return IsBlack(x) ? x->height++ : x->height; //若弼前節(jié)點為黑，則計入黑深度
4 } //因統(tǒng)一定stature(NULL) = -1垮衷，故height比黑高度少一厅翔，好在丌致影響刡各種算法中癿比較刞斷

此處的height已不再是指常規(guī)的樹高，而是紅黑樹的黑高度搀突。故如代碼8.15所示刀闷，節(jié)點黑 高度需要更新的情況共分三種:或者左、右孩子的黑高度不等;或者作為紅節(jié)點仰迁，黑高度與其孩 子不相等;或者作為黑節(jié)點甸昏，黑高度不等于孩子的黑高度加一。

因新節(jié)點的引入徐许，而導致父子節(jié)點同為紅色的此類情況施蜜，稱作“雙紅”(double red)。 為修正雙紅缺陷雌隅，可調用solveDoubleRed(x)接口翻默。每引入一個關鍵碼，該接口都可能迭代地 調用多次恰起。在此過程中修械，當前節(jié)點x的兄弟及兩個孩子(初始時都是外部節(jié)點)，始終均為黑色检盼。

• 雙紅修正RR1
  首先肯污，考查u為黑色的情況。此時吨枉，x的兄弟蹦渣、兩個孩子的黑高度，均與u相等貌亭。圖8.25(a) 和(b)即為此類情況的兩種可能(另兩種對稱情況柬唯，請讀者獨立補充)。

  
  
  image.png
  
  

  此時紅黑樹條件(3)的違反圃庭，從B-樹角度等效地看权逗，即同一節(jié)點不應包含緊鄰的紅色關鍵碼美尸。 故如圖8.25(c')所示，只需令黑色關鍵碼與緊鄰的紅色關鍵碼互換顏色斟薇。從圖(c)紅黑樹的角度 看师坎，這等效于按中序遍歷次序，對節(jié)點x堪滨、p和g及其四棵子樹胯陋，做一次局部“3 + 4”重構。

不難驗證袱箱，如此調整之后遏乔，局部子樹的黑高度將復原，這意味著全樹的平衡也必然得以恢復发笔。 同時盟萨，新子樹的根節(jié)點b為黑色，也不致引發(fā)新的雙紅現象了讨。至此捻激，整個插入操作遂告完成。

• 雙紅修正(RR-2)
  再考查節(jié)點u為紅色的情況前计。此時胞谭，u的左、右孩子非空且均為黑色男杈，其黑高度必與x的兄弟
  以及兩個孩子相等丈屹。圖8.26(a)和(b)給出了兩種可能的此類情況(另兩種對稱情況，請讀者獨 立補充)伶棒。此時紅黑樹條件(3)的違反旺垒，從B-樹角度等效地看，即該節(jié)點因超過4度而發(fā)生上溢肤无。

  
  
  image.png

不難驗證先蒋，如此調整之后局部子樹的黑高度復原。然而舅锄，子樹根節(jié)點g轉為紅色之后鞭达，有可 能在更高層再次引發(fā)雙紅現象司忱。從圖8.26(c')B-樹的角度來看皇忿，對應于在關鍵碼g被移出并歸入 上層節(jié)點之后，進而導致上層節(jié)點的上溢??即上溢的向上傳播坦仍。
若果真如此鳍烁，可以等效地將g視作新插入的節(jié)點，同樣地分以上兩類情況如法處置繁扎。請注意幔荒， 每經過一次這樣的迭代糊闽，節(jié)點g都將在B-樹中(作為關鍵碼)上升一層，而在紅黑樹中存在雙紅 缺陷的位置也將相應地上升兩層爹梁，故累計至多迭代O(logn)次右犹。

image.png

/****************************************************************************************** *RedBlack雙紅調整算法:解決節(jié)點x不其父均為紅色癿問題。分為兩大類情冴:
* RR-1:2次顏色翻轉姚垃，2次黑高度更新念链，1~2次旋轉，丌再逑弻
* RR-2:3次顏色翻轉积糯，3次黑高度更新掂墓，0次旋轉，需要逑弻 ******************************************************************************************/
template <typename T> void RedBlack<T>::solveDoubleRed(BinNodePosi(T) x) { //x弼前必為紅 if (IsRoot(*x)) //若已(逑弻)轉至樹根看成，則將其轉黑君编，整樹黑高度也隨乀逑增
{ _root->color = RB_BLACK; _root->height++; return; } //否則，x的父親p必存在 BinNodePosi(T) p = x->parent; if (IsBlack(p)) return; //若p為黑川慌，則可終止調整吃嘿。否則 BinNodePosi(T) g = p->parent; //既然p為紅，則x癿祖父必存在窘游，且必為黑色 BinNodePosi(T) u = uncle(x); //以下唠椭，規(guī)x叔父u癿顏色分刪處理
if (IsBlack(u)) { //u為黑色(含NULL)時
if (IsLChild(*x) == IsLChild(*p)) //若x不p同側(即zIg-zIg戒zAg-zAg)，則
///// /////
p->color = RB_BLACK; //p由紅轉黑忍饰，x保持紅 else //若x不p異側(即zIg-zAg戒zAg-zIg)贪嫂，則
x->color = RB_BLACK; //x由紅轉黑，p保持紅
g->color = RB_RED; //g必定由黑轉紅 以上雖保證總共兩次染色艾蓝，但因增加了刞斷而得丌償失 在旋轉后將根置黑力崇、孩子置紅，雖需三次染色但效率更高
BinNodePosi(T) gg = g->parent; //曾祖父(great-grand parent)
BinNodePosi(T) r = FromParentTo(*g) = rotateAt(x); //調整后癿子樹根節(jié)點 r->parent = gg; //不原曾祖父聯接
 } }
} else { //若u為紅色
p->color = RB_BLACK; p->height++; //p由紅轉黑
u->color = RB_BLACK; u->height++; //u由紅轉黑
if (!IsRoot(*g)) g->color = RB_RED; //g若非根赢织，則轉紅
solveDoubleRed(g); //繼續(xù)調整g(類似亍尾逑弻亮靴，可優(yōu)化為迭代形式)

• 節(jié)點刪除算法
  節(jié)點刪除與雙黑現象

template <typename T> bool RedBlack<T>::remove(const T& e) { //從紅黑樹中初除關鍵碼e 
BinNodePosi(T) & x = search(e); if (!x) return false; //確定目標節(jié)點存在(留意對_hot的位置) 
BinNodePosi(T) r = removeAt(x, _hot); if (0 >= --_size) return true; //實施刪除
// assert: _hot某一孩子剛被初除，且被r所指節(jié)點(可能是NULL)接替于置。以下檢查是否失衡茧吊，幵做必要調整 
if (!_hot) //若剛被初除癿是根節(jié)點，則將其置黑八毯，并更新黑高度
{ _root->color = RB_BLACK; updateHeight(_root); return true; } // assert: 以下搓侄，原x(現r)必非根，_hot必非空
if (BlackHeightUpdated(*(_hot))) //若所有祖先癿黑深度依然平衡话速，則無需調整 
  return true;
if (IsRed(r)) //否則讶踪，若r為紅，則叧需令其轉黑
{ r->color = RB_BLACK; r->height++; return true; }
// assert: 以下泊交，原x(現r)均為黑色
solveDoubleBlack(r); return true; //經雙黑調整后迒回
} //若目標節(jié)點存在且被初除乳讥，返回true;否則迒回false

不難驗證柱查，此時紅黑樹的前兩個條件繼續(xù)滿足，但后兩個條件卻未必依然滿足云石。

如圖8.28所示唉工，除了其接替者r，x 還應有另一個孩子w汹忠。既然x是實際被刪除 者酵紫，故w必為(黑色的)外部節(jié)點NULL。
如圖(a)和(a')所示错维，若x為紅色奖地， 則在刪除x并代之以r后，條件(3~4)依然 滿足;反之赋焕，若x為黑色参歹，則要看其替代 者r的顏色。
如圖(b)和(b')所示隆判，若r為紅色犬庇， 則只需將其翻轉為黑色，即可使條件 (3~4)重新滿足侨嘀。
然而如圖(c)和(c')所示臭挽，若x和r均 為黑色，則為使條件(3~4)重新成立咬腕，還 需要做略微復雜一些的處理欢峰。

image.png

因某一無紅色孩子的黑節(jié)點被刪除，而導致的此類復雜情況涨共，稱作“雙黑”(double black) 現象纽帖。此時，需從r出發(fā)調用solveDoubleBlack(r)算法予以修正举反。

自然懊直，原黑節(jié)點x的兄弟必然非空，將其記作s;x的父親記作p火鼻，其顏色不確定(故在圖中 以八角形示意)室囊。以下視s和p顏色的不同組合，按四種情況分別處置魁索。

• 雙黑修正(BB-1)
  既然節(jié)點x的另一孩子w=NULL融撞，故從B-樹角度(圖8.29(a'))看節(jié)點x被刪除之后的情況，
  可以等效地理解為:關鍵碼x原所屬的節(jié)點發(fā)生下溢;此時蛾默，t和s必然屬于B-樹的同一節(jié)點懦铺，且 該節(jié)點就是下溢節(jié)點的兄弟捉貌。故可參照B-樹的調整方法支鸡，下溢節(jié)點從父節(jié)點借出一個關鍵碼(p)冬念， 然后父節(jié)點從向下溢節(jié)點的兄弟節(jié)點借出一個關鍵碼(s)，調整后的效果如圖(b')牧挣。

從紅黑樹的角度(圖(b))來看急前， 上述調整過程等效于，對節(jié)點t瀑构、s和p 實施“3 + 4”重構裆针。

此外，根據紅黑樹與B-樹的對應 關系不難理解寺晌，若這三個節(jié)點按中序遍 歷次序重命名為a世吨、b和c，則還需將a 和c染成黑色呻征，b則繼承p此前的顏色耘婚。 就圖8.29的具體實例而言，也就是將t 和p染成黑色陆赋，s繼承p此前的顏色沐祷。注 意，整個過程中節(jié)點r保持黑色不變攒岛。
由圖8.29(b)(及其對稱情況)不 難驗證赖临，經以上處理之后，紅黑樹的所 有條件灾锯，都在這一局部以及全局得到恢 復兢榨，故刪除操作遂告完成。

image.png

• 雙黑修正(BB-2-R)
  節(jié)點s及其兩個孩子均為黑色時顺饮，視節(jié)點p顏色的不同色乾，又可進一步分為兩種情況。

先考慮p為紅色的情況领突。如圖8.30(a)所示暖璧，即為一種典型的此類情況

image.png

與BB-1類似，在對應的B-樹中君旦，關鍵碼x的刪除導 致其所屬的節(jié)點下溢澎办。但因此時關鍵碼s所在節(jié)點只有兩 個分支，故下溢節(jié)點無法從父節(jié)點借出關鍵碼(p)金砍。
按照8.2.8節(jié)的B-樹平衡算法局蚀，此時應如圖(b')所 示，將關鍵碼p取出并下降一層恕稠，然后以之為“粘合劑”琅绅， 將原左、右孩子合并為一個節(jié)點鹅巍。從紅黑樹角度看千扶，這 一過程可如圖(b)所示等效地理解為:s和p顏色互換料祠。
由圖8.30(b)(及其對稱情況)可知，經過以上處 理澎羞，紅黑樹的所有條件都在此局部得以恢復髓绽。另外，由 于關鍵碼p原為紅色妆绞，故如圖8.30(a')所示顺呕，在關鍵碼p 所屬節(jié)點中，其左或右必然還有一個黑色關鍵碼(當然括饶， 不可能左株茶、右兼有)--這意味著，在關鍵碼p從其中取 出之后图焰，不致引發(fā)新的下溢忌卤。至此，紅黑樹條件亦必在 全局得以恢復楞泼，刪除操作即告完成驰徊。

• 雙黑修正(BB-2-B)
  接下來，再考慮節(jié)點s堕阔、s的兩個孩子以及節(jié)點p均為黑色的情況棍厂。 如圖8.31(a)所示，即為一種典型的此類情況(與之對稱的情況超陆，請讀者獨立補充)牺弹。此時
  與BB-2-R類似，在對應的B-樹中时呀，因關鍵碼x的刪除张漂，導致其所屬節(jié)點發(fā)生下溢。

因此可如圖(b')所示谨娜，將下溢 節(jié)點與其兄弟合并航攒。從紅黑樹的角 度來看，這一過程可如圖(b)所示等 效地理解為:節(jié)點s由黑轉紅趴梢。
由圖8.31(b)(及其對稱情況) 可知漠畜，經以上處理，紅黑樹所有條 件都在此局部得到恢復坞靶。
然而憔狞，因s和x在此之前均為黑 色，故如圖8.31(a')所示彰阴，p原所 屬的B-樹節(jié)點必然僅含p這一個關 鍵碼瘾敢。于是在p被借出之后，該節(jié)點 必將繼而發(fā)生下溢，故有待于后續(xù) 進一步修正簇抵。

image.png

從紅黑樹的角度來看庆杜，此時的狀態(tài)可等效地理解為:節(jié)點p的父節(jié)點剛被刪除。當然正压，可以 按照本節(jié)所介紹的算法，視具體的情況繼續(xù)調整责球。
實際上稍后總結時將會看出焦履，這也是雙黑修正過程中，需要再次迭代的唯一可能雏逾。幸運的是嘉裤， 盡管此類情況可能持續(xù)發(fā)生，下溢的位置也必然不斷上升栖博，故至多迭代O(logn)次后必然終止屑宠。

• 雙黑修正(BB-3)
  最后，考慮節(jié)點s為紅色的情
  況仇让。如圖8.32(a)所示典奉，即為一種典 型的此類情況(與之對稱的情況， 請讀者獨立補充)丧叽。此時卫玖，作為紅 節(jié)點s的父親，節(jié)點p必為黑色;同 時踊淳，s的兩個孩子也應均為黑色假瞬。

于是從B-樹的角度來看，只需 如圖(b')所示迂尝，令關鍵碼s與p互換 顏色脱茉，即可得到一棵與之完全等價 的B-樹。而從紅黑樹的角度來看垄开， 這一轉換對應于以節(jié)點p為軸做一 次旋轉琴许，并交換節(jié)點s與p的顏色。

image.png

讀者可能會發(fā)現溉躲，經過如此處理之后虚吟，雙黑缺陷依然存在，而且缺陷位置的高度也并未上升签财。 既然如此串慰，這一步調整的意義又何在呢?

實際上，經過這一轉換之后唱蒸，情況已經發(fā)生了微妙而本質的變化邦鲫。仔細觀察圖(b)不難發(fā)現， 在轉換之后的紅黑樹中，被刪除節(jié)點x(及其替代者節(jié)點r)有了一個新的兄弟s'--與此前的 兄弟s不同庆捺，s'必然是黑的!這就意味著古今，接下來可以套用此前所介紹其它情況的處置方法，繼 續(xù)并最終完成雙黑修正滔以。

還有一處本質的變化捉腥，同樣需要注意:現在的節(jié)點p，也已經黑色轉為紅色你画。因此接下來即 便需要繼續(xù)調整抵碟，必然既不可能轉換回此前的情況BB-3，也不可能轉入可能需要反復迭代的情 況BB-2-B坏匪。實際上反過來拟逮，此后只可能轉入更早討論過的兩類情況??BB-1或BB-2-R。這就意 味著适滓，接下來至多再做一步迭代調整敦迄，整個雙黑修正的任務即可大功告成。

image.png

image.png

一旦在某步迭代中做過節(jié)點的旋轉調整凭迹，整個修復過程便會隨即 完成罚屋。因此與雙紅修正一樣，雙黑修正的整個過程嗅绸，也僅涉及常數次的拓撲結構調整操作沿后。
這一有趣的特性同時也意味著，在每此插入操作之后朽砰，拓撲聯接關系有所變化的節(jié)點絕不會 超過常數個??這一點與AVL樹(的刪除操作)完全不同尖滚，也是二者之間最本質的一項差異。

/****************************************************************************************** *RedBlack雙黑調整算法:解決節(jié)點x不被其替代癿節(jié)點均為黑色癿問題
分為三大類共四種情冴:
BB-1 :2次顏色翻轉瞧柔，2次黑高度更新漆弄，1~2次旋轉，不再迭代 
BB-2R:2次顏色翻轉造锅，2次黑高度更新撼唾，0次旋轉，不再更新 
BB-2B:1次顏色翻轉哥蔚，1次黑高度更新倒谷，0次旋轉，需要迭代
BB-3 :2次顏色翻轉糙箍，2次黑高度更新渤愁，1次旋轉，轉為BB-1或者BB-2-R
template <typename T> void RedBlack<T>::solveDoubleBlack(BinNodePosi(T) r) { BinNodePosi(T) p = r ? r->parent : _hot; if (!p) return; //r父親 
BinNodePosi(T) s = (r == p->lChild) ? p->rChild : p->lChild; //r的兄弟
if(IsBlack(s)) { //兄弟s為黑
BinNodePosi(T) t = NULL; //s的紅孩子(若左深夯、右孩子都是紅抖格，左者優(yōu)先;皆黑時為NULL) 
if (HasLChild(*s) && IsRed(s->lChild)) t = s->lChild;
else if (HasRChild(*s) && IsRed(s->rChild)) t = s->rChild;
if(t) { //黑s有紅孩子:BB-1
RBColor oldColor = p->color; //備份原子樹根節(jié)點p顏色诺苹，并對t及其父親、祖父 
BinNodePosi(T) b = FromParentTo(*p) = rotateAt(t); //重平衡雹拄，并將新子樹的左收奔、右孩子染黑 
if (HasLChild(*b)) b->lChild->color = RB_BLACK; updateHeight(b->lChild); //左孩子
if (HasRChild(*b)) b->rChild->color = RB_BLACK; updateHeight(b->rChild); //右孩子 
b->color = oldColor; updateHeight(b); //新子樹根節(jié)點繼承原根節(jié)點的顏色
} else { //黑s無紅孩子
s->color = RB_RED; s->height--; //s轉紅 
if (IsRed(p)) { //BB-2R
p->color = RB_BLACK; //p轉黑，但黑高度不變 } 
else { //BB-2B
p->height--; //p保持黑滓玖，但黑高度下降
solveDoubleBlack(p); }
 }
} else { //兄弟s為紅:BB-3
s->color = RB_BLACK; p->color = RB_RED; //s轉黑坪哄，p轉紅
BinNodePosi(T) t = IsLChild(*s) ? s->lChild : s->rChild; //取t不其父s同側 
_hot = p; FromParentTo(*p) = rotateAt(t); //對t及其父親、祖父做平衡調整 
solveDoubleBlack(r); //繼續(xù)修正r處雙黑——此時的p已轉紅势篡，故后續(xù)叧能是BB-1或者BB-2R
 } }