伸展樹(shù)簡(jiǎn)介

伸展樹(shù)(Splay Tree)是特殊的二叉查找樹(shù)。

它的特殊是指，它除了本身是棵二叉查找樹(shù)之外，它還具備一個(gè)特點(diǎn): 當(dāng)某個(gè)節(jié)點(diǎn)被訪問(wèn)時(shí)，伸展樹(shù)會(huì)通過(guò)旋轉(zhuǎn)使該節(jié)點(diǎn)成為樹(shù)根。這樣做的好處是，下次要訪問(wèn)該節(jié)點(diǎn)時(shí)，能夠迅速的訪問(wèn)到該節(jié)點(diǎn)。

特性

1. 和普通的二叉查找樹(shù)相比，具有任何情況下、任何操作的平攤O(log2n)的復(fù)雜度，時(shí)間性能上更好
2. 和一般的平衡二叉樹(shù)比如 紅黑樹(shù)、AVL樹(shù)相比，維護(hù)更少的節(jié)點(diǎn)額外信息，空間性能更優(yōu)，同時(shí)編程復(fù)雜度更低
3. 在很多情況下，對(duì)于查找操作，后面的查詢和之前的查詢有很大的相關(guān)性。這樣每次查詢操作將被查到的節(jié)點(diǎn)旋轉(zhuǎn)到樹(shù)的根節(jié)點(diǎn)位置，這樣下次查詢操作可以很快的完成
4. 可以完成對(duì)區(qū)間的查詢、修改、刪除等操作，可以實(shí)現(xiàn)線段樹(shù)和樹(shù)狀數(shù)組的所有功能

旋轉(zhuǎn)

伸展樹(shù)實(shí)現(xiàn)O(log2n)量級(jí)的平攤復(fù)雜度依靠每次對(duì)伸展樹(shù)進(jìn)行查詢、修改、刪除操作之后，都進(jìn)行旋轉(zhuǎn)操作 Splay(x, root)，該操作將節(jié)點(diǎn)x旋轉(zhuǎn)到樹(shù)的根部。

伸展樹(shù)的旋轉(zhuǎn)有六種類(lèi)型，如果去掉鏡像的重復(fù)，則為三種：zig(zag)、zig-zig(zag-zag)、zig-zag(zag-zig)。

1 自底向上的方式進(jìn)行旋轉(zhuǎn)

1.1 zig旋轉(zhuǎn)

如圖所示，x節(jié)點(diǎn)的父節(jié)點(diǎn)為y，x為y的左子節(jié)點(diǎn)，且y節(jié)點(diǎn)為根。則只需要對(duì)x節(jié)點(diǎn)進(jìn)行一次右旋(zig操作)，使之成為y的父節(jié)點(diǎn)，就可以使x成為伸展樹(shù)的根節(jié)點(diǎn)。

1.2 zig-zig旋轉(zhuǎn)

如上圖所示，x節(jié)點(diǎn)的父節(jié)點(diǎn)y，y的父節(jié)點(diǎn)z，三者在一字型鏈上。此時(shí)，先對(duì)y節(jié)點(diǎn)和z節(jié)點(diǎn)進(jìn)行zig旋轉(zhuǎn)，然后再對(duì)x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zig旋轉(zhuǎn)，最后變?yōu)橛覉D所示，x成為y和z的祖先節(jié)點(diǎn)。

1.3 zig-zag旋轉(zhuǎn)

如上圖所示，x節(jié)點(diǎn)的父節(jié)點(diǎn)y，y的父節(jié)點(diǎn)z，三者在之字型鏈上。此時(shí)，先對(duì)x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zig旋轉(zhuǎn)，然后再對(duì)x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zag旋轉(zhuǎn)，最后變?yōu)橛覉D所示，x成為y和z的祖先節(jié)點(diǎn)。

2 自頂向下的方式進(jìn)行旋轉(zhuǎn)

