自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

Java數(shù)據(jù)結(jié)構(gòu)與算法解析(八)——伸展樹

作者：佚名
開發(fā) 后端 大數(shù)據(jù) 算法
伸展樹(Splay Tree)是特殊的二叉查找樹。它的特殊是指，它除了本身是棵二叉查找樹之外，它還具備一個(gè)特點(diǎn): 當(dāng)某個(gè)節(jié)點(diǎn)被訪問時(shí)，伸展樹會(huì)通過旋轉(zhuǎn)使該節(jié)點(diǎn)成為樹根。這樣做的好處是，下次要訪問該節(jié)點(diǎn)時(shí)，能夠迅速的訪問到該節(jié)點(diǎn)。

Java數(shù)據(jù)結(jié)構(gòu)與算法解析(八)——伸展樹

伸展樹簡介

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

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

特性

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

旋轉(zhuǎn)

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

伸展樹的旋轉(zhuǎn)有六種類型，如果去掉鏡像的重復(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)為根。則只需要對x節(jié)點(diǎn)進(jìn)行一次右旋(zig操作)，使之成為y的父節(jié)點(diǎn)，就可以使x成為伸展樹的根節(jié)點(diǎn)。

1.2 zig-zig旋轉(zhuǎn)

 

如上圖所示，x節(jié)點(diǎn)的父節(jié)點(diǎn)y，y的父節(jié)點(diǎn)z，三者在一字型鏈上。此時(shí)，先對y節(jié)點(diǎn)和z節(jié)點(diǎn)進(jìn)行zig旋轉(zhuǎn)，然后再對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í)，先對x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zig旋轉(zhuǎn)，然后再對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)我們沿著樹向下搜索某個(gè)節(jié)點(diǎn)x時(shí)，將搜索路徑上的節(jié)點(diǎn)及其子樹移走。構(gòu)建兩棵臨時(shí)的樹——左樹和右樹。沒有被移走的節(jié)點(diǎn)構(gòu)成的樹稱為中樹。

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

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

2.1 zig旋轉(zhuǎn)

 

如圖所示，x節(jié)點(diǎn)的子節(jié)點(diǎn)y就是我們要找的節(jié)點(diǎn)，則只需要對y節(jié)點(diǎn)進(jìn)行一次右旋(zig操作)，使之成為x的父節(jié)點(diǎn)，就可以使y成為伸展樹的根節(jié)點(diǎn)。將y作為中樹的根，同時(shí)，x節(jié)點(diǎn)移動(dòng)到右樹R中，顯然右樹上的節(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í)，對x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zig，然后對z和y進(jìn)行zig，使z成為中樹的根，同時(shí)將y及其子樹掛載到右樹R上。

2.3 zig-zag旋轉(zhuǎn)

  

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

2.4 合并

 

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

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

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

  1. public class SplayTree<T extends Comparable<T>> { 
  2.     private SplayTreeNode<T> mRoot;    // 根結(jié)點(diǎn) 
  3.  
  4.     public class SplayTreeNode<T extends Comparable<T>> { 
  5.         T key;                // 關(guān)鍵字(鍵值) 
  6.         SplayTreeNode<T> left;    // 左孩子 
  7.         SplayTreeNode<T> right;    // 右孩子 
  8.  
  9.         public SplayTreeNode() { 
  10.             this.left = null; 
  11.             this.right = null; 
  12.         } 
  13.  
  14.         public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) { 
  15.             this.key = key; 
  16.             this.left = left; 
  17.             this.right = right; 
  18.         } 
  19.     } 
  20. }  

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

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

