模拟插入关键码e //设T中本不含e
按BST的常规算法插入 // x = insert(e)必为末端节点
设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
实现：
template <typename T> BinNodePosi(T) RedBlack<T>::insert(const T & e){
//确认目标节点不存在（留意对_hot的设置）
BinNodePosi(T) & x =search(e); if(x) return x;
//创建红节点x，以_hot为父，黑高度-1
x = new BinNode<T>(e,_hot,NULL,NULL,-1);
_size++;
//如有必要，做双红修正
solveDoubleRed(x);
//返回插入节点
return x ? x : _hot->parent;
} //无论原树中是否有e，返回时总有x->data == e
RR-1:u->color == B
此时：x、p、g的四个孩子（可能是外部节点）全为黑，且黑高度相同
1.参照AVL树算法，做局部3+4重构
将节点x、p、g及其四棵子树，按中序组合为：T0<a<T1<b<T2<c<T3
2.染色：b转黑，a或c转红
RR-2:u->color == R
在B-树中，等效于超级节点发生上溢
p与u转黑，g转红
在B-树中，等效于节点分裂，关键码g上升一层
双红修正：复杂度
重构、染色均属常数时间的局部操作，统计其总次数
红黑树的每一次插入操作都可在O(logn)时间内完成
其中至多做：
1.O(logn)次节点染色
2.一次"3+4"重构
