0001 template <typename T> BinNodePosi(T) BinNode<T>::zag() { //ʱת 0002 BinNodePosi(T) rChild = rc; 0003 rChild->parent = this->parent; 0004 if ( rChild->parent ) 0005 ( ( this == rChild->parent->lc ) ? rChild->parent->lc : rChild->parent->rc ) = rChild; 0006 rc = rChild->lc; if ( rc ) rc->parent = this; 0007 rChild->lc = this; this->parent = rChild; 0008 // update heights 0009 height = 1 + max ( stature ( lc ), stature ( rc ) ); 0010 rChild->height = 1 + max ( stature ( rChild->lc ), stature ( rChild->rc ) ); 0011 for ( BinNodePosi(T) x = rChild->parent; x; x = x->parent ) 0012 if ( HeightUpdated( *x ) ) 0013 break; 0014 else 0015 x->height = 1 + max ( stature ( x->lc ), stature ( x->rc ) ); 0016 return rChild; 0017 }