伸展树 伸展树英語Splay Tree是一种能够自我平衡的二叉查找树它能在均摊 O  log  n  displaystyle Olog n 的时间内完成基于伸展Splay操作的插入查找修改和删除操作它是由丹尼爾斯萊托和羅伯特塔揚在年发明的 在伸展树上的一般操作都基于伸展操作假设想要对一个二叉查找树执行一系列的查找操作为了使整个查找时间更小被查频率高的那些条目就应当经常处于靠近树根的位置于是想到设计一个简单方法在每次查找之后对树进行調整把被查找的条目搬移到离树根近一些的地方伸展树应运而生伸展树是一种自调整形式的二叉查找树它会沿着从某个节点到树根之间的路径通过一系列的旋转把这个节点搬移到树根去 它的优势在于不需要记录用于平衡树的冗余信息