伸展树(SplayTree)

Left_Rotate(T,x)//x.right ≠ NIL
    y = x.right                // set y
    x.right = y.left           //turn y‘s left subtree to x‘s right subtree
    if y.left ≠ NIL
        y.left.p = x
    y.p = x.p                  //link x‘s parent to y
    if x.p == NIL
        T.root = y
    else if x == x.p.left    
        x.p.left = y
    else
        x.p.right = y
    y.left = x                 //put x on y‘s left
    x.p = y

Right_Rotate(T,y)//y.left ≠ NIL
    x = y.left                 // set x
    y.left = x.right           //turn x‘s right subtree to y‘s left subtree
    if x.right ≠ NIL
        x.right.p = y
    x.p = y.p                  //link y‘s parent to x
    if y.p == NIL
        T.root = x
    else if y == y.p.left    
        y.p.left = x
    else
        y.p.right = x
    x.right = y                 //put y on x‘s right
    y.p = x

void splay( node *x ) {
    while( x->parent ) {
      if( !x->parent->parent ) {//x的父结点为树根
        if( x->parent->left == x ) right_rotate( x->parent );
        else left_rotate( x->parent );
      } 
      else if( x->parent->left == x && x->parent->parent->left == x->parent ) {//左"一字型"
        right_rotate( x->parent->parent );
        right_rotate( x->parent );
      } 
      else if( x->parent->right == x && x->parent->parent->right == x->parent ) {//右"一字型"
        left_rotate( x->parent->parent );
        left_rotate( x->parent );
      } 
      else if( x->parent->left == x && x->parent->parent->right == x->parent ) {//左右"之自型"(从下至上看)
        right_rotate( x->parent );
        left_rotate( x->parent );
      } 
      else {//右左"之自型"(从下至上看)
        left_rotate( x->parent );
        right_rotate( x->parent );
      }
    }
  }