Splay tree --扩展树
扩展树的C语言实现版本，这个是自上而下且节点带大小（size)的扩展树（伸展树）的具体实现。它由Daniel Dominic Sleator 和Robert Endre Tarjan，Tarjan在计算机算法领域，是个大师级别的人物，求强连通图的分量scc算法，很多基础的算法都是他发现的一个扩展树是自适应调整的二叉搜索树。其他常见的二叉搜索树有，AVL tree，red-black tree(红黑树）。但这里有个明显的区别，splay tree 通过节点额外附带属性信息，该信息记录最近访问的节点。它提供基本操作，如插入，查询和删除，平摊情况下都是 O(logN)的渐近复杂度，单次操作，要比，要对于非随机访问操作，splay tree，即使在不知道访问序列的具体模式情况下，也比其他搜索树提供较好性能。二叉搜索树上的所有普通操作（节点的增删改查），如果整合一个基本操作，都成为splaying，按照一定元素顺序Splaying 这个树，即重新排列了节点，并且这个节点被置为根。一种方法是，第一步，基于标准二叉树的执行对该节点原有的操作，然后基于树的旋转，使得这个节点成为根节点。相应的，一个top-down算法可以整合查询和树的重新组织为一个单一的步骤。
?
头文件：
?
?
splaytree算法复杂度：http://en.wikipedia.org/wiki/Splay_tree
平摊分析情况下：
?
Splay treeTypeTreeInvented1985Invented byDaniel Dominic Sleator and Robert Endre TarjanTime complexity
in big O notationAverageWorst caseSpaceO(n)O(n)SearchO(log n)amortized O(log n)InsertO(log n)amortized O(log n)DeleteO(log n)amortized O(log n)?
?
