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; //视v、p和g相对位置分四种情况 0007 if ( IsLChild ( *p ) ) /* zig */ 0008 if ( IsLChild ( *v ) ) { /* zig-zig */ 0009 p->parent = g->parent; //向上联接 0010 return connect34 ( v, p, g, v->lc, v->rc, p->rc, g->rc ); 0011 } else { /* zig-zag */ 0012 v->parent = g->parent; //向上联接 0013 return connect34 ( p, v, g, p->lc, v->lc, v->rc, g->rc ); 0014 } 0015 else /* zag */ 0016 if ( IsRChild ( *v ) ) { /* zag-zag */ 0017 p->parent = g->parent; //向上联接 0018 return connect34 ( g, p, v, g->lc, p->lc, v->lc, v->rc ); 0019 } else { /* zag-zig */ 0020 v->parent = g->parent; //向上联接 0021 return connect34 ( g, v, p, g->lc, v->lc, v->rc, p->rc ); 0022 } 0023 }