ACM___________________________

伸展樹(Splay Tree)是AVL樹不錯的替代，它有以下幾個特點：
(1)它是二叉查找樹的改進，所以具有二叉查找樹的有序性。
(2)對伸展樹的操作的平攤復雜度是O(log2n)。
(3)伸展樹的空間要求、編程難度非常低。

提到伸展樹，就不得不提到AVL樹和Read-Black樹，雖然這兩種樹能夠保證各種操作在最壞情況下都為logN，但是兩都實現都比較復雜。而在實際情況中，90%的訪問發生在10%的數據上。因此，我們可以重構樹的結構，使得被經常訪問的節點朝樹根的方向移動。盡管這會引入額外的操作，但是經常被訪問的節點被移動到了靠近根的位置，因此，對于這部分節點，我們可以很快的訪問。這樣，就能使得平攤復雜度為logN。

1、自底向上的伸展樹
伸展操作Splay(x,S)是在保持伸展樹有序性的前提下，通過一系列旋轉操作將伸展樹S中的元素x調整至樹的根部的操作。
在旋轉的過程中，要分三種情況分別處理：
(1)Zig 或 Zag
(2)Zig-Zig 或 Zag-Zag
(3)Zig-Zag 或 Zag-Zig
1.1、Zig或Zag操作
節點x的父節點y是根節點。

1.2、Zig-Zig或Zag-Zag操作
節點x的父節點y不是根節點，且x與y同時是各自父節點的左孩子或者同時是各自父節點的右孩子。

1.3、Zig-Zag或Zag-Zig操作
節點x的父節點y不是根節點，x與y中一個是其父節點的左孩子而另一個是其父節點的右孩子。

2、自頂向下的伸展樹
    在自底向上的伸展樹中，我們需要求一個節點的父節點和祖父節點，因此這種伸展樹難以實現。因此，我們可以構建自頂向下的伸展樹。
    當我們沿著樹向下搜索某個節點X的時候，我們將搜索路徑上的節點及其子樹移走。我們構建兩棵臨時的樹──左樹和右樹。沒有被移走的節點構成的樹稱作中樹。在伸展操作的過程中：
(1)當前節點X是中樹的根。
(2)左樹L保存小于X的節點。
(3)右樹R保存大于X的節點。
開始時候，X是樹T的根，左右樹L和R都是空的。和前面的自下而上相同，自上而下也分三種情況：
2.1、Zig操作

如上圖，在搜索到X的時候，所查找的節點比X小，將Y旋轉到中樹的樹根。旋轉之后，X及其右子樹被移動到右樹上。很顯然，右樹上的節點都大于所要查找的節點。注意X被放置在右樹的最小的位置，也就是X及其子樹比原先的右樹中所有的節點都要小。這是由于越是在路徑前面被移動到右樹的節點，其值越大。

2.2、Zig-Zig操作

這種情況下，所查找的節點在Z的子樹中，也就是，所查找的節點比X和Y都小。所以要將X，Y及其右子樹都移動到右樹中。首先是Y繞X右旋，然后Z繞Y右旋，最后將Z的右子樹（此時Z的右子節點為Y）移動到右樹中。

2.3、Zig-Zag操作

這種情況中，首先將Y右旋到根。這和Zig的情況是一樣的，然后變成上圖右邊所示的形狀。此時，就與Zag(與Zig相反)的情況一樣了。

最后，在查找到節點后，將三棵樹合并。如圖：

2.4、示例：
下面是一個查找節點19的例子。在例子中，樹中并沒有節點19,最后，距離節點最近的節點18被旋轉到了根作為新的根。節點20也是距離節點19最近的節點，但是節點20沒有成為新根，這和節點20在原來樹中的位置有關系。

3、實現
3.1、splay操作

代碼

tree_node * splay (int i, tree_node * t) {
    tree_node N, *l, *r, *y;
    if (t == NULL) 
        return t;
    N.left = N.right = NULL;
    l = r = &N;

    for (;;)
    {
        if (i < t->item) 
        {
            if (t->left == NULL) 
                break;
            if (i < t->left->item) 
            {
                y = t->left;                           /* rotate right */
                t->left = y->right;
                y->right = t;
                t = y;
                if (t->left == NULL) 
                    break;
            }
            r->left = t;                               /* link right */
            r = t;
            t = t->left;
        } else if (i > t->item)
        {
            if (t->right == NULL) 
                break;
            if (i > t->right->item) 
            {
                y = t->right;                          /* rotate left */
                t->right = y->left;
                y->left = t;
                t = y;
                if (t->right == NULL) 
                    break;
            }
            l->right = t;                              /* link left */
            l = t;
            t = t->right;
        } else {
            break;
        }
    }
    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;
    return t;
}

Rotate right(查找10)：

Link right：

Assemble：

Rotate left(查找20)：

Link left：

3.2、插入操作

