Splay Tree 是二叉查找树的一种，它与平衡二叉树、红黑树不同的是，Splay Tree从不强制地保持自身的平衡，每当查找到某个节点n的时候，在返回节点n的同时，Splay Tree会将节点n旋转到树根的位置，这样就使得Splay Tree天生有着一种类似缓存的能力，因为每次被查找到的节点都会被搬到树根的位置，所以当80%的情况下我们需要查找的元素都是某个固定的节点，或者是一部分特定的节点时，那么在很多时候，查找的效率会是O(1)的效率！当然如果查找的节点是很均匀地分布在不同的地方时，Splay Tree的性能就会变得很差了，但Splay Tree的期望的时间复杂度还是O（nlogn）的。
这里先介绍一下左旋（zag）和右旋（zig）的操作
然后就是Splay Tree进行Splay操作的具体步骤，主要分两种情况：
先看图中的左边，查找到的x节点的父节点是y，x是y的左子树，y的父节点z是根节点，y也是z的左子树，要把x旋转到根节点的位置，就要进行zig(y)，然后再进行zig(x)操作
再看图中的右边，查找到的z节点的父节点是y，z是y的右子树，y的父节点x是根节点，y也是x的右子树，要把z旋转到根节点的位置，就要进行zag(y)，然后进行zag(x)操作
若是途中的情况，若需要把x移动到根节点，则需要先进行zig(x)，然后再进行zag(x)操作
还有一种y是z的左子树，x是y的右子树的情况，这时就需要先进行zag(x)，然后再进行zig(x)操作了
下面就给出我自己写的Java版的Splay Tree的一种实现（为了方便，自己定义了类似于Map的接口，仅供参考）：Splay Tree Node
public class SplayTreeNode implements Serializable { private static final long serialVersionUID = 72651428543015658L; protected int key; protected Object value; protected SplayTreeNode father; protected SplayTreeNode leftChild; protected SplayTreeNode rightyChild; // get, set 方法 }
Splay Tree 的接口
public interface SplayTree { /** * 添加/更新node结点 * @param node * @return */ public void put(SplayTreeNode node); /** * 根据key获取对应的node结点，若该结点不存在，则返回null * @param key * @return */ public SplayTreeNode get(int key); /** * 根据key删除对应的node结点，若该结点不存在，则什么都不做 * @param key */ public void remove(int key); /** * 返回SplayTree中结点的个数 * @return */ public int size(); /** * 显示SplayTree的树形结构 */ public void showTree(); /** * 显示SplayTree各个结点的详细信息 */ public void showDetail();
Splay Tree 的实现
public class DefaultSplayTree implements SplayTree, Serializable { private static final long serialVersionUID = 4967206515246041054L; protected int size; protected SplayTreeNode root; public DefaultSplayTree() { this.size = 0; this.root = null; } /* (non-Javadoc) * @see SplayTree#get(int) */ @Override public SplayTreeNode get(int key) { SplayTreeNode currentNode = this.root; while (true) { // 找不到对应的结点，返回null if (currentNode == null) { return null; } // 当前结点就是要找的结点 if (key == currentNode.getKey()) { this.splay(currentNode); return currentNode; // key比当前结点的key要小 } else if (key < currentNode.getKey()) { currentNode = currentNode.getLeftChild(); // key比当前结点的key要大 } else { currentNode = currentNode.getRightyChild(); } } } /* (non-Javadoc) * @see SplayTree#put(SplayTreeNode) */ @Override public void put(SplayTreeNode node) { if (node == null) { return; } // 当前的splay树为空 if (this.root == null) { this.root = node; this.size ++; return; } // 当前结点 SplayTreeNode currentNode = this.root; // 当前结点的父结点 SplayTreeNode currentNodeFather = null; // 当前结点是否是父结点的左子树 boolean isLeft = false;; while (true) { // 当前结点为null，则此位置为添加结点的插入位置 if (currentNode == null) { node.setFather(currentNodeFather); if (isLeft) { currentNodeFather.setLeftChild(node); } else { currentNodeFather.setRightyChild(node); } this.size ++; this.splay(node); return; } // 若当前结点的key比添加的结点的key要小，则在当前结点的左子树中查找 if (node.getKey() < currentNode.getKey()) { currentNodeFather = currentNode; isLeft = true; currentNode = currentNode.getLeftChild(); // 若当前结点的key比添加的结点的key要大，则在当前结点的右子树中查找 } else if (node.getKey() > currentNode.getKey()) { currentNodeFather = currentNode; isLeft = false; currentNode = currentNode.getRightyChild(); // 当前结点的key和要添加的结点的key相等，则更新该结点 } else { currentNode.setValue(node.getValue()); node = currentNode; this.splay(node); return; } } } /* (non-Javadoc) * @see SplayTree#remove(int) */ @Override public void remove(int key) { SplayTreeNode node = this.get(key); if (node != null) { this.join(node.getLeftChild(), node.getRightyChild()); this.size --; } } /** * 对node结点进行右旋 * @param node */ protected void zig(SplayTreeNode node) { // 获取旋转结点的父结点 SplayTreeNode father = node.getFather(); // 将旋转结点的右子树设为父结点的左子树 father.setLeftChild(node.getRightyChild()); // 若旋转结点的右子树不为空，则将父结点设为右子树的父结点 if (node.getRightyChild() != null) { node.getRightyChild().setFather(father); } // 将父结点的父结点（爷爷结点）设为旋转结点的父结点 node.setFather(father.getFather()); // 若爷爷结点不为空 if (father.getFather() != null) { // 若父结点为爷爷结点的左子树，则将旋转结点设为爷爷结点的左子树 if (father == father.getFather().getLeftChild()) { father.getFather().setLeftChild(node); // 若父结点为爷爷结点的右子树，则将旋转结点设为爷爷结点的右子树 } else { father.getFather().setRightyChild(node); } } // 将父结点设为旋转结点的右子树 node.setRightyChild(father); // 更新父结点的父结点为旋转结点 father.setFather(node); } /** * 对node结点进行左旋 * @param node */ protected void zag(SplayTreeNode node) { // 获取旋转结点的父结点 SplayTreeNode father = node.getFather(); // 将旋转结点的左子树设为父结点的右子树 father.setRightyChild(node.getLeftChild()); // 若旋转结点的左子树不为空，则将父结点设为左子树的父结点 if (node.getLeftChild() != null) { node.getLeftChild().setFather(father); } // 将父结点的父结点（爷爷结点）设为旋转结点的父结点 node.setFather(father.getFather()); // 若爷爷结点不为空 if (father.getFather() != null) { // 若父结点为爷爷结点的左子树，则将旋转结点设为爷爷结点的左子树 if (father == father.getFather().getLeftChild()) { father.getFather().setLeftChild(node); // 若父结点为爷爷结点的右子树，则将旋转结点设为爷爷结点的右子树 } else { father.getFather().setRightyChild(node); } } // 将父结点设为旋转结点的左子树 node.setLeftChild(father); // 更新父结点的父结点为旋转结点 father.setFather(node); } /** * 对node结点进行伸展 * @param node */ protected void splay(SplayTreeNode node) { if (this.root == null) { return; } while (node.getFather() != null) { if (node.getFather() == this.root) { if (node == node.getFather().getLeftChild()) { this.zig(node); } else { this.zag(node); } } else if (node.getFather().getFather().getLeftChild() == node.getFather()) { if (node == node.getFather().getLeftChild()) { this.zig(node.getFather()); this.zig(node); } else { this.zag(node); this.zig(node); } } else { if (node == node.getFather().getRightyChild()) { this.zag(node.getFather()); this.zag(node); } else { this.zig(node); this.zag(node); } } } this.root = node; } /** * 合并treeA, treeB，更新root * @param treeA * @param treeB */ protected void join(SplayTreeNode treeA, SplayTreeNode treeB) { if (treeA != null) { treeA.setFather(null); } if (treeB != null) { treeB.setFather(null); } if (treeA == null) { this.root = treeB; return; } if (treeB == null) { this.root = treeA; return; } SplayTreeNode node = treeA; while (node.getRightyChild() != null) { this.splay(node.getRightyChild()); node = node.getRightyChild(); } node.setRightyChild(treeB); treeB.setFather(node); this.root = node; } /* (non-Javadoc) * @see SplayTree#size() */ @Override public int size() { return this.size; } /* (non-Javadoc) * @see SplayTree#showTree() */ @Override public void showTree() { List<SplayTreeNode> nodeList = new ArrayList<SplayTreeNode>(); nodeList.add(this.root); this.bfs(nodeList); } /** * 广度优先遍历SplayTree的每个结点，若结点不为空则输出key值，若为空则输出* * @param nodeList */ protected void bfs(List<SplayTreeNode> nodeList) { List<SplayTreeNode> newNodeList = new ArrayList<SplayTreeNode>(); boolean found = false; for (SplayTreeNode node : nodeList) { if (node != null) { found = true; System.out.print(node.getKey() + " "); newNodeList.add(node.getLeftChild()); newNodeList.add(node.getRightyChild()); } else { System.out.print("* "); newNodeList.add(null); newNodeList.add(null); } } System.out.println(""); if (found) { this.bfs(newNodeList); } } /* (non-Javadoc) * @see SplayTree#showDetail() */ @Override public void showDetail() { this.inorderTraversal(this.root); } /** * 中序遍历SplayTree的每个结点，并输出结点的详细信息 * @param node */ protected void inorderTraversal(SplayTreeNode node) { if (node != null) { System.out.println(node.toString()); this.inorderTraversal(node.getLeftChild()); this.inorderTraversal(node.getRightyChild()); } } }