2.旋轉(zhuǎn)

  1. /* 
  2. * 旋轉(zhuǎn)key對應(yīng)的節(jié)點(diǎn)為根節(jié)點(diǎn)，并返回根節(jié)點(diǎn)。 
  3. * 
  4. * 注意： 
  5. *   (a)：伸展樹中存在"鍵值為key的節(jié)點(diǎn)"。 
  6. *          將"鍵值為key的節(jié)點(diǎn)"旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  7. *   (b)：伸展樹中不存在"鍵值為key的節(jié)點(diǎn)"，并且key < tree.key。 
  8. *      b-1 "鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)存在的話，將"鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  9. *      b-2 "鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)存在的話，則意味著，key比樹中任何鍵值都小，那么此時(shí)，將最小節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  10. *   (c)：伸展樹中不存在"鍵值為key的節(jié)點(diǎn)"，并且key > tree.key。 
  11. *      c-1 "鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)存在的話，將"鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  12. *      c-2 "鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)不存在的話，則意味著，key比樹中任何鍵值都大，那么此時(shí)，將最大節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  13. */ 
  14.    private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) { 
  15.        if (tree == null) 
  16.            return tree; 
  17.  
  18.        SplayTreeNode<T> N = new SplayTreeNode<T>(); 
  19.        SplayTreeNode<T> l = N; 
  20.        SplayTreeNode<T> r = N; 
  21.        SplayTreeNode<T> c; 
  22.  
  23.        for (; ; ) { 
  24.            int cmp = key.compareTo(tree.key); 
  25.            if (cmp < 0) { 
  26.                if (key.compareTo(tree.left.key) < 0) { 
  27.                    c = tree.left;                           /* rotate right */ 
  28.                    tree.left = c.right; 
  29.                    c.right = tree; 
  30.                    tree = c; 
  31.                    if (tree.left == null) 
  32.                        break; 
  33.                } 
  34.                r.left = tree;                               /* link right */ 
  35.                r = tree; 
  36.                tree = tree.left; 
  37.            } else if (cmp > 0) { 
  38.  
  39.                if (tree.right == null) 
  40.                    break; 
  41.  
  42.                if (key.compareTo(tree.right.key) > 0) { 
  43.                    c = tree.right;                          /* rotate left */ 
  44.                    tree.right = c.left; 
  45.                    c.left = tree; 
  46.                    tree = c; 
  47.                    if (tree.right == null) 
  48.                        break; 
  49.                } 
  50.  
  51.                l.right = tree;                              /* link left */ 
  52.                l = tree; 
  53.                tree = tree.right; 
  54.            } else { 
  55.                break; 
  56.            } 
  57.        } 
  58.        l.right = tree.left;                                /* assemble */ 
  59.        r.left = tree.right; 
  60.        tree.left = N.right; 
  61.        tree.right = N.left; 
  62.  
  63.        return tree; 
  64.    } 
  65.  
  66.    public void splay(T key) { 
  67.        mRoot = splay(mRoot, key); 
  68.    }  

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

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

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

(b)：伸展樹中不存在”鍵值為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í)，將最小節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

(c)：伸展樹中不存在”鍵值為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í)，將最大節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

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

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

 

01, 右旋

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

 

02, 右鏈接

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

 

03.組合

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

 

 

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

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

3.插入

  1. /** 
  2.      * 將結(jié)點(diǎn)插入到伸展樹中，并返回根節(jié)點(diǎn) 
  3.      * @param tree 伸展樹的根節(jié)點(diǎn) 
  4.      * @param z 插入的結(jié)點(diǎn) 
  5.      * @return 
  6.      */ 
  7.     private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) { 
  8.         int cmp; 
  9.         SplayTreeNode<T> y = null; 
  10.         SplayTreeNode<T> x = tree; 
  11.  
  12.         // 查找z的插入位置 
  13.         while (x != null) { 
  14.             y = x; 
  15.             cmp = z.key.compareTo(x.key); 
  16.             if (cmp < 0) 
  17.                 x = x.left; 
  18.             else if (cmp > 0) 
  19.                 x = x.right; 
  20.             else { 
  21.                 System.out.printf("不允許插入相同節(jié)點(diǎn)(%d)!\n", z.key); 
  22.                 z = null; 
  23.                 return tree; 
  24.             } 
  25.         } 
  26.  
  27.         if (y == null) 
  28.             tree = z; 
  29.         else { 
  30.             cmp = z.key.compareTo(y.key); 
  31.             if (cmp < 0) 
  32.                 y.left = z; 
  33.             else 
  34.                 y.right = z; 
  35.         } 
  36.  
  37.         return tree; 
  38.     } 
  39.  
  40.     public void insert(T key) { 
  41.         SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null); 
  42.  
  43.         // 如果新建結(jié)點(diǎn)失敗，則返回。 
  44.         if ((z = new SplayTreeNode<T>(key, null, null)) == null) 
  45.             return; 
  46.  
  47.         // 插入節(jié)點(diǎn) 
  48.         mRoot = insert(mRoot, z); 
  49.         // 將節(jié)點(diǎn)(key)旋轉(zhuǎn)為根節(jié)點(diǎn) 
  50.         mRoot = splay(mRoot, key); 
  51.     }  

