由紅、黑兩類節(jié)點(diǎn)組成的BST //亦可給邊染色

（統(tǒng)一增設(shè)外部節(jié)點(diǎn)NULL，使之成為真二叉樹）

1）樹根：必為黑色

2）外部節(jié)點(diǎn)：均為黑色

3）其余節(jié)點(diǎn)：若為紅，則只能有黑孩子 //紅之子、之父必黑

4）外部節(jié)點(diǎn)到根：途中黑節(jié)點(diǎn)數(shù)目相等 //黑深度

(2,4)樹==紅黑樹

提升各紅節(jié)點(diǎn)，使之與其（黑）父親等高——于是每棵紅黑樹都對(duì)應(yīng)于一顆(2,4)-樹

將黑節(jié)點(diǎn)與其紅孩子視作（關(guān)鍵碼并合并為）超級(jí)節(jié)點(diǎn)

無(wú)非四種組合，分別對(duì)應(yīng)于4階B-樹的一類內(nèi)部節(jié)點(diǎn)

接口定義：

template <typename T> class RedBlack:public BST<T> {

public:? ? //BST::search()等其余接口可直接沿用

? ? ? ? ? ? ? BinNodePosi(T) insert (const T & e); //重寫插入

? ? ? ? ? ? ? bool remove(const T & e); //重寫刪除

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)

}