0001 /******************************************************************************************
0002  * BST节点旋转变换统一算法（3节点 + 4子树），返回调整之后局部子树根节点的位置
0003  * 注意：尽管子树根会正确指向上层节点（如果存在），但反向的联接须由上层函数完成
0004  ******************************************************************************************/
0005 template <typename T> BinNodePosi<T> BST<T>::rotateAt( BinNodePosi<T> v ) { //v为非空孙辈节点
0006    BinNodePosi<T> p = v->parent; int TurnV = (v == p->rc);
0007    BinNodePosi<T> g = p->parent; int TurnP = (p == g->rc);
0008    BinNodePosi<T> r = ( TurnP == TurnV ) ? p : v; //子树新的根节点
0009    ( FromParentTo(g) = r )->parent = g->parent;; //须保持与母树的联接
0010    switch ( ( TurnP << 1 ) | TurnV ) { //视p、v的拐向，无非四种情况
0011       case 0b00 : //zig-zig
0012          return connect34( v, p, g,  v->lc, v->rc, p->rc, g->rc );
0013       case 0b01 : //zig-zag
0014          return connect34( p, v, g,  p->lc, v->lc, v->rc, g->rc );
0015       case 0b10 : //zag-zig
0016          return connect34( g, v, p,  g->lc, v->lc, v->rc, p->rc );
0017       default : //0b11 ~ zag-zag
0018          return connect34( g, p, v,  g->lc, p->lc, v->lc, v->rc );
0019    }
0020 }