這種方式不需要節(jié)點(diǎn)存儲(chǔ)其父節(jié)點(diǎn)的引用。當(dāng)我們沿著樹(shù)向下搜索某個(gè)節(jié)點(diǎn)x時(shí)，將搜索路徑上的節(jié)點(diǎn)及其子樹(shù)移走。構(gòu)建兩棵臨時(shí)的樹(shù)——左樹(shù)和右樹(shù)。沒(méi)有被移走的節(jié)點(diǎn)構(gòu)成的樹(shù)稱(chēng)為中樹(shù)。

1. 當(dāng)前節(jié)點(diǎn)x是中樹(shù)的根
2. 左樹(shù)L保存小于x的節(jié)點(diǎn)
3. 右樹(shù)R保存大于x的節(jié)點(diǎn)

開(kāi)始時(shí)候，x是樹(shù)T的根，左樹(shù)L和右樹(shù)R都為空。三種旋轉(zhuǎn)操作：

2.1 zig旋轉(zhuǎn)

如圖所示，x節(jié)點(diǎn)的子節(jié)點(diǎn)y就是我們要找的節(jié)點(diǎn)，則只需要對(duì)y節(jié)點(diǎn)進(jìn)行一次右旋(zig操作)，使之成為x的父節(jié)點(diǎn)，就可以使y成為伸展樹(shù)的根節(jié)點(diǎn)。將y作為中樹(shù)的根，同時(shí)，x節(jié)點(diǎn)移動(dòng)到右樹(shù)R中，顯然右樹(shù)上的節(jié)點(diǎn)都大于所要查找的節(jié)點(diǎn)。

2.2 zig-zig旋轉(zhuǎn)

如上圖所示，x節(jié)點(diǎn)的左子節(jié)點(diǎn)y，y的左子節(jié)點(diǎn)z，三者在一字型鏈上，且要查找的節(jié)點(diǎn)位于z節(jié)點(diǎn)為根的子樹(shù)中。此時(shí)，對(duì)x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zig，然后對(duì)z和y進(jìn)行zig，使z成為中樹(shù)的根，同時(shí)將y及其子樹(shù)掛載到右樹(shù)R上。

2.3 zig-zag旋轉(zhuǎn)

如上圖所示，x節(jié)點(diǎn)的左子節(jié)點(diǎn)y，y的右子節(jié)點(diǎn)z，三者在之字型鏈上，且需要查找的元素位于以z為根的子樹(shù)上。此時(shí)，先對(duì)x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zig旋轉(zhuǎn)，將x及其右子樹(shù)掛載到右樹(shù)R上，此時(shí)y成為中樹(shù)的根節(jié)點(diǎn);然后再對(duì)z節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zag旋轉(zhuǎn)，使得z成為中樹(shù)的根節(jié)點(diǎn)。

2.4 合并

最后，找到節(jié)點(diǎn)或者遇到空節(jié)點(diǎn)之后，需要對(duì)左、中、右樹(shù)進(jìn)行合并。如圖所示，將左樹(shù)掛載到中樹(shù)的最左下方(滿足遍歷順序要求)，將右樹(shù)掛載到中樹(shù)的最右下方(滿足遍歷順序要求)。

伸展樹(shù)的實(shí)現(xiàn)

1.節(jié)點(diǎn)

public class SplayTree<T extends Comparable<T>> { 
    private SplayTreeNode<T> mRoot;    // 根結(jié)點(diǎn) 
 
    public class SplayTreeNode<T extends Comparable<T>> { 
        T key;                // 關(guān)鍵字(鍵值) 
        SplayTreeNode<T> left;    // 左孩子 
        SplayTreeNode<T> right;    // 右孩子 
 
        public SplayTreeNode() { 
            this.left = null; 
            this.right = null; 
        } 
 
        public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) { 
            this.key = key; 
            this.left = left; 
            this.right = right; 
        } 
    } 
}  

SplayTree是伸展樹(shù)，而SplayTreeNode是伸展樹(shù)節(jié)點(diǎn)。在此，我將SplayTreeNode定義為SplayTree的內(nèi)部類(lèi)。在伸展樹(shù)SplayTree中包含了伸展樹(shù)的根節(jié)點(diǎn)mRoot。SplayTreeNode包括的幾個(gè)組成元素:

1. key – 是關(guān)鍵字，是用來(lái)對(duì)伸展樹(shù)的節(jié)點(diǎn)進(jìn)行排序的。
2. left – 是左孩子。
3. right – 是右孩子。

