前言
前面的學習中，筆者就二叉樹、二叉查找樹、平衡二叉樹進行了一些總結。此篇文章主要
讨論伸展樹。我們知道的是在二叉查找樹上的基本操作（查找、插入）的時間複雜讀與樹的高度
成正比的關系。對于一個含有N個結點的二叉查找樹來說，這些操作的最壞運作情況為OlogN）。
但是我們這知道在極端的情況下，會導緻樹退化為一個單支樹，這導緻了操作時間為O（N）。
為了克服上面的情況，出現了一些二叉查找樹的變形，例如上篇文章的AVL樹。以及接下來
要讨論的伸展樹。
伸展樹定義
伸展樹是基于二叉查找樹的，它不保證樹一直是平衡的，但是各種操作的平均複雜讀是
O（logN） 。
伸展樹的設計是具體考慮到了局部性原理 （剛被通路的内容下次可能還被通路，查找次數
多的内容可能下次還被通路），為了使整個的查詢時間更小，查詢頻率高的那些結點應當處于
靠近樹根的位置。
這樣，一個比較好的解決方案就是：每次查找就結點之後對樹進行重新構造。把查找的結
點搬移到樹根的位置，以這種方式自調整形式的二叉查找樹就是伸展樹。
旋轉操作
搞清楚了伸展樹的定義，那麼我們來看看是如何實作結點的搬移操作的，和AVL樹一樣同樣
是通過旋轉來操作的。具體如何旋轉，我們分三種情況。單旋轉、一字旋轉和之字旋轉。
這裡我們假定通路的結點為A
單旋轉
對于單旋轉操作，我們先看一個執行個體，之後對其略做分析。
此時，通路的結點A的父結點B是根結點，如果A是B的左孩子，我們對A、B直接進行一次
右旋轉操作，同理如果結點A是B的右孩子則進行一次左旋轉。具體操作就不給執行個體圖了。
一字型旋轉（左左、右右）
同樣的我們先看一個執行個體操作圖：
此時通路的是根結點，它是其父結點的左子樹、且其父結點同時是也是左子樹的情況下
我們需要進行右、右旋轉來達到目地。至于A、B都是右子樹的情況就不示範了，其操作為
左、左旋轉。
之字旋轉
話不多說，我們首先看一個實際操作。
可以看出的是此時的情況與2有些相似，隻是A、B所與的左右不一緻了，對于其操作也不
詳述了，圖中的操作情況以給出。
伸展樹實作（源碼）
package com.kiritor;
/**伸展樹
* @author Kiritor*/
public class SplayTree {
static class BinaryNode {
// Constructors
BinaryNode(Comparable theElement) {
this(theElement, null, null);
}
BinaryNode(Comparable theElement, BinaryNode lt, BinaryNode rt) {
element = theElement;
left = lt;
right = rt;
}
Comparable element;
BinaryNode left;
BinaryNode right;
}
private BinaryNode root;
private static BinaryNode nullNode;
static
{
nullNode = new BinaryNode(null);
nullNode.left = nullNode.right = nullNode;
}
private static BinaryNode newNode = null; //用于插入的操作
private static BinaryNode header = new BinaryNode(null);//用于調整操作
public SplayTree() {
root = nullNode;
}
public void insert(Comparable x) {
if (newNode == null)
newNode = new BinaryNode(x);//建立一個結點
//根結點為空則建立的結點作為根結點
if (root == nullNode) {
newNode.left = newNode.right = nullNode;
root = newNode;
} else {
root = splay(x, root);//調整
if (x.compareTo(root.element) < 0) {
newNode.left = root.left;
newNode.right = root;
root.left = nullNode;
root = newNode;
} else if (x.compareTo(root.element) > 0) {
newNode.right = root.right;
newNode.left = root;
root.right = nullNode;
root = newNode;
} else
return;
}
newNode = null;
}
public void remove(Comparable x) {
BinaryNode newTree;
root = splay(x, root);
if (root.element.compareTo(x) != 0)
return; // Item not found; do nothing
if (root.left == nullNode)
newTree = root.right;
else {
newTree = root.left;
newTree = splay(x, newTree);
newTree.right = root.right;
}
root = newTree;
}
public Comparable findMin() {
if (isEmpty())
return null;
BinaryNode ptr = root;
while (ptr.left != nullNode)
ptr = ptr.left;
root = splay(ptr.element, root);
return ptr.element;
}
public Comparable findMax() {
if (isEmpty())
return null;
BinaryNode ptr = root;
while (ptr.right != nullNode)
ptr = ptr.right;
root = splay(ptr.element, root);
return ptr.element;
}
public Comparable find(Comparable x) {
root = splay(x, root);
if (root.element.compareTo(x) != 0)
return null;
return root.element;
}
public void makeEmpty() {
root = nullNode;
}
public boolean isEmpty() {
return root == nullNode;
}
public void printTree() {
if (isEmpty())
System.out.print("Empty tree ");
else
printTree(root);
}
private BinaryNode splay(Comparable x, BinaryNode t) {
BinaryNode leftTreeMax, rightTreeMin;
header.left = header.right = nullNode;
leftTreeMax = rightTreeMin = header;
nullNode.element = x;
for (;;)
if (x.compareTo(t.element) < 0) {
if (x.compareTo(t.left.element) < 0)
t = rotateWithLeftChild(t);
if (t.left == nullNode)
break;
rightTreeMin.left = t;
rightTreeMin = t;
t = t.left;
} else if (x.compareTo(t.element) > 0) {
if (x.compareTo(t.right.element) > 0)
t = rotateWithRightChild(t);
if (t.right == nullNode)
break;
// Link Left
leftTreeMax.right = t;
leftTreeMax = t;
t = t.right;
} else
break;
leftTreeMax.right = t.left;
rightTreeMin.left = t.right;
t.left = header.right;
t.right = header.left;
return t;
}
static BinaryNode rotateWithLeftChild(BinaryNode k2) {
BinaryNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
static BinaryNode rotateWithRightChild(BinaryNode k1) {
BinaryNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
private void printTree(BinaryNode t) {
if (t != t.left) {
printTree(t.left);
System.out.print(t.element.toString()+" ");
printTree(t.right);
}
}
public static void main(String[] args) {
SplayTree tree = new SplayTree();
tree.insert(12);
tree.insert(8);
tree.insert(2);
tree.insert(4);
tree.insert(14);
tree.insert(16);
tree.insert(6);
tree.insert(1);
tree.insert(11);
tree.remove(8);
System.out.println("被查找的節點:" + tree.find(11));
System.out.println("此時的根:" + tree.root.element);
System.out.println("被查找的節點:" + tree.find(12));
System.out.println("此時的根:" + tree.root.element);
System.out.println("被查找的節點:" + tree.find(11));
System.out.println("此時的根:" + tree.root.element);
System.out.println("伸展樹值情況:");
tree.printTree();
}
}
運作情況為：