数据结构基础14———非线性数据结构之自平衡二叉查找树之伸展树

伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊O(log n)的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

场景：
继AVL树之后，我们给出了2-3树和红黑树。虽然红黑树将2-3树的实现变成了二叉查找树结构，但对于红黑树本身其实还是是引入新的信息表明红还是黑色，并不够纯粹。红红黑黑花里胡哨的，强迫症又犯了怎么办？我们希望要一个纯粹的二叉树
实现而不需要去管这些红黑颜色，不需要去保存额外的信息，有没有其他的方案呢？

伸展树的出发点是这样的：考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问，也就是我们通常所说的"二八"法则），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。这样，很容易得想到以下这个方案：每次查找节点之后对树进行重构，把被查找的节点搬移到树根，这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后，它均会通过旋转的方法把被访问节点旋转到树根的位置。

为了将当前被访问节点旋转到树根，我们通常将节点自底向上旋转，直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系（指中序遍历结果是全序的）情况下，所有基本操作的平摊复杂度仍为O（log n）（平摊复杂度，摊返分析见后面章节）

优点

1.伸展树的自我平衡使其拥有良好的性能，因为频繁访问的节点会被移动到更靠近根节点，进而获得更快的访问速度。

2.可靠的性能——它的平均效率不输于其他平衡树

3.存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。

缺点：
伸展树最显著的缺点是它有可能会变成一条链。例如，在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率，操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的——O(log n)。

即使以“只读”方式（例如通过查找操作）访问伸展树，其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言，如果允许多个线程同时执行查找操作，则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用，尽管用于实现优先级队列的方式不多。

伸展(splay)

当一个节点x被访问过后，伸展操作会将x移动到根节点。为了进行伸展操作，我们会进行一系列的旋转，每次旋转会使x离根节点更近。通过每次访问节点后的伸展操作，最近访问的节点都会离根节点更近，且伸展树也会大致平衡，这样我们就可以得到期望均摊时间复杂度的下界——均摊O(log n)。

每次旋转操作由三个因素决定：

x是其父节点p的左儿子还是右儿子；
p是否为根；
p是其父节点g（x的祖父节点）的左儿子还是右儿子。
在每次旋转操作后，设置g的儿子为x是很重要的。如果g为空，那么x显然就是根节点了。

共有三种旋转操作，每种都有左旋（Zig）和右旋（Zag）两种情况。为了简单起见，对每种旋转操作只展示一种情况(因为是对称的，程序上是6种但是逻辑上是3种)。这些旋转操作是：

Zig：当p为根节点时进行。Zig通常只在伸展操作的最后一步进行。
(单旋转)

Zig-zig和Zag-zag：当p不为根节点且x和p都为左儿子或都为右儿子时进行。下图为x和p都为左儿子时的情况（即Zig-zig），需先将p右旋到g的位置，再将x右旋到p的位置。
(一字型旋转)

Zig-zag和Zag-zig：当p不为根节点且x为左儿子而p为右儿子时进行，反之亦然。下图为前述情况（即Zig-zag），需先将x左旋到p到的位置，再将x右旋到g的位置。
（之字形旋转）

连接(join)

给出两棵树S和T，且S的所有元素都比T的元素要小。下面的步骤可以把它们连接成一棵树：

伸展S中最大的节点。现在这个节点变为S的根节点，且没有右儿子。
令T的根节点变为其右儿子。

分割(split)

给出一棵树和一个元素x，返回两棵树：一棵中所有的元素均小于等于x，另一棵中所有的元素大于x。下面的步骤可以完成这个操作：

伸展x。这样的话x成为了这棵树的根所以它的左子树包含了所有比x小的元素，右子树包含了所有比x大的元素。
把x的右子树从树中分割出来。

插入(insert)

插入操作是一个比较复杂的过程，具体步骤如下: 我们假定要插入的值为k。

如果当前树为空，则直接插入根。

如果当前节点的权值等于k则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行splay操作。

否则按照二叉查找树的性质

public class SplayTree<T extends Comparable<T>> {

	private SplayTreeNode<T> mRoot; // 根结点

	public class SplayTreeNode<T extends Comparable<T>> {
		T key; // 关键字(键值)
		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;
		}
	}

	public SplayTree() {
		mRoot = null;
	}

	/*
	 * 前序遍历"伸展树"
	 */
	private void preOrder(SplayTreeNode<T> tree) {
		if (tree != null) {
			System.out.print(tree.key + " ");
			preOrder(tree.left);
			preOrder(tree.right);
		}
	}

	public void preOrder() {
		preOrder(mRoot);
	}

	/*
	 * 中序遍历"伸展树"
	 */
	private void inOrder(SplayTreeNode<T> tree) {
		if (tree != null) {
			inOrder(tree.left);
			System.out.print(tree.key + " ");
			inOrder(tree.right);
		}
	}

	public void inOrder() {
		inOrder(mRoot);
	}

	/*
	 * 后序遍历"伸展树"
	 */
	private void postOrder(SplayTreeNode<T> tree) {
		if (tree != null) {
			postOrder(tree.left);
			postOrder(tree.right);
			System.out.print(tree.key + " ");
		}
	}

	public void postOrder() {
		postOrder(mRoot);
	}

	/*
	 * (递归实现)查找"伸展树x"中键值为key的节点
	 */
	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);
	}

	/*
	 * (非递归实现)查找"伸展树x"中键值为key的节点
	 */
	private SplayTreeNode<T> iterativeSearch(SplayTreeNode<T> x, T key) {
		while (x != null) {
			int cmp = key.compareTo(x.key);

			if (cmp < 0)
				x = x.left;
			else if (cmp > 0)
				x = x.right;
			else
				return x;
		}

		return x;
	}

	public SplayTreeNode<T> iterativeSearch(T key) {
		return iterativeSearch(mRoot, key);
	}

	/*
	 * 查找最小结点：返回tree为根结点的伸展树的最小结点。
	 */
	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;
	}

	/*
	 * 查找最大结点：返回tree为根结点的伸展树的最大结点。
	 */
	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;
	}

	/*
	 * 旋转key对应的节点为根节点，并返回根节点。
	 *
	 * 注意： (a)：伸展树中存在"键值为key的节点"。 将"键值为key的节点"旋转为根节点。 (b)：伸展树中不存在"键值为key的节