分类： C/C++
2013-08-07 17:36:20
日志系统保存缓存的就是伸展树，所以简单介绍下。
假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
总体就是一个思想，在向下查找的过程中，把不符合标准的按照左小右大的原则分别放在左右两棵树上。等到找到想找的节点，把它作为新的根节点，然后把左右棵树作为这个根节点的子树。
这样就实现了查找节点的上移。
同样，如果是插入的话，移上来的会是两个最接近插入数据的，然后把需要插入的节点作为根节点。
那么怎么移动到左右两边呢？
按照常规思路，无非就是从根节点开始，大的放左边，小的放右边。
如下图。
在划分的时候，就这样。
就左树而言，新加入的子树放在左树的最右边的节点。（因为二叉树的查找肯定是缩小范围，这样的话，越后面的节点与查找节点的差距越小。）
但这样存在一个问题，那就是很多时候无法使得树的结构变平衡。
比如
在划分的时候，就这样。
就左树而言，新加入的子树放在左树的最右边的节点。（因为二叉树的查找肯定是缩小范围，这样的话，越后面的节点与查找节点的差距越小。）
但这样存在一个问题，那就是很多时候无法使得树的结构变平衡。
比如
比如左左，左左结构就会三点一线，影响平衡，这种情况最好进行旋转。
这样移出去的子树就会不平衡。
尽量让插入的每部分都平衡以此来保证总体的平衡。
当然左右或者右左就不需要了，首先，这种结构是否旋转对于是否平衡影响不大（直观是这样，我不会证明哈），其次，这种结构本身就是折线，怎么旋转....
所以
就得到了左左或者右右需要旋转，两点一组
这样就得到了自顶向下的方法
同时还有自底向上的，也是遇到左左或者右右需要做不同的处理。
本来就是以要访问的节点X为轴，一直旋转，直到X转到根节点。
但是如果X，X的父节点，X父节点的父节点三点一线的话，就需要特殊处理，需要先以X的父节点为轴转动，再以X为节点转动。也是为了平衡...
代码我自己写了一份，跟lighttpd的很相似
这个网址有用C++实现的代码，可以参考下
http://www.cnblogs.com/huangxincheng/archive/2012/08/04/2623455.html
