本文主要是介绍Splay Tree学习过程，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我把学习经历贴上来（包括看过那些论文，参考过哪些 博客）
http://en.wikipedia.org/wiki/Splay_tree
http://www.link.cs.cmu.edu/splay/ demo
http://www.artofproblemsolving.com/blog/54268 zkw大神
https://www.youtube.com/watch?v=nKZWL9hbcI4 动画演示
伸展树是什么，有什么用，如何实现？
（1）伸展树是什么？
伸展树是一种自适应的平衡二叉树，主要支持的操作是动态维护一个有序表, 从而支持字典, 前驱, 后继, 中序遍历, 优先队列等等多种操作（摘自http://www.artofproblemsolving.com/blog/54268）他支持二叉树的所有操作，并且摊还之后时间复杂度都为对数。但是并不保证某次操作都在对数时间内。
（2）伸展树有什么用？
白书里介绍了可分裂合并序列的一个典型应用时文本编辑器。因为文本需要在任意位置插入和删除字符，但是数组不能实现快速插入，链表不能快速定位。所以数组和链表这时都无用武之地。虽然两者结合起来，形成链式数组在实际运用中比较普遍。但是伸展树也不失为一个选择。（2014/8/11）
（3）如何实现？
首先我们要向伸展树的每个节点要维护哪些信息。要维护哪些信息，我们从他的基本操作入手。记得04年国家集训队论文杨思雨一文《伸展树的基本操作与应用》中给出9中基本操作，我们分析这九种操作然后确立维护哪些信息。
首先记住splay tree也是一种二叉查找树，所以维护的关键字是有序的。
操作1： 查找关键字X
这根普通的二叉查找树没什么区别，我们只要从根节点出发，如果当前节点比要查找的关键字大，则查找右子树，如果比当前节点小，则查找左子树。如果等于那么返回当前节点。
操作2：求最大值
因为是二叉查找树，所以最右边的叶子节点就是最大值。
操作3：求最小值
因为是二叉查找树，所以最左边的叶子节点就是最小值。
操作4：求前驱
这里我们如果对每个保存其父节点的，那么这操作就会简单许多。
操作5：求后继
同理。
这里求前驱和后继要注意一下：
操作6：在介绍插入，删除操作之前，由于要维护树的平衡，所以我们还是先将旋转操作。
其实，旋转操作很好理解的，总共有六种，但是是对称的，所以知道三种，其他三种也就知道了。
1：如果要旋转的节点x的父节点是根节点，那么只要将父节点绕着x节点顺时针旋转一次就好
2：
操作6：插入操作X
首先按照正常的二叉查找树的操作插入X，然后
这篇关于Splay Tree学习过程的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
