跳转至

1 AVL trees and Splay trees

文本统计：约 893 个字

1.1 AVL trees

目标：加速二叉树的查询速度

性质：

  1. 空二叉树是一个 AVL 树
  2. 如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 \(|h(l_s)−h(r_s)|≤1\)，\(h\) 是其左右子树的高度
  3. 树高为 \(O(\log ⁡n)\)

Balance Factor: 左子树和右子树高度差

如何维护？

我们只需要找到最深的那个trouble finder，然后根据trouble maker与trouble maker的相对位置选择不同的旋转方式

四种旋转方式：

  1. LL/RR rotation

  1. LR/RL rotation

验证搜索的复杂度

我们不从一个固定的n去求搜索复杂度，我们考虑高度为h的树所含节点的最小值。

得到递推公式后，利用斐波那契数列求出\(n_h=\frac{1}{\sqrt 5}(\frac{1+\sqrt{5}}{2})^{h+3}-1\) \(\Rightarrow h=O(\ln n)\)

1.2 Splay trees

——Self-Adjusting Tree

目标：任何从空字数开始的连续M次树操作至多\(O(M\log N)\)

每当一个节点被访问，便将他移到根节点的位置上。然而我们并不能仅仅通过AVL树操作达成这一目标。

比如下面这种情况，经过一番操作并没有让树的高度下降。

Splay操作

对于节点\(X\)，标记其父节点为\(P\)和爷节点\(G\)。

情况1：\(P\)是根节点，直接交换\(P\)和\(G\)，并更新子节点

情况2：\(P\)不是根节点，这时也分为两种情况。

  • 第一种是Zig-Zag
  • 第二钟是Zig-Zig

其中Zig-zag是先对P和X进行左旋转，然后对G和X做右旋转。Zig-zig先对P和G进行右旋转，然后对P和X进行右旋转。

splay trees 的一次查询

插入操作

​ 先按照二叉树的插入方法，将其插入到某个空位置上，然后再进行splay操作

查询操作

​ 按照正常的二叉树查询方法，然后多进行一步 splay 操作

删除操作

  • Find \(X\); (\(X\) will be at the root)
  • Remove \(X\);
  • FindMax (\(T_L\))
  • Make \(T_R\) the right child of the root of \(T_L\) .

首先在树中找到要删除的元素x，将他转到根节点并删去，这样原来的树就分裂成了两棵树，然后将左子树中拥有最大关键字的那一个元素p转到根，由于它是左子树中的最大元素，所以他不存在右儿子，这样只要把原来x的右子树作为p的右子树，就重新合并成了一棵树。

算法分析

见Splay Tree的时间复杂度证明

1.3 Amortized Analysis

Aggregate analysis

Show that for all n, a sequence of n operations takes worst-case time \(T(n)\) in total. In the worst case, the average cost, or amortized cost, per operation is therefore \(T(n)/n\).

就是求连续n步操作一个整体的最坏时间复杂度。

Accounting method

When an operation’s amortized cost \(\hat c_i\) exceeds its actual cost \(c_i\), we assign the difference to specific objects in the data structure as credit. Credit can help pay for later operations whose amortized cost is less than their actual cost.

可以在一些花费较小的步骤先预支一些，然后再花费较大的步骤中花掉预支的费用

Potential method

定义一个势能函数\(\Phi\), 使得\(\hat c_i-c_i=\Phi(D_i)-\Phi(D_{i-1})\)

这样就可以得到\(\sum_{i=1}^n\hat c_i=\sum_{i=1}^n(c_i+\Phi(D_i)-\Phi(D_{i-1})=\sum_{i=1}^nc_i+\Phi(D_n)-\Phi(D_0)\)

一般情况下，一个好的势能函数总能保证一开始的势能是最小的

然后由上述知识解释\(Splay\ Trees:\ T_{amortized}=O(\log N)\)

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！