2.旋轉(zhuǎn)

/* 
* 旋轉(zhuǎn)key對(duì)應(yīng)的節(jié)點(diǎn)為根節(jié)點(diǎn)，并返回根節(jié)點(diǎn)。 
* 
* 注意： 
*   (a)：伸展樹(shù)中存在"鍵值為key的節(jié)點(diǎn)"。 
*          將"鍵值為key的節(jié)點(diǎn)"旋轉(zhuǎn)為根節(jié)點(diǎn)。 
*   (b)：伸展樹(shù)中不存在"鍵值為key的節(jié)點(diǎn)"，并且key < tree.key。 
*      b-1 "鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)存在的話，將"鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
*      b-2 "鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)存在的話，則意味著，key比樹(shù)中任何鍵值都小，那么此時(shí)，將最小節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
*   (c)：伸展樹(shù)中不存在"鍵值為key的節(jié)點(diǎn)"，并且key > tree.key。 
*      c-1 "鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)存在的話，將"鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
*      c-2 "鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)不存在的話，則意味著，key比樹(shù)中任何鍵值都大，那么此時(shí)，將最大節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
*/ 
   private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) { 
       if (tree == null) 
           return tree; 
 
       SplayTreeNode<T> N = new SplayTreeNode<T>(); 
       SplayTreeNode<T> l = N; 
       SplayTreeNode<T> r = N; 
       SplayTreeNode<T> c; 
 
       for (; ; ) { 
           int cmp = key.compareTo(tree.key); 
           if (cmp < 0) { 
               if (key.compareTo(tree.left.key) < 0) { 
                   c = tree.left;                           /* rotate right */ 
                   tree.left = c.right; 
                   c.right = tree; 
                   tree = c; 
                   if (tree.left == null) 
                       break; 
               } 
               r.left = tree;                               /* link right */ 
               r = tree; 
               tree = tree.left; 
           } else if (cmp > 0) { 
 
               if (tree.right == null) 
                   break; 
 
               if (key.compareTo(tree.right.key) > 0) { 
                   c = tree.right;                          /* rotate left */ 
                   tree.right = c.left; 
                   c.left = tree; 
                   tree = c; 
                   if (tree.right == null) 
                       break; 
               } 
 
               l.right = tree;                              /* link left */ 
               l = tree; 
               tree = tree.right; 
           } else { 
               break; 
           } 
       } 
       l.right = tree.left;                                /* assemble */ 
       r.left = tree.right; 
       tree.left = N.right; 
       tree.right = N.left; 
 
       return tree; 
   } 
 
   public void splay(T key) { 
       mRoot = splay(mRoot, key); 
   }  

上面的代碼的作用：將”鍵值為key的節(jié)點(diǎn)”旋轉(zhuǎn)為根節(jié)點(diǎn)，并返回根節(jié)點(diǎn)。它的處理情況共包括：

(a)：伸展樹(shù)中存在”鍵值為key的節(jié)點(diǎn)”。

將”鍵值為key的節(jié)點(diǎn)”旋轉(zhuǎn)為根節(jié)點(diǎn)。

(b)：伸展樹(shù)中不存在”鍵值為key的節(jié)點(diǎn)”，并且key < tree->key。

b-1) “鍵值為key的節(jié)點(diǎn)”的前驅(qū)節(jié)點(diǎn)存在的話，將”鍵值為key的節(jié)點(diǎn)”的前驅(qū)節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

b-2) “鍵值為key的節(jié)點(diǎn)”的前驅(qū)節(jié)點(diǎn)存在的話，則意味著，key比樹(shù)中任何鍵值都小，那么此時(shí)，將最小節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

(c)：伸展樹(shù)中不存在”鍵值為key的節(jié)點(diǎn)”，并且key > tree->key。

c-1) “鍵值為key的節(jié)點(diǎn)”的后繼節(jié)點(diǎn)存在的話，將”鍵值為key的節(jié)點(diǎn)”的后繼節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

