為實習準備的資料結構（6）-- 伸展樹

前言

之前也寫過兩篇關于伸展樹的，一篇是概念，一篇是實作，
今天重溫一下，

回顧往昔，光陰似箭，日月如梭啊，

伸展樹

現在我們來介紹一種相對與AVL樹更簡單的資料結構，它叫伸展樹，它保證從空樹開始連續任意M次操作最多花費O(MlogN)時間，雖然這種保證并不排除任一次操作花費的時間為O(N)，但是我們關注的是最終的結果，

伸展樹是基于這樣的事實：對于二叉查找樹來說，每次操作的最壞時間為O(N),并不壞，只要它不時常發生就行，

伸展樹的基本想法是：考慮到區域性原理（剛被訪問的內容下次可能仍會被訪問，查找次數多的內容可能下一次會被訪問），為了使整個查找時間更小，被查頻率高的那些節點應當經常處于靠近樹根的位置，這樣，很容易得想到以下這個方案：每次查找節點之后對樹進行重構，把被查找的節點搬移到樹根，這種自調整形式的二叉查找樹就是伸展樹，每次對伸展樹進行操作后，它均會通過旋轉的方法把被訪問節點旋轉到樹根的位置，

自底向上旋轉

旋轉方式參見為實習準備的資料結構（5）-- 圖解AVL樹（平衡二叉搜索樹）
實施上面描述的重新構造的一種方法是執行單旋轉，這意味著我們將在訪問路徑上的每一個節點和它們的父節點進行旋轉，
作為栗子，考慮在下面的樹中對k1進行一次訪問之后所發生的情況：

一次旋轉之后：

k1還沒到根，繼續轉：

轉，再轉：

好，轉完了，

可以看到，本來一棵長樹變成了近乎平衡的樹，
這些旋轉的效果是將k1不斷推向樹根，使得k1的進一步訪問很容易（沒被再推走之前），
不過缺點也很明顯，原先的帶頭大哥k3，百分之九十九也是剛剛坐上頭把交椅，屁股還沒坐熱就讓k1給踢到小角落去了，

更進一步：展開

展開的思路類似于前面介紹的旋轉的想法，不過在旋轉如何實施上我們稍微有一點選擇的余地，我們仍然從底部向上沿著訪問路徑旋轉，
令X是在訪問路徑上的一個非根節點，我們將在這個路徑上實施旋轉操作，如果X的父節點是根節點，那么我們只需要旋轉X和樹根，否則，X就有父親§和祖父(G)，存在以上兩種情況以及對稱的情形要考慮（跟AVL樹差不多），

情況一：之字型（zig-zag）

也就是AVL樹里那倆要雙旋的，

情況二：一字型（zig-zig）

也就是AVL樹里那倆只需要單旋的，

注意甄別這次旋轉和之前旋轉的不同，更要看清楚和標準AVL單旋的差別，
這一次一字型旋轉，其中包含了兩次的AVL單旋，

首先，對P做一次單旋
然后，對X做一次單旋

示例

來看個栗子，還是上面那個，k1

展開的第一步是在k1，顯然是一個之字型，因此我們用k1,k2,k3執行一次標準的AVL雙旋轉，得到如下的樹：

注意和上面的旋轉進行比對，

這一步轉完之后，迎接k1的是一個一字型，因此我們用k1,k4,k5來做一次一字型旋轉，注意看：

雖然從一些小栗子上很難看出來，但是展開操作不僅將訪問節點移動到根處，而且還把訪問路徑上的大部分節點深度大致減少一半的效果（某些淺的節點最多向后推兩個層次），

伸展樹的節點洗掉

這個洗掉略微抽象了一點，簡而言之，就是：

1. 訪問被洗掉節點，從而使得它被提到根節點，
2. 洗掉該節點，整棵二叉樹被一分為二（一般是，除非你洗掉的節點比較特殊，比如最大節點或最小節點）
3. 兩棵樹記為TL和TR
4. 方法一：找到TL中的最大元素m，得益于二叉搜索樹的順序性，此時節點m的左子樹必然為空，這時只需要將TR接在m的右側即可，
5. 方法二：方法一的鏡像，

自頂向下伸展樹

上面的操作，需要一次自頂向下的一次遍歷，而后自底向上的一次遍歷，這可以通過備忘錄模式來實作（自底向上需要沿途保存節點），不過這需要大量的開銷，而且也需要處理許多特殊情況，那么，接下來我們來講一下如何在初始訪問路徑上施行一些旋轉，結果得到在實踐中更快的程序，只用到O(1)的額外空間，但卻保持了O(logN)的攤還時間界，

為了敘述的方便，上圖的右旋叫做X繞Y右旋，左旋叫做Y繞X左旋，

