概念
伸展树是一种二叉查找树，它能在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中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次左右旋转操作或者右左旋转操作。
之字形旋转
