Splay Tree 是二叉查找树的一种,它与平衡二叉树、红黑树不同的是,Splay Tree从不强制地保持自身的平衡,每当查找到某个节点n的时候,在返回节点n的同时,Splay Tree会将节点n旋转到树根的位置,这样就使得Splay Tree天生有着一种类似缓存的能力,因为每次被查找到的节点都会被搬到树根的位置,所以当80%的情况下我们需要查找的元素都是某个固定的节点,或者是一部分特定的节点时,那么在很多时候,查找的效率会是O(1)的效率!当然如果查找的节点是很均匀地分布在不同的地方时,Splay Tree的性能就会变得很差了,但Splay Tree的期望的时间复杂度还是O(nlogn)的。 这里先介绍一下左旋(zag)和右旋(zig)的操作
先看图中的左边,查找到的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)操作了
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()); } } }
相关推荐
展树(Splay Tree)是一种二叉搜索树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
SplayTree优化版C源代码,带有完整的解释,其实就是置顶向下的Splay tree
SplayTree详细解释
splay tree C# code 伸展树的C#代码实现 我看到没有C#实现版本,所以就把java代码转化成C#实现了一把
伸展树(Splay tree)图解与实现(2020.10.22).pdf
伸展树(Splay Tree)是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
快速八叉树 :(非递归)和简单(<1000行代码)实现是直接从Wikipedia改编而成的,使用与相同的API来针对其他树运行基准测试。 该树基于D.Sleator自上而下的展开...S splaytree import SplayTree from 'splaytree'
红黑树、平衡二叉树、B树、二叉搜索树和SPlay树的C++源码实现,带工程
游戏树展开树的简单实现。 所有函数都具有与 STL 映射函数类似的调用。细节此实现是出于教育目的。 对该库进行了基本测试。 如果您发现错误,请报告它,我会尝试修复它。特征C++11 组件前向迭代器和 const_iterator ...
SplayTree 这个C#项目是从转换而来的 用法: var tree = new SplayTree (); ... 阿皮 与原始项目一致,但是是Pascal风格。 执照 麻省理工学院
erl-splay-tree:Erlang中的splay-tree实现
伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。伸展树是一种自...
该代码包括了二叉树、二叉查找树、平衡树的Java实现代码
伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。 [1] 在伸展树上...
八卦树 单边注解的八叉树
top_down splay_tree 伸展树
此实现提供了类似哈希的界面,并且提供了Splay树中通常不存在的几个功能-有效删除通常访问最少的项,并提供额外的快速搜索选项。叶修剪由于八字树倾向于将自身与最常访问的元素一起组织到树的根部,因此最不频繁...
节点展开树展开树实现进行中...
POJ 3580代码 Splay tree实现