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; updateHeight ( a ); 0012 c->lc = T2; if ( T2 ) T2->parent = c; 0013 c->rc = T3; if ( T3 ) T3->parent = c; updateHeight ( c ); 0014 b->lc = a; a->parent = b; 0015 b->rc = c; c->parent = b; updateHeight ( b ); 0016 return b; //该子树新的根节点 0017 }