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; BinNodePosi<T> g = p->parent;
0007    switch ( ( IsRChild(*p) << 1 ) | IsRChild(*v) ) { //视p、v的拐向，分四种情况
0008       case 0b00 : //zig-zig
0009          p->parent = g->parent; return connect34( v, p, g, v->lc, v->rc, p->rc, g->rc );
0010       case 0b01 : //zig-zag
0011          v->parent = g->parent; return connect34( p, v, g, p->lc, v->lc, v->rc, g->rc );
0012       case 0b10 : //zag-zig
0013          v->parent = g->parent; return connect34( g, v, p, g->lc, v->lc, v->rc, p->rc );
0014       default : //0b11 ~ zag-zag
0015          p->parent = g->parent; return connect34( g, p, v, g->lc, p->lc, v->lc, v->rc );
0016    }
0017 }