入门平衡树——Treap

Brilliant11001 · 2024-02-01 08:59:52 · 算法·理论

前置芝士：

上回书说道，为了维护 \texttt{BST} 的平衡，产生了各种平衡树，其中有一种入门级的平衡树—— \texttt{Treap}。

\texttt{Treap} 的基本思路

满足 \texttt{BST} 性质的二叉查找树不是唯一的，他们维护的是一组相同的数值，本质上是等价的。所以我们可以通过在维持 \texttt{BST} 性质的前提下，通过改变这课二叉搜索树的形态来维持它的左右子树平衡，使树的深度为 O(\log n) 级别。

而这种既维持了 \texttt{BST} 性质，又改变了这棵二叉搜索树的形态的方法就是 “旋转”

注意：不是单纯的转，而是可以通过这种方式形象地理解维护平衡的过程。

“单旋转”是最基本的旋转操作，它又分为“左旋”和“右旋”。如下图所示：

以右旋为例。在初始情况下，x 是 y 的左儿子，A 和 B 分别是 x 的左右子树， C 是 y 的右子树。

“右旋”操作在维持 \texttt{BST} 性质的基础上，把 x 变为 y 的父节点。因为 x 的权值小于 y 的权值，所以 y 应该做 x 的右儿子。

当 x 变成 y 的父节点后，y 的左子树就空了出来，于是 x 原来的右子树 B 就恰好作为 y 的左子树。

右旋也叫 \operatorname{zig}，\operatorname{zig(p)} 可以理解为把 p 的左儿子绕着 p 向右旋转。这里有更形象的解释：

代码：

void zig(int &p) {
    int q = tr[p].ls;
    tr[p].ls = tr[q].rs, tr[q].rs = p, p = q;
}

左旋也叫 \operatorname{zag}，\operatorname{zag(p)} 可以理解为把 p 的右儿子绕着 p 向左旋转。 由于原理和右旋一样，就只放代码了：

void zag(int &p) {
    int q = tr[p].rs;
    tr[p].rs = tr[q].ls, tr[q].ls = p, p = q;
}

经过一系列合理的旋转，就可以使 \texttt{BST} 变得平衡了。比如：

那么，什么才是“合理”的旋转操作呢？上篇文章提到了：在随机数据下，普通的 \texttt{BST} 是趋于平衡的。\texttt{Treap} 的思想就是利用“随机”来创造平衡条件。因为在旋转过程中必须维持 \texttt{BST} 性质，所以 \texttt{Treap} 就把“作用在堆性质上。