當我們沿著樹向下搜索某個節點X的時候，我們將搜索路徑上的節點及其子樹移走，我們構建兩棵臨時的樹──左樹和右樹，沒有被移走的節點構成的樹稱作中樹，在伸展操作的程序中：
1、當前節點X是中樹的根，
2、左樹L保存小于X的節點，
3、右樹R保存大于X的節點，
開始時候，X是樹T的根，左右樹L和R都是空的，

和自底向上一樣，自頂向下也分了三種情況，

zig(單旋轉)

如上圖，在搜索到X的時候，所查找的節點比X小，將Y旋轉到中樹的樹根，旋轉之后，X及其右子樹被移動到右樹上，很顯然，右樹上的節點都大于所要查找的節點，注意X被放置在右樹的最小的位置，也就是X及其子樹比原先的右樹中所有的節點都要小，這是由于越是在路徑前面被移動到右樹的節點，其值越大，讀者可以分析一下樹的結構，原因很簡單，（就這句，給我點醒了）

通了一點之后，后面就好辦了，

zig-zig(一字型旋轉)

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

zig-zag(之字型旋轉)

在這種情況中，首先將Y右旋到根，這和Zig的情況是一樣的，然后變成上圖右邊所示的形狀，接著，對Z進行左旋，將Y及其左子樹移動到左樹上，這樣，這種情況就被分成了兩個Zig情況，這樣，在編程的時候就會簡化，但是操作的數目增加（相當于兩次Zig情況），

合并樹

將中樹的左右子樹分別連接到左樹的右子樹和右樹的左子樹上，將左右樹作為X的左右子樹，重新最成了一所查找的節點為根的樹，

我一直沒看懂的示例

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

而一直困擾我的，就是第二步到第三步的轉化，為什么要把20提上去，現在明白了，

自頂向下伸展樹代碼實作

#include <stdlib.h>
#include <stdio.h>
	
int size;  /* number of nodes in the tree */
             /* Not actually needed for any of the operations */
typedef struct tree_node Tree;
struct tree_node
{
    Tree *left, *right;
    int item;
};

Tree *splay (int i, Tree *t)
{
 /* Simple top down splay, not requiring i to be in the tree t.  */
 /* What it does is described above.                             */
    Tree 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;
}
/* Here is how sedgewick would have written this.                    */
/* It does the same thing.                                           */
Tree * sedgewickized_splay (int i, Tree * t)
{
    Tree 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 && i < t->left->item)
            {
                y = t->left;
                t->left = y->right;
                y->right = t;
                t = y;
	        }
            if (t->left == NULL)
                break;
            r->left = t;
            r = t;
            t = t->left;
        }
        else if (i > t->item)
        {
            if (t->right != NULL && i > t->right->item)
            {
                y = t->right;
                t->right = y->left;
                y->left = t;
                t = y;
            }
            if (t->right == NULL)
                break;
            l->right = t;
            l = t;
            t = t->right;
        }
        else
            break;
        }
    }
    l->right=t->left;
    r->left=t->right;
    t->left=N.right;
    t->right=N.left;
    return t;
}

Tree * insert(int i, Tree * t)
{
/* Insert i into the tree t, unless it's already there.    */
/* Return a pointer to the resulting tree.                 */
    Tree * new_node;
     
    new_node = (Tree *) malloc (sizeof (Tree));
    if (new_node == NULL)
    {
        printf("Ran out of space\n");
        exit(1);
    }
    new_node ->item = i;
    if (t == NULL)
    {
        new_node->left = new_node->right = NULL;
        size = 1;
        return new_node;
    }
    t = splay(i,t);
    if (i < t->item)
    {
        new_node->left = t->left;
        new_node->right = t;
        t->left = NULL;
        size ++;
        return new_node;
    }
    else if (i > t->item)
    {
        new_node->right = t->right;
        new_node->left = t;
        t->right = NULL;
        size++;
        return new_node;
    }
    else
    {
        /* We get here if it's already in the tree */
        /* Don't add it again                      */
        free(new_node);
        return t;
    }
}

Tree * delete(int i, Tree * t)
{
/* Deletes i from the tree if it's there.               */
/* Return a pointer to the resulting tree.              */
    Tree * x;
    if (t==NULL)
       return NULL;
    t = splay(i,t);
    if (i == t->item)
    {               /* found it */
        if (t->left == NULL)
            x = t->right;
        else
        {
            x = splay(i, t->left);
            x->right = t->right;
        }
        size--;
        free(t);
        return x;
    }
    return t;                         /* It wasn't there */
}

int main(int argv, char *argc[])
{
/* A sample use of these functions.  Start with the empty tree,         */
/* insert some stuff into it, and then delete it                        */
    Tree * root;
    int i;
    root = NULL;              /* the empty tree */
    size = 0;
    for (i = 0; i < 1024; i++)
    {
        root = insert((541*i) & (1023), root);
    }
    printf("size = %d\n", size);
    for (i = 0; i < 1024; i++)
    {
        root = delete((541*i) &(1023), root);
    }
    printf("size = %d\n", size);
}