模擬插入關(guān)鍵碼e //設(shè)T中本不含e
按BST的常規(guī)算法插入 // x = insert(e)必為末端節(jié)點
設(shè)x的父親p = x->parent存在 //否則，即平凡的首次插入
將x染紅（除非它是根） //x->color = isRoot(x) ? B : R
雙紅缺陷(double-red)? //p->color == x->color == R
考查：x的祖父 g = p->parent //g != null && g->color == B
? ? ? ? ? ?p的兄弟 u = p== g->lc ? g->rc : g->lc
實現(xiàn)：
template <typename T> BinNodePosi(T) RedBlack<T>::insert(const T & e){
//確認(rèn)目標(biāo)節(jié)點不存在（留意對_hot的設(shè)置）
BinNodePosi(T) & x =search(e); if(x) return x;
//創(chuàng)建紅節(jié)點x退渗，以_hot為父移稳，黑高度-1
x = new?BinNode<T>(e,_hot,NULL,NULL,-1);
_size++;
//如有必要，做雙紅修正
solveDoubleRed(x);
//返回插入節(jié)點
return x ? x : _hot->parent;
} //無論原樹中是否有e会油，返回時總有x->data == e
RR-1:u->color == B
此時：x个粱、p、g的四個孩子（可能是外部節(jié)點）全為黑翻翩，且黑高度相同
1.參照AVL樹算法都许，做局部3+4重構(gòu)
將節(jié)點x、p嫂冻、g及其四棵子樹胶征，按中序組合為：T0<a<T1<b<T2<c<T3
2.染色：b轉(zhuǎn)黑，a或c轉(zhuǎn)紅
RR-2:u->color == R
在B-樹中桨仿，等效于超級節(jié)點發(fā)生上溢
p與u轉(zhuǎn)黑睛低，g轉(zhuǎn)紅
在B-樹中，等效于節(jié)點分裂，關(guān)鍵碼g上升一層
雙紅修正：復(fù)雜度
重構(gòu)钱雷、染色均屬常數(shù)時間的局部操作骂铁，統(tǒng)計其總次數(shù)
紅黑樹的每一次插入操作都可在O(logn)時間內(nèi)完成
其中至多做：
1.O(logn)次節(jié)點染色
2.一次"3+4"重構(gòu)