c-2) “鍵值為key的節(jié)點(diǎn)”的后繼節(jié)點(diǎn)不存在的話，則意味著，key比樹(shù)中任何鍵值都大，那么此時(shí)，將最大節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

下面列舉個(gè)例子分別對(duì)a進(jìn)行說(shuō)明。

在下面的伸展樹(shù)中查找10，，共包括”右旋” –> “右鏈接” –> “組合”這3步。

01, 右旋

對(duì)應(yīng)代碼中的”rotate right”部分

02, 右鏈接

對(duì)應(yīng)代碼中的”link right”部分

03.組合

對(duì)應(yīng)代碼中的”assemble”部分

提示：如果在上面的伸展樹(shù)中查找”70”，則正好與”示例1”對(duì)稱(chēng)，而對(duì)應(yīng)的操作則分別是”rotate left”, “link left”和”assemble”。

其它的情況，例如”查找15是b-1的情況，查找5是b-2的情況”等等，這些都比較簡(jiǎn)單，大家可以自己分析。

3.插入

/** 
     * 將結(jié)點(diǎn)插入到伸展樹(shù)中，并返回根節(jié)點(diǎn) 
     * @param tree 伸展樹(shù)的根節(jié)點(diǎn) 
     * @param z 插入的結(jié)點(diǎn) 
     * @return 
     */ 
    private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) { 
        int cmp; 
        SplayTreeNode<T> y = null; 
        SplayTreeNode<T> x = tree; 
 
        // 查找z的插入位置 
        while (x != null) { 
            y = x; 
            cmp = z.key.compareTo(x.key); 
            if (cmp < 0) 
                x = x.left; 
            else if (cmp > 0) 
                x = x.right; 
            else { 
                System.out.printf("不允許插入相同節(jié)點(diǎn)(%d)!\n", z.key); 
                z = null; 
                return tree; 
            } 
        } 
 
        if (y == null) 
            tree = z; 
        else { 
            cmp = z.key.compareTo(y.key); 
            if (cmp < 0) 
                y.left = z; 
            else 
                y.right = z; 
        } 
 
        return tree; 
    } 
 
    public void insert(T key) { 
        SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null); 
 
        // 如果新建結(jié)點(diǎn)失敗，則返回。 
        if ((z = new SplayTreeNode<T>(key, null, null)) == null) 
            return; 
 
        // 插入節(jié)點(diǎn) 
        mRoot = insert(mRoot, z); 
        // 將節(jié)點(diǎn)(key)旋轉(zhuǎn)為根節(jié)點(diǎn) 
        mRoot = splay(mRoot, key); 
    }  

insert(key)是提供給外部的接口，它的作用是新建節(jié)點(diǎn)(節(jié)點(diǎn)的鍵值為key)，并將節(jié)點(diǎn)插入到伸展樹(shù)中;然后，將該節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

insert(tree, z)是內(nèi)部接口，它的作用是將節(jié)點(diǎn)z插入到tree中。insert(tree, z)在將z插入到tree中時(shí)，僅僅只將tree當(dāng)作是一棵二叉查找樹(shù)，而且不允許插入相同節(jié)點(diǎn)。

4.刪除

/** 
     *  
     * @param tree 伸展樹(shù) 
     * @param key 刪除的結(jié)點(diǎn) 
     * @return 
     */ 
    private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) { 
        SplayTreeNode<T> x; 
 
        if (tree == null) 
            return null; 
 
        // 查找鍵值為key的節(jié)點(diǎn)，找不到的話直接返回。 
        if (search(tree, key) == null) 
            return tree; 
 
        // 將key對(duì)應(yīng)的節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
        tree = splay(tree, key); 
 
        if (tree.left != null) { 
            // 將"tree的前驅(qū)節(jié)點(diǎn)"旋轉(zhuǎn)為根節(jié)點(diǎn) 
            x = splay(tree.left, key); 
            // 移除tree節(jié)點(diǎn) 
            x.right = tree.right; 
        } 
        else 
            x = tree.right; 
 
        tree = null; 
 
        return x; 
    } 
 
    public void remove(T key) { 
        mRoot = remove(mRoot, key); 
    }  

remove(key)是外部接口，remove(tree, key)是內(nèi)部接口。