insert(key)是提供給外部的接口，它的作用是新建節(jié)點(diǎn)(節(jié)點(diǎn)的鍵值為key)，并將節(jié)點(diǎn)插入到伸展樹中;然后，將該節(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)作是一棵二叉查找樹，而且不允許插入相同節(jié)點(diǎn)。

4.刪除

  1. /** 
  2.      *  
  3.      * @param tree 伸展樹 
  4.      * @param key 刪除的結(jié)點(diǎn) 
  5.      * @return 
  6.      */ 
  7.     private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) { 
  8.         SplayTreeNode<T> x; 
  9.  
  10.         if (tree == null) 
  11.             return null; 
  12.  
  13.         // 查找鍵值為key的節(jié)點(diǎn)，找不到的話直接返回。 
  14.         if (search(tree, key) == null) 
  15.             return tree; 
  16.  
  17.         // 將key對應(yīng)的節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  18.         tree = splay(tree, key); 
  19.  
  20.         if (tree.left != null) { 
  21.             // 將"tree的前驅(qū)節(jié)點(diǎn)"旋轉(zhuǎn)為根節(jié)點(diǎn) 
  22.             x = splay(tree.left, key); 
  23.             // 移除tree節(jié)點(diǎn) 
  24.             x.right = tree.right; 
  25.         } 
  26.         else 
  27.             x = tree.right; 
  28.  
  29.         tree = null; 
  30.  
  31.         return x; 
  32.     } 
  33.  
  34.     public void remove(T key) { 
  35.         mRoot = remove(mRoot, key); 
  36.     }  

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

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

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

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

  1. public class SplayTree<T extends Comparable<T>> {     
  2.     private SplayTreeNode<T> mRoot;    // 根結(jié)點(diǎn) 
  3.  
  4.     public class SplayTreeNode<T extends Comparable<T>> { 
  5.         T key;                // 關(guān)鍵字(鍵值) 
  6.         SplayTreeNode<T> left;    // 左孩子 
  7.         SplayTreeNode<T> right;    // 右孩子 
  8.  
  9.         public SplayTreeNode() { 
  10.             this.left = null; 
  11.             this.right = null; 
  12.         } 
  13.  
  14.         public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) { 
  15.             this.key = key; 
  16.             this.left = left; 
  17.             this.right = right; 
  18.         } 
  19.     } 
  20.  
  21.     /* 
  22.  * 旋轉(zhuǎn)key對應(yīng)的節(jié)點(diǎn)為根節(jié)點(diǎn)，并返回根節(jié)點(diǎn)。 
  23.  * 
  24.  * 注意： 
  25.  *   (a)：伸展樹中存在"鍵值為key的節(jié)點(diǎn)"。 
  26.  *          將"鍵值為key的節(jié)點(diǎn)"旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  27.  *   (b)：伸展樹中不存在"鍵值為key的節(jié)點(diǎn)"，并且key < tree.key。 
  28.  *      b-1 "鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)存在的話，將"鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  29.  *      b-2 "鍵值為key的節(jié)點(diǎn)"的前驅(qū)節(jié)點(diǎn)存在的話，則意味著，key比樹中任何鍵值都小，那么此時(shí)，將最小節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  30.  *   (c)：伸展樹中不存在"鍵值為key的節(jié)點(diǎn)"，并且key > tree.key。 
  31.  *      c-1 "鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)存在的話，將"鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  32.  *      c-2 "鍵值為key的節(jié)點(diǎn)"的后繼節(jié)點(diǎn)不存在的話，則意味著，key比樹中任何鍵值都大，那么此時(shí)，將最大節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  33.  */ 
  34.     private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) { 
  35.         if (tree == null) 
  36.             return tree; 
  37.  
  38.         SplayTreeNode<T> N = new SplayTreeNode<T>(); 
  39.         SplayTreeNode<T> l = N; 
  40.         SplayTreeNode<T> r = N; 
  41.         SplayTreeNode<T> c; 
  42.  
  43.         for (; ; ) { 
  44.             int cmp = key.compareTo(tree.key); 
  45.             if (cmp < 0) { 
  46.                 if (key.compareTo(tree.left.key) < 0) { 
  47.                     c = tree.left;                           /* rotate right */ 
  48.                     tree.left = c.right; 
  49.                     c.right = tree; 
  50.                     tree = c; 
  51.                     if (tree.left == null) 
  52.                         break; 
  53.                 } 
  54.                 r.left = tree;                               /* link right */ 
  55.                 r = tree; 
  56.                 tree = tree.left; 
  57.             } else if (cmp > 0) { 
  58.  
  59.                 if (tree.right == null) 
  60.                     break; 
  61.  
  62.                 if (key.compareTo(tree.right.key) > 0) { 
  63.                     c = tree.right;                          /* rotate left */ 
  64.                     tree.right = c.left; 
  65.                     c.left = tree; 
  66.                     tree = c; 
  67.                     if (tree.right == null) 
  68.                         break; 
  69.                 } 
  70.  
  71.                 l.right = tree;                              /* link left */ 
  72.                 l = tree; 
  73.                 tree = tree.right; 
  74.             } else { 
  75.                 break; 
  76.             } 
  77.         } 
  78.         l.right = tree.left;                                /* assemble */ 
  79.         r.left = tree.right; 
  80.         tree.left = N.right; 
  81.         tree.right = N.left; 
  82.  
  83.         return tree; 
  84.     } 
  85.  
  86.     public void splay(T key) { 
  87.         mRoot = splay(mRoot, key); 
  88.     } 
  89.  
  90.  
  91.  
  92.     /** 
  93.      * 將結(jié)點(diǎn)插入到伸展樹中，并返回根節(jié)點(diǎn) 
  94.      * @param tree 伸展樹的根節(jié)點(diǎn) 
  95.      * @param z 插入的結(jié)點(diǎn) 
  96.      * @return 
  97.      */ 
  98.     private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) { 
  99.         int cmp; 
  100.         SplayTreeNode<T> y = null; 
  101.         SplayTreeNode<T> x = tree; 
  102.  
  103.         // 查找z的插入位置 
  104.         while (x != null) { 
  105.             y = x; 
  106.             cmp = z.key.compareTo(x.key); 
  107.             if (cmp < 0) 
  108.                 x = x.left; 
  109.             else if (cmp > 0) 
  110.                 x = x.right; 
  111.             else { 
  112.                 System.out.printf("不允許插入相同節(jié)點(diǎn)(%d)!\n", z.key); 
  113.                 z = null; 
  114.                 return tree; 
  115.             } 
  116.         } 
  117.  
  118.         if (y == null) 
  119.             tree = z; 
  120.         else { 
  121.             cmp = z.key.compareTo(y.key); 
  122.             if (cmp < 0) 
  123.                 y.left = z; 
  124.             else 
  125.                 y.right = z; 
  126.         } 
  127.  
  128.         return tree; 
  129.     } 
  130.  
  131.     public void insert(T key) { 
  132.         SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null); 
  133.  
  134.         // 如果新建結(jié)點(diǎn)失敗，則返回。 
  135.         if ((z = new SplayTreeNode<T>(key, null, null)) == null) 
  136.             return; 
  137.  
  138.         // 插入節(jié)點(diǎn) 
  139.         mRoot = insert(mRoot, z); 
  140.         // 將節(jié)點(diǎn)(key)旋轉(zhuǎn)為根節(jié)點(diǎn) 
  141.         mRoot = splay(mRoot, key); 
  142.     } 
  143.  
  144.     /* 
  145.  * 刪除結(jié)點(diǎn)(z)，并返回被刪除的結(jié)點(diǎn) 
  146.  * 
  147.  * 參數(shù)說明： 
  148.  *     bst 伸展樹 
  149.  *     z 刪除的結(jié)點(diǎn) 
  150.  */ 
  151.  
  152.     /** 
  153.      * 
  154.      * @param tree 伸展樹 
  155.      * @param key 刪除的結(jié)點(diǎn) 
  156.      * @return 
  157.      */ 
  158.     private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) { 
  159.         SplayTreeNode<T> x; 
  160.  
  161.         if (tree == null) 
  162.             return null; 
  163.  
  164.         // 查找鍵值為key的節(jié)點(diǎn)，找不到的話直接返回。 
  165.         if (search(tree, key) == null) 
  166.             return tree; 
  167.  
  168.         // 將key對應(yīng)的節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。 
  169.         tree = splay(tree, key); 
  170.  
  171.         if (tree.left != null) { 
  172.             // 將"tree的前驅(qū)節(jié)點(diǎn)"旋轉(zhuǎn)為根節(jié)點(diǎn) 
  173.             x = splay(tree.left, key); 
  174.             // 移除tree節(jié)點(diǎn) 
  175.             x.right = tree.right; 
  176.         } 
  177.         else 
  178.             x = tree.right; 
  179.  
  180.         tree = null; 
  181.  
  182.         return x; 
  183.     } 
  184.  
  185.     public void remove(T key) { 
  186.         mRoot = remove(mRoot, key); 
  187.     } 
  188.  
  189.     /* 
  190.     * (遞歸實(shí)現(xiàn))查找"伸展樹x"中鍵值為key的節(jié)點(diǎn) 
  191.     */ 
  192.     private SplayTreeNode<T> search(SplayTreeNode<T> x, T key) { 
  193.         if (x==null) 
  194.             return x; 
  195.  
  196.         int cmp = key.compareTo(x.key); 
  197.         if (cmp < 0) 
  198.             return search(x.left, key); 
  199.         else if (cmp > 0) 
  200.             return search(x.right, key); 
  201.         else 
  202.             return x; 
  203.     } 
  204.  
  205.     public SplayTreeNode<T> search(T key) { 
  206.         return search(mRoot, key); 
  207.     } 
  208.  
  209.     /* 
  210.    * 查找最小結(jié)點(diǎn)：返回tree為根結(jié)點(diǎn)的伸展樹的最小結(jié)點(diǎn)。 
  211.    */ 
  212.     private SplayTreeNode<T> minimum(SplayTreeNode<T> tree) { 
  213.         if (tree == null) 
  214.             return null; 
  215.  
  216.         while(tree.left != null) 
  217.             tree = tree.left; 
  218.         return tree; 
  219.     } 
  220.  
  221.     public T minimum() { 
  222.         SplayTreeNode<T> p = minimum(mRoot); 
  223.         if (p != null) 
  224.             return p.key; 
  225.  
  226.         return null; 
  227.     } 
  228.  
  229.     /* 
  230.      * 查找最大結(jié)點(diǎn)：返回tree為根結(jié)點(diǎn)的伸展樹的最大結(jié)點(diǎn)。 
  231.      */ 
  232.     private SplayTreeNode<T> maximum(SplayTreeNode<T> tree) { 
  233.         if (tree == null) 
  234.             return null; 
  235.  
  236.         while(tree.right != null) 
  237.             tree = tree.right; 
  238.         return tree; 
  239.     } 
  240.  
  241.     public T maximum() { 
  242.         SplayTreeNode<T> p = maximum(mRoot); 
  243.         if (p != null) 
  244.             return p.key; 
  245.  
  246.         return null; 
  247.     }  
