伸展树

概念

伸展树是一种二叉查找树，它能在O(logn)内完成插入、查找和删除操作。
伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。

优点

• 可靠的性能-它的平均效率不输于其他平衡树
• 存储所需的内存少-伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小

缺点

伸展树最明显的缺点是它有可能会变成一条链表。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的O(logn)

基本操作

伸展树主要有三种旋转操作，分别为单旋转，一字形旋转和之字形旋转。为了便于解释，我们假设当前被访问节点为X，X的父亲节点为Y（如果X的父亲节点存在），X的祖父节点为Z（如果X的祖父节点存在）。

• 单旋转
  节点X的父节点Y是根节点。这时，如果X是Y的左孩子，我们进行一次右旋操作；如果X是Y的右孩子，则我们进行一次左旋操作。经过旋转，X成为二叉查找树T的根节点，调整结束。

单旋转

• 一字型旋转
  节点X的父节点Y不是根节点，Y的父节点为Z，且X与Y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次左左旋转操作或者右右旋转操作。

一字型旋转

• 之字形旋转
  节点X的父节点Y不是根节点，Y的父节点为Z，X与Y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次左右旋转操作或者右左旋转操作。

之字形旋转