remove(tree, key)的作用是：刪除伸展樹(shù)中鍵值為key的節(jié)點(diǎn)。

它會(huì)先在伸展樹(shù)中查找鍵值為key的節(jié)點(diǎn)。若沒(méi)有找到的話，則直接返回。若找到的話，則將該節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)，然后再刪除該節(jié)點(diǎn)。

伸展樹(shù)實(shí)現(xiàn)完整代碼

public class SplayTree<T extends Comparable<T>> {     
    private SplayTreeNode<T> mRoot;    // 根結(jié)點(diǎn) 
 
    public class SplayTreeNode<T extends Comparable<T>> { 
        T key;                // 關(guān)鍵字(鍵值) 
        SplayTreeNode<T> left;    // 左孩子 
        SplayTreeNode<T> right;    // 右孩子 
 
        public SplayTreeNode() { 
            this.left = null; 
            this.right = null; 
        } 
 
        public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) { 
            this.key = key; 
            this.left = left; 
            this.right = right; 
        } 
    } 
 
    /* 
 * 旋轉(zhuǎn)key對(duì)應(yīng)的節(jié)點(diǎn)為根節(jié)點(diǎn)，并返回根節(jié)點(diǎn)。 
 * 
 * 注意： 
 *   (a)：伸展樹(shù)中存在"鍵值為key的節(jié)點(diǎn)"。 
 *          將"鍵值為key的節(jié)點(diǎn)"旋轉(zhuǎn)為根節(jié)點(diǎn)。 
 *   (b)：伸展樹(shù)中不存在"鍵值為key的節(jié)點(diǎn)"，并且key < tree.key。 
 *      b-1 "鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)存在的話，將"鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
 *      b-2 "鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)存在的話，則意味著，key比樹(shù)中任何鍵值都小，那么此時(shí)，將最小節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
 *   (c)：伸展樹(shù)中不存在"鍵值為key的節(jié)點(diǎn)"，并且key > tree.key。 
 *      c-1 "鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)存在的話，將"鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
 *      c-2 "鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)不存在的話，則意味著，key比樹(shù)中任何鍵值都大，那么此時(shí)，將最大節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
 */ 
    private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) { 
        if (tree == null) 
            return tree; 
 
        SplayTreeNode<T> N = new SplayTreeNode<T>(); 
        SplayTreeNode<T> l = N; 
        SplayTreeNode<T> r = N; 
        SplayTreeNode<T> c; 
 
        for (; ; ) { 
            int cmp = key.compareTo(tree.key); 
            if (cmp < 0) { 
                if (key.compareTo(tree.left.key) < 0) { 
                    c = tree.left;                           /* rotate right */ 
                    tree.left = c.right; 
                    c.right = tree; 
                    tree = c; 
                    if (tree.left == null) 
                        break; 
                } 
                r.left = tree;                               /* link right */ 
                r = tree; 
                tree = tree.left; 
            } else if (cmp > 0) { 
 
                if (tree.right == null) 
                    break; 
 
                if (key.compareTo(tree.right.key) > 0) { 
                    c = tree.right;                          /* rotate left */ 
                    tree.right = c.left; 
                    c.left = tree; 
                    tree = c; 
                    if (tree.right == null) 
                        break; 
                } 
 
                l.right = tree;                              /* link left */ 
                l = tree; 
                tree = tree.right; 
            } else { 
                break; 
            } 
        } 
        l.right = tree.left;                                /* assemble */ 
        r.left = tree.right; 
        tree.left = N.right; 
        tree.right = N.left; 
 
        return tree; 
    } 
 
    public void splay(T key) { 
        mRoot = splay(mRoot, key); 
    } 
 
 
 
    /** 
     * 將結(jié)點(diǎn)插入到伸展樹(shù)中，并返回根節(jié)點(diǎn) 
     * @param tree 伸展樹(shù)的根節(jié)點(diǎn) 
     * @param z 插入的結(jié)點(diǎn) 
     * @return 
     */ 
    private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) { 
        int cmp; 
        SplayTreeNode<T> y = null; 
        SplayTreeNode<T> x = tree; 
 
        // 查找z的插入位置 
        while (x != null) { 
            y = x; 
            cmp = z.key.compareTo(x.key); 
            if (cmp < 0) 
                x = x.left; 
            else if (cmp > 0) 
                x = x.right; 
            else { 
                System.out.printf("不允許插入相同節(jié)點(diǎn)(%d)!\n", z.key); 
                z = null; 
                return tree; 
            } 
        } 
 
        if (y == null) 
            tree = z; 
        else { 
            cmp = z.key.compareTo(y.key); 
            if (cmp < 0) 
                y.left = z; 
            else 
                y.right = z; 
        } 
 
        return tree; 
    } 
 
    public void insert(T key) { 
        SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null); 
 
        // 如果新建結(jié)點(diǎn)失敗，則返回。 
        if ((z = new SplayTreeNode<T>(key, null, null)) == null) 
            return; 
 
        // 插入節(jié)點(diǎn) 
        mRoot = insert(mRoot, z); 
        // 將節(jié)點(diǎn)(key)旋轉(zhuǎn)為根節(jié)點(diǎn) 
        mRoot = splay(mRoot, key); 
    } 
 
    /* 
 * 刪除結(jié)點(diǎn)(z)，并返回被刪除的結(jié)點(diǎn) 
 * 
 * 參數(shù)說(shuō)明： 
 *     bst 伸展樹(shù) 
 *     z 刪除的結(jié)點(diǎn) 
 */ 
 
    /** 
     * 
     * @param tree 伸展樹(shù) 
     * @param key 刪除的結(jié)點(diǎn) 
     * @return 
     */ 
    private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) { 
        SplayTreeNode<T> x; 
 
        if (tree == null) 
            return null; 
 
        // 查找鍵值為key的節(jié)點(diǎn)，找不到的話直接返回。 
        if (search(tree, key) == null) 
            return tree; 
 
        // 將key對(duì)應(yīng)的節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
        tree = splay(tree, key); 
 
        if (tree.left != null) { 
            // 將"tree的前驅(qū)節(jié)點(diǎn)"旋轉(zhuǎn)為根節(jié)點(diǎn) 
            x = splay(tree.left, key); 
            // 移除tree節(jié)點(diǎn) 
            x.right = tree.right; 
        } 
        else 
            x = tree.right; 
 
        tree = null; 
 
        return x; 
    } 
 
    public void remove(T key) { 
        mRoot = remove(mRoot, key); 
    } 
 
    /* 
    * (遞歸實(shí)現(xiàn))查找"伸展樹(shù)x"中鍵值為key的節(jié)點(diǎn) 
    */ 
    private SplayTreeNode<T> search(SplayTreeNode<T> x, T key) { 
        if (x==null) 
            return x; 
 
        int cmp = key.compareTo(x.key); 
        if (cmp < 0) 
            return search(x.left, key); 
        else if (cmp > 0) 
            return search(x.right, key); 
        else 
            return x; 
    } 
 
    public SplayTreeNode<T> search(T key) { 
        return search(mRoot, key); 
    } 
 
    /* 
   * 查找最小結(jié)點(diǎn)：返回tree為根結(jié)點(diǎn)的伸展樹(shù)的最小結(jié)點(diǎn)。 
   */ 
    private SplayTreeNode<T> minimum(SplayTreeNode<T> tree) { 
        if (tree == null) 
            return null; 
 
        while(tree.left != null) 
            tree = tree.left; 
        return tree; 
    } 
 
    public T minimum() { 
        SplayTreeNode<T> p = minimum(mRoot); 
        if (p != null) 
            return p.key; 
 
        return null; 
    } 
 
    /* 
     * 查找最大結(jié)點(diǎn)：返回tree為根結(jié)點(diǎn)的伸展樹(shù)的最大結(jié)點(diǎn)。 
     */ 
    private SplayTreeNode<T> maximum(SplayTreeNode<T> tree) { 
        if (tree == null) 
            return null; 
 
        while(tree.right != null) 
            tree = tree.right; 
        return tree; 
    } 
 
    public T maximum() { 
        SplayTreeNode<T> p = maximum(mRoot); 
        if (p != null) 
            return p.key; 
 
        return null; 
    }