0001 /******************************************************************************************
0002  * 按照“3 + 4”结构联接3个节点及其四棵子树，返回重组之后的局部子树根节点位置（即b）
0003  * 子树根节点与上层节点之间的双向联接，均须由上层调用者完成
0004  * 可用于AVL和RedBlack的局部平衡调整
0005  ******************************************************************************************/
0006 template <typename T> BinNodePosi<T> BST<T>::connect34 (
0007    BinNodePosi<T> a, BinNodePosi<T> b, BinNodePosi<T> c,
0008    BinNodePosi<T> T0, BinNodePosi<T> T1, BinNodePosi<T> T2, BinNodePosi<T> T3
0009 ) {
0010    a->lc = T0; if ( T0 ) T0->parent = a;
0011    a->rc = T1; if ( T1 ) T1->parent = a; a->updateHeight();
0012    c->lc = T2; if ( T2 ) T2->parent = c;
0013    c->rc = T3; if ( T3 ) T3->parent = c; c->updateHeight ();
0014    b->lc = a; a->parent = b;
0015    b->rc = c; c->parent = b; b->updateHeight();
0016    return b; //该子树新的根节点
0017 }