简单_伸展树(Splay tree)

如果你注意观察你会发现，输入法就打某个字，如果你下次还打那个字，那么它的位置将在它上一次位置的前面，如果你一直打某个字，那么它每次都往前移动一格或多格。
所以不同的人使用搜狗输入法啊、紫光啊、QQ输入法啊都觉得好使，因为它会根据每个人的不同习惯把你经常打的字弄到靠近前面。
输入法也是要求查询效率的，所以输入法其实也是btree，但是为了更加的智能它使用了另一种树结构-----------伸展树。
伸展树不要求像AVL、红黑树那样追求完美的平衡(其实红黑树也没AVL树那样使劲的追求平衡)，伸展树追求的是90%与10%原则，啥意思呢？这意思是说平时我们打字的时候90%的字我们都不经常去打，至少绝大多数人每天都是在打那10%还不到的字，所以它就把经常使用到的字往根节点挪动。
其实在平时应用中我们都是使用多种数据结构，也就是结构混合使用，千万别拘泥于某一种招式和动作，学数据结构就和练武一样，有时候忘记了才能跳出来才能看的更远更清晰。

package sunfa.tree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

/**
 * 伸展树（Splay Tree）是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。<br>
 * 它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。<br>
 * 在伸展树上的一般操作都基于伸展操作。<br>
 * 
 * 各种查找树存在不足。比如：对于一个有n个节点的平衡树，虽然最坏情况下每次查找的时间复杂度不会超过O(logn)，<br>
 * 但是如果访问模式不均匀，平衡树的效率就会受到影响。此外，它们还需要额外的空间来存储平衡信息。<br>
 * 
 * 伸展树存在的意义:
 * 假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。<br>
 * 于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。<br>
 * splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。<br>
 *
 * @param <K>
 * @param <V>
 */
public class MySplayTree<K, V> {

	public static void main(String[] args) {
		MySplayTree<Integer, Integer> tree = new MySplayTree<Integer, Integer>(
				new Comparator<Integer>() {
					public int compare(Integer o1, Integer o2) {
						return o1 - o2;
					}
				});
		Random ran = new Random();
		int n = 10;
		List<Integer> list = new ArrayList<Integer>();
		int[] arr = { 10, 8, 18, 3, 9, 11, 21 };
		for (int i = 0; i < arr.length; i++) {
			int o = arr[i];// ran.nextInt(100);
			tree.put(o, o);
			list.add(o);
		}
		System.out.println("printTree:");
		tree.printTree(tree.root);
		System.out.println("search:");
		tree.search(8);
		/*
		 * for (int i = 0; i < list.size(); i++) { Entry<Integer, Integer> node
		 * = tree.search(Integer.parseInt(list .get(i).toString()));
		 * System.out.print(node.key + ","); }
		 */
	}

	private Entry<K, V> root;
	private Comparator<K> comp;

	public MySplayTree(Comparator<K> c) {
		comp = c;
	}

	public void put(K key, V value) {
		if (root == null) {
			root = new Entry<K, V>(null, key, value);
			return;
		}
		Entry<K, V> node = root;
		while (true) {
			int c = compare(key, node.key);
			if (c == 0) {
				node.value = value;
				return;
			} else if (c < 0) {
				if (node.left != null) {
					node = node.left;
				} else {
					node.left = new Entry<K, V>(node, key, value);
					return;
				}
			} else {
				if (node.right != null) {
					node = node.right;
				} else {
					node.right = new Entry<K, V>(node, key, value);
					return;
				}
			}
		}
	}

	/**
	 * 如果某个节点被访问，则旋转该节点使得该节点被提升到距离根节点进一步的位置，也就是向上提升一个级别(和他的父节点交换)
	 * @param key
	 * @return
	 */
	public Entry<K, V> search(K key) {
		Entry<K, V> node = root;
		while (true) {
			if (node == null)
				return null;
			int c = compare(key, node.key);
			if (c == 0) {
				spaly(node);
				return node;
			} else if (c < 0) {
				node = node.left;
			} else {
				node = node.right;
			}
		}
	}

