qq

 1 template <class T>
 2 void RBtree<T>::RotateLeft(RBnode* x)      //以x为支点左旋，原来y是x的右分支，转换后x成为y的左分支
 3 {
 4     RBnode* y = x -> right;      //y为x的右分支
 5     x -> right = y -> left;      //将y的左分支的地址z赋给x的右分支
 6     if (y -> left != NIL)
 7         y -> left -> fa = x;     //将y的左分支z与x连接起来
 8     y -> fa = x -> fa;      //将y与x的前驱结点连接起来
 9     if (x -> fa == NIL)      //如果x本身是根节点
10         ROOT = y;      //y将转变为根节点
11     else if (x == x -> fa -> left)      //如果x本身是左分支
12         x -> fa -> left = y;      //y也将转变为x前驱结点的左分支
13     else      //如果x本身是右分支
14         x -> fa -> right = y;      //y也将转变为x前驱结点的右分支
15     y -> left = x;      //x变成y的左分支
16     x -> fa = y;      //改变x前驱指针
17     return ;
18 }

 1 template <class T>
 2 void RBtree<T>::RotateRight(RBnode* x)      //以x为支点右旋，原来y是x的左分支，转换后x是y的右分支
 3 {
 4     RBnode* y = x -> left;      //y为x的左分支
 5     x -> left = y -> right;      //将y的左分支的地址z赋给x的右分支
 6     if (y -> right != NIL)
 7         y -> right -> fa = x;     //将y的右分支z与x连接起来
 8     y -> fa = x -> fa;      //y与x的前驱结点连接起来
 9     if (x -> fa == NIL)      //如果x本身是根节点
10         ROOT = y;      //y将转变为根节点
11     else if (x == x -> fa -> right)      //如果x本身是右分支
12         x -> fa -> right = y;      //y也将转变为x前驱结点的右分支
13     else      //如果x本身是左分支
14         x -> fa -> left = y;      //y也将转变为x前驱结点的左分支
15     y -> right = x;      //x成为y的右分支
16     x -> fa = y;      //y是x的前驱结点
17     return ;
18 }