責(zé)任編輯：龐桂玉 來源： 36大數(shù)據(jù)
Java數(shù)據(jù)結(jié)構(gòu)算法解析
相關(guān)推薦

2017-08-31 09:45:43

JavaArrayList數(shù)據(jù)

2022-09-21 07:57:33

二叉搜索樹排序二叉樹

2022-09-26 07:56:53

AVL算法二叉樹

2021-03-18 08:44:20

Java數(shù)據(jù)結(jié)構(gòu)算法

2023-09-15 10:33:41

算法數(shù)據(jù)結(jié)構(gòu)

2020-10-30 09:56:59

Trie樹之美

2021-04-07 09:26:37

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-24 10:41:04

Java數(shù)據(jù)結(jié)構(gòu)算法

2020-10-21 14:57:04

數(shù)據(jù)結(jié)構(gòu)算法圖形

2023-03-08 08:03:09

數(shù)據(jù)結(jié)構(gòu)算法歸并排序

2023-03-31 08:24:29

數(shù)據(jù)結(jié)構(gòu)算法數(shù)目

2023-10-27 07:04:20

2021-05-12 09:07:09

Java數(shù)據(jù)結(jié)構(gòu)算法

2022-09-14 07:59:27

字典樹Trie基數(shù)樹

2021-04-01 10:34:18

Java編程數(shù)據(jù)結(jié)構(gòu)算法

2020-11-02 09:15:47

算法與數(shù)據(jù)結(jié)構(gòu)

2021-03-29 10:13:47

Java編程數(shù)據(jù)結(jié)構(gòu)算法

2021-03-19 10:25:12

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-09-29 18:28:41

數(shù)據(jù)結(jié)構(gòu)算法最小生成樹

2023-03-02 08:15:13

點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號