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