AVL Trees

定义

image.png

  • Balance Factor: AVL Trees, Splay Trees & Amortized Analysis - 图2
  • 注意空节点高度是-1，单个节点是0

Rotation | 旋转

单旋

Right-Right Rotation

  • 逆时针

image.png

Left-Left Rotation

  • 顺时针

image.png

双旋

Left-Right Rotation

两次单旋，先是 trouble maker 的RR Rotation，再是 LL Rotation
image.png
AVL Trees, Splay Trees & Amortized Analysis - 图6

Right-Left Rotation

两次单旋，先是 trouble maker 的LL Rotation，再是RR Rotation
image.png
607CE9118BB60C88BFEC925DB504E113.png

性质

image.png
这样单次查询的时间复杂度是AVL Trees, Splay Trees & Amortized Analysis - 图10，树的高度为AVL Trees, Splay Trees & Amortized Analysis - 图11

伸展树 | Splay Trees

Find

:::warning

  • “Start from an empty tree at most AVL Trees, Splay Trees & Amortized Analysis - 图12 time”，从空树开始的连续M次操作时间不会超过AVL Trees, Splay Trees & Amortized Analysis - 图13
  • 不意味着单次是AVL Trees, Splay Trees & Amortized Analysis - 图14，个别操作可能超过。总的摊还时间是那么多
  • 伸展树的核心想法是：一个节点被访问后，我们就通过一系列AVL树的旋转方法将它转至根节点 ::: 接下来我们研究如何实现这样的想法：
    我们尝试单旋：
    AVL Trees, Splay Trees & Amortized Analysis - 图15
    我们会发现k3沉到了更底部，这不是我们想看到的，接下来我们给出旋转方法：
    image.pngimage.png

    Delete

    接下来我们来看一下删除操作：
    image.png
  1. 找到待删除元素X，经过AVL操作，X变为根节点
  2. 删除X，这时有两个子树
  3. 找到左子树的最大元素Y，经过AVL操作，Y变为左子树的根节点（Y没有右孩子）
  4. 将右子树接到左子树的右孩子上

Amortized Analysis | 摊还分析

image.png
分析方法：

  • 聚合分析
  • 核算法
  • 势能方法

Aggregate Analysis | 聚合分析

对于连续的AVL Trees, Splay Trees & Amortized Analysis - 图20次操作最坏用AVL Trees, Splay Trees & Amortized Analysis - 图21时间，那么单次摊还时间是AVL Trees, Splay Trees & Amortized Analysis - 图22
image.png

Accounting Method | 核算法

我的理解是“多退少补”
image.png

Potential Method | 势能函数