代碼

  /*
  **將i插入樹t中,返回樹的根結點(item值==i)
  */
  tree_node* ST_insert(int i, tree_node *t) {
      /* Insert i into the tree t, unless it's already there.    */
      /* Return a pointer to the resulting tree.                 */
      tree_node* node;
      
      node = (tree_node *) malloc (sizeof (tree_node));
     if (node == NULL){
         printf("Ran out of space\n");
         exit(1);
     }
     node->item = i;
     if (t == NULL) {
         node->left = node->right = NULL;
         size = 1;
         return node;
     }
     t = splay(i,t);
     if (i < t->item) {  //令t為i的右子樹
         node->left = t->left;
         node->right = t;
         t->left = NULL;
         size ++;
         return node;
     } else if (i > t->item) { //令t為i的左子樹
         node->right = t->right;
         node->left = t;
         t->right = NULL;
         size++;
         return node;
     } else { 
         free(node); //i值已經存在于樹t中
         return t;
     }
 }

3.3、刪除操作

完整代碼：

代碼

#include <stdio.h>
#include <stdlib.h>

int     size; //結點數量

#define        NUM        20

typedef struct tree_node{
    struct tree_node*    left;
    struct tree_node*    right;
    int        item;
}tree_node;

tree_node* splay (int i, tree_node* t) {
    tree_node N, *l, *r, *y;

    if (t == NULL) 
        return t;

    N.left = N.right = NULL;
     l = r = &N;
 
     for (;;)
     {
         if (i < t->item) 
         {
             if (t->left == NULL) 
                 break;
             if (i < t->left->item) 
             {
                 y = t->left;                           /* rotate right */
                 t->left = y->right;
                 y->right = t;
                 t = y;
                 if (t->left == NULL) 
                     break;
             }
             r->left = t;                               /* link right */
            r = t;
             t = t->left;
         } else if (i > t->item)
         {
             if (t->right == NULL) 
                 break;
             if (i > t->right->item) 
             {
                 y = t->right;                          /* rotate left */
                 t->right = y->left;
                 y->left = t;
                 t = y;
                 if (t->right == NULL) 
                     break;
             }
             l->right = t;                              /* link left */
             l = t;
             t = t->right;
         } else {
             break;
         }
     }
     l->right = t->left;                                /* assemble */
     r->left = t->right;
     t->left = N.right;
     t->right = N.left;
     return t;
 }
 
 /*
 **將i插入樹t中,返回樹的根結點(item值==i)
 */
 tree_node* ST_insert(int i, tree_node *t) {
     /* Insert i into the tree t, unless it's already there.    */
     /* Return a pointer to the resulting tree.                 */
     tree_node* node;
     
     node = (tree_node *) malloc (sizeof (tree_node));
     if (node == NULL){
         printf("Ran out of space\n");
         exit(1);
     }
     node->item = i;
     if (t == NULL) {
         node->left = node->right = NULL;
         size = 1;
         return node;
     }
     t = splay(i,t);
     if (i < t->item) {  //令t為i的右子樹
         node->left = t->left;
         node->right = t;
         t->left = NULL;
         size ++;
         return node;
     } else if (i > t->item) { //令t為i的左子樹
         node->right = t->right;
         node->left = t;
         t->right = NULL;
         size++;
         return node;
    } else { 
         free(node); //i值已經存在于樹t中
         return t;
     }
 }
 
 
 /*
 **從樹中刪除i,返回樹的根結點
 */
 tree_node* ST_delete(int i, tree_node* t) {
     /* Deletes i from the tree if it's there.               */
     /* Return a pointer to the resulting tree.              */
     tree_node* x;
     if (t==NULL) 
         return NULL;
     t = splay(i,t);
     if (i == t->item) {               /* found it */
         if (t->left == NULL) { //左子樹為空,則x指向右子樹即可
             x = t->right;
         } else {
             x = splay(i, t->left); //查找左子樹中最大結點max,令右子樹為max的右子樹
             x->right = t->right;
         }
         size--;
         free(t);
         return x;
     }
     return t;                         /* It wasn't there */
 }
 
 void ST_inoder_traverse(tree_node*    node)
 {
     if(node != NULL)
     {
         ST_inoder_traverse(node->left);
         printf("%d ", node->item);
         ST_inoder_traverse(node->right);
     }
 }
 
 void ST_pre_traverse(tree_node*    node)
 {
     if(node != NULL)
    {
         printf("%d ", node->item);
         ST_pre_traverse(node->left);
         ST_pre_traverse(node->right);
     }
 }
 
 
 void main() {
     /* A sample use of these functions.  Start with the empty tree,         */
     /* insert some stuff into it, and then delete it                        */
     tree_node* root;
     int i;
 
     root = NULL;              /* the empty tree */
     size = 0;
 
     for(i = 0; i < NUM; i++)
         root = ST_insert(rand()%NUM, root);
 
     ST_pre_traverse(root);
     printf("\n");
     ST_inoder_traverse(root);
 
     for(i = 0; i < NUM; i++)
         root = ST_delete(i, root);
 
     printf("\nsize = %d\n", size);
 }