(转)平衡树--Splay Tree
类别：二叉排序树
空间效率：O(n)时间效率：O(log n)内完成插入、查找、删除操作 创造者：Daniel Sleator和Robert Tarjan 优点：每次查询会调整树的结构，使被查询频率高的条目更靠近树根。
注：所有图片来自wiki。 http://blog.csdn.net/cyberzhg/article/details/8058208
Tree Rotation
树的旋转是splay的基础，对于二叉查找树来说，树的旋转不破坏查找树的结构。Splaying
Splaying是Splay Tree中的基本操作，为了让被查询的条目更接近树根，Splay Tree使用了树的旋转操作，同时保证二叉排序树的性质不变。 Splaying的操作受以下三种因素影响：- 节点x是父节点p的左孩子还是右孩子
- 节点p是不是根节点，如果不是
- 节点p是父节点g的左孩子还是右孩子
Zig Step
当p为根节点时，进行zip step操作。 当x是p的左孩子时，对x右旋； 当x是p的右孩子时，对x左旋。Zig-Zig Step
当p不是根节点，且x和p同为左孩子或右孩子时进行Zig-Zig操作。 当x和p同为左孩子时，依次将p和x右旋； 当x和p同为右孩子时，依次将p和x左旋。Zig-Zag Step
当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。 当p为左孩子，x为右孩子时，将x左旋后再右旋。 当p为右孩子，x为左孩子时，将x右旋后再左旋。 优质内容筛选与推荐>>1、11.Django数据库操作（查）
2、（转）远程下载图片
3、Windows Phone，向8.1开发进军
4、冲刺周期会议十二
5、2016.7.9 计算机网络复习要点第四章之网际控制报文协议ICMP