	/**
	 * 旋转节点
	 * 关于伸展树的旋转：
	 * 1、被旋转的节点是左子节点
	 * 		a)被旋转节点是根节点的直接子节点
	 * 		b)被旋转节点是根节点的非直接子节点
	 * 2、被旋转的节点是右子节点
	 * 		a)被旋转节点是根节点的直接子节点
	 * 		b)被旋转节点是根节点的非直接子节点
	 * 
	 * 旋转还是很简单的，虽然这里有2个大点，左或者右，但只要写完一边的代码另一边直接copy后把left改成right并且把right改成left就可以了。
	 * @param node   查找到的节点，这个节点需要被提升到其父节点的位置
	 */
	private void spaly(Entry<K, V> node) {
		if (node != root) {
			// 被旋转的节点是左子节点
			if (node.parent.left == node) {
				if (node.parent.parent == null) {// 被旋转节点是根节点的直接子节点
					Entry<K, V> p = node.parent;
					if (node.right != null) {
						p.left = node.right;
						node.right.parent = p;
					} else {
						node.right = p;
						p.parent = node;
					}
					p.parent = node;
					node.right = p;
					node.parent = null;
					this.root = node;
				} else {// 被旋转节点是根节点的非直接子节点
					Entry<K, V> p = node.parent.parent;
					Entry<K, V> p2 = node.parent;
					if (node.right != null) {
						p2.left = node.right;
						node.right.parent = p2;
					} else {
						node.right = p2;
						p2.parent = node;
						p2.left = null;
					}
					p.left = node;
					node.parent = p;
				}
			} else {
				if (node.parent.parent == null) {// 被旋转节点是根节点的直接子节点
					Entry<K, V> p = node.parent;
					if (node.left != null) {
						p.right = node.left;
						node.left.parent = p;
					} else {
						node.left = p;
						p.parent = node;
					}
					p.parent = node;
					node.left = p;
					node.parent = null;
					this.root = node;
				} else {// 被旋转节点是根节点的非直接子节点
					Entry<K, V> p = node.parent.parent;
					Entry<K, V> p2 = node.parent;
					if (node.left != null) {
						p2.right = node.left;
						node.left.parent = p2;
					} else {
						node.left = p2;
						p2.parent = node;
						p2.right = null;
					}
					p.right = node;
					node.parent = p;
				}
			}
		}
	}

	private void printTree(Entry<K, V> node) {
		if (node == null)
			return;
		printTree(node.left);
		System.out.print(node.key + ",");
		printTree(node.right);
	}

	private int compare(K k1, K k2) {
		return comp != null ? (((Comparator<K>) comp).compare(k1, k2))
				: (((Comparable<K>) k1).compareTo(k2));
	}

	static class Entry<K, V> {
		Entry<K, V> parent;
		Entry<K, V> left;
		Entry<K, V> right;
		K key;
		V value;

		public Entry(Entry<K, V> parent, K key, V value) {
			super();
			this.parent = parent;
			this.key = key;
			this.value = value;
		}
	}
}

修正：关于节点旋转部分的代码是按照自己的逻辑写的，因为当时测试的时候没有发现问题就。看了算法导论的关于这部分的伪代码描述感觉自己的那个旋转写的不行。下面是算法道理上旋转部分的代码

/**
	 * 左旋转 <br>
	 * 1、分离旋转的子节点的(左或右)部分，分离出来的的部分称为分离集。  <br>
	 * 2、分离集的左子节点挂接到分离元素原来处的位置。 <br>
	 * 3、分离集去顶替旋转元素的位置(也起到了断开旋转元素与旋转元素父的关系)  <br>
	 * 	a)旋转元素为跟元素  <br>
	 * 	b)旋转元素是它父节点的左子节点 <br>
	 * 	c)旋转元素是它父节点的右子节点,和b)相反 <br>
	 * 4、旋转集(第3步中旋转元素部分被断开，这里称旋转集)挂接到分离集的左子节点处。 <br>
	 * 
	 * @param x
	 *            旋转的元素
	 */
	private void leftRotate(Entry<K, V> x) {
		// ①
		Entry<K, V> y = x.right;// 分离出旋转元素的右子节点
		// ②
		x.right = y.left;// 旋转元素的右子节点的左子节点挂接到旋转元素的右子节点处
		if (y.left != null) {
			y.left.parent = x;//
		}
		// ③
		y.parent = x.parent;// 分离出来的部分挂接到旋转元素的父节点下
		if (x.parent == null) {// 如果旋转元素为根节点,就让旋转元素成为根
			this.root = y;
		} else if (x == x.parent.left) {// 如果旋转元素是它父节点的左子节点,让旋转元素父节点的左指针指向分离出的节点
			x.parent.left = y;
		} else {// 如果是右子节点，就用父节点的右指针指向分离节点
			x.parent.right = y;
		}
		// ④
		y.left = x;// 分离出来的部分的左子节点指向旋转元素
		x.parent = y;// 旋转元素的父节点指向分离出的元素
	}

	/**
	 * 右旋转，参考左旋转
	 * @param x
	 */
	private void rightRotate(Entry<K, V> x) {
		// ①
		Entry<K, V> y = x.left;// 分离出旋转元素的右子节点
		// ②
		x.left = y.right;// 旋转元素的右子节点的左子节点挂接到旋转元素的右子节点处
		if (y.right != null)
			y.right.parent = x;//
		// ③
		y.parent = x.parent;// 分离出来的部分挂接到旋转元素的父节点下
		if (x.parent == null) {// 如果旋转元素为根节点,就让旋转元素成为根
			this.root = y;
		} else if (x == x.parent.left) {// 如果旋转元素是它父节点的左子节点,让旋转元素父节点的左指针指向分离出的节点
			x.parent.left = y;
		} else {// 如果是右子节点，就用父节点的右指针指向分离节点
			x.parent.right = y;
		}
		// ④
		y.right = x;// 分离出来的部分的左子节点指向旋转元素
		x.parent = y;// 旋转元素的父节点指向分离出的元素
	}