伸展樹簡介

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

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

特性

1.和普通的二叉查找樹相比，具有任何情況下、任何操作的平攤O(log2n)的復(fù)雜度，時間性能上更好

2.和一般的平衡二叉樹比如 紅黑樹、AVL樹相比，維護(hù)更少的節(jié)點(diǎn)額外信息，空間性能更優(yōu)，同時編程復(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，三者在一字型鏈上。此時，先對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，三者在之字型鏈上。此時，先對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)存儲其父節(jié)點(diǎn)的引用。當(dāng)我們沿著樹向下搜索某個節(jié)點(diǎn)x時，將搜索路徑上的節(jié)點(diǎn)及其子樹移走。構(gòu)建兩棵臨時的樹——左樹和右樹。沒有被移走的節(jié)點(diǎn)構(gòu)成的樹稱為中樹。

(1) 當(dāng)前節(jié)點(diǎn)x是中樹的根

(2) 左樹L保存小于x的節(jié)點(diǎn)

(3) 右樹R保存大于x的節(jié)點(diǎn)

開始時候，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作為中樹的根，同時，x節(jié)點(diǎn)移動到右樹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)為根的子樹中。此時，對x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zig，然后對z和y進(jìn)行zig，使z成為中樹的根，同時將y及其子樹掛載到右樹R上。

2.3 zig-zag旋轉(zhuǎn)

如上圖所示，x節(jié)點(diǎn)的左子節(jié)點(diǎn)y，y的右子節(jié)點(diǎn)z，三者在之字型鏈上，且需要查找的元素位于以z為根的子樹上。此時，先對x節(jié)點(diǎn)和y節(jié)點(diǎn)進(jìn)行zig旋轉(zhuǎn)，將x及其右子樹掛載到右樹R上，此時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)

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

(1) key – 是關(guān)鍵字，是用來對伸展樹的節(jié)點(diǎn)進(jìn)行排序的。

(2) left – 是左孩子。

(3) right – 是右孩子。

2.旋轉(zhuǎn)

/* * 旋轉(zhuǎn)key對應(yīng)的節(jié)點(diǎ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比樹中任何鍵值都小，那么此時，將最小節(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比樹中任何鍵值都大，那么此時，將最大節(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)：伸展樹中存在”鍵值為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比樹中任何鍵值都小，那么此時，將最小節(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比樹中任何鍵值都大，那么此時，將最大節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

下面列舉個例子分別對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”, “l(fā)ink left”和”assemble”。

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

3.插入

/** * 將結(jié)點(diǎn)插入到伸展樹中，并返回根節(jié)點(diǎn) * @param tree 伸展樹的根節(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; elsey.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)插入到伸展樹中；然后，將該節(jié)點(diǎn)旋轉(zhuǎn)為根節(jié)點(diǎn)。

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

4.刪除

/** * * @param tree 伸展樹 * @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對應(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)的作用是：刪除伸展樹中鍵值為key的節(jié)點(diǎn)。

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

伸展樹實(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對應(yīng)的節(jié)點(diǎ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比樹中任何鍵值都小，那么此時，將最小節(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比樹中任何鍵值都大，那么此時，將最大節(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)插入到伸展樹中，并返回根節(jié)點(diǎn) * @param tree 伸展樹的根節(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; elsey.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ù)說明： * bst 伸展樹 * z 刪除的結(jié)點(diǎn) */ /** * * @param tree 伸展樹 * @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對應(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))查找'伸展樹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)的伸展樹的最小結(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)的伸展樹的最大結(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; }}

來自：http://blog.csdn.net/u012124438/article/details/78067998