由紅、黑兩類節(jié)點(diǎn)組成的BST //亦可給邊染色
（統(tǒng)一增設(shè)外部節(jié)點(diǎn)NULL乎折，使之成為真二叉樹(shù)）
1）樹(shù)根：必為黑色
2）外部節(jié)點(diǎn)：均為黑色
3）其余節(jié)點(diǎn)：若為紅鸠真，則只能有黑孩子 //紅之子谦去、之父必黑
4）外部節(jié)點(diǎn)到根：途中黑節(jié)點(diǎn)數(shù)目相等 //黑深度
(2,4)樹(shù)==紅黑樹(shù)
提升各紅節(jié)點(diǎn)稻扬，使之與其（黑）父親等高——于是每棵紅黑樹(shù)都對(duì)應(yīng)于一顆(2,4)-樹(shù)
將黑節(jié)點(diǎn)與其紅孩子視作（關(guān)鍵碼并合并為）超級(jí)節(jié)點(diǎn)
無(wú)非四種組合，分別對(duì)應(yīng)于4階B-樹(shù)的一類內(nèi)部節(jié)點(diǎn)
接口定義：
template <typename T> class RedBlack:public BST<T> {
public:? ? //BST::search()等其余接口可直接沿用
? ? ? ? ? ? ? BinNodePosi(T) insert (const T & e); //重寫(xiě)插入
? ? ? ? ? ? ? bool remove(const T & e); //重寫(xiě)刪除
protected:? ? void solveDoubleRed(BinNodePosi(T) x); //雙紅修正
? ? ? ? ? ? ? void solve Double Black(BinNodePosi(T) x); //雙黑修正
? ? ? ? ? ? ? int updateHeight(BinNodePosi(T) x); //更新節(jié)點(diǎn)x的高度
};
template <typename T> int RedBlack<T>::updateHeight(BinNodePosi(T) x) {
x->height = max(stature(x->lc),stature(x->rc));
if(IsBlack(x)) x->height++; return x->height; //只計(jì)黑節(jié)點(diǎn)
}
