什么是 zip 树，它是如何工作的？
tem*_*def 20 random binary-search-tree skip-lists data-structures
我听说过一种新的平衡 BST 数据结构，称为zip 树。什么是zip树？它是如何工作的？
tem*_*def 42
从较高层次来看，zip 树是
\n- \n
- 随机平衡二叉搜索树， \n
- 这是一种将跳表编码为 BST 的方法，并且 \n
- 它使用称为压缩和解压缩的一对操作，而不是树旋转。 \n
第一个要点 - zip 树是随机的、平衡的 BST - 给人一种 zip 树在高层次上实现的效果的感觉。它是一种平衡二叉搜索树，与 Treap 类似，但与红/黑树不同，它使用随机化来平衡树。从这个意义上说，zip 树并不能保证是平衡树，但具有非常高的平衡概率。
\n第二个要点 - zip 树是跳表的编码 - 展示了 zip 树的来源以及为什么直观地它们是平衡的。您可以将 zip 树视为采用随机跳表数据结构的一种方式，该结构支持预期时间 O(log n) 内的所有主要操作，并将其表示为二叉搜索树。这提供了关于 zip 树从何而来以及为什么我们期望它们如此快的直觉。
\n第三个要点 - zip 树使用压缩和解压缩而不是树旋转 - 解释了 zip 树的名称以及编写一棵树的感觉。Zip 树与其他类型的平衡树（例如红/黑树或 AVL 树）的不同之处在于，节点在树周围移动不是通过旋转，而是通过一对操作将较大的节点链转换为两个较小的链或反之亦然。
\n这个答案的其余部分更深入地探讨了 zip 树的来源、它们的工作原理以及它们的结构。
\n回顾：跳过列表
\n为了理解 zip 树从何而来，我们首先回顾一下另一个数据结构，即跳跃列表。跳跃列表是一种数据结构，类似于二叉搜索树，按排序顺序存储元素的集合。然而，跳表不是树结构。相反，跳跃列表的工作原理是通过多层链接列表按排序顺序存储元素。此处显示了一个示例跳过列表：
\n
如您所见，元素按排序顺序表示。每个元素都有一个关联的height，并且是许多等于其高度的链表的一部分。跳表的所有元素都参与底层。理想情况下，大约一半的节点将位于其上方的层中，大约四分之一的节点将位于其上方的层中，大约八分之一的节点将位于其上方的层中，等等。（更多关于如何稍后工作。）
\n要在跳跃列表中进行查找，我们从最顶层开始。我们在跳跃列表中向前走，直到（1）我们找到我们正在寻找的元素，（2）我们找到一个比我们正在寻找的元素更大的元素，或者（3）我们到达了末尾列表。在第一种情况下，我们打开香槟庆祝，因为我们发现了我们正在寻找的物品，并且没有什么可做的。在第二种或第三种情况下，我们“超出”了我们正在寻找的元素。但这没什么好担心的 - 事实上，这很有帮助，因为这意味着我们正在寻找的东西必须位于我们遇到“过冲”的节点和它之前的节点之间。因此，我们将转到上一个节点，下拉一层，然后从那里开始搜索。
\n例如，我们如何搜索 47：
\n
在这里，蓝色边缘表示我们向前移动的链接，红色边缘表示我们超出并决定下降到下一层的位置。
\n关于跳表如何工作的一个强有力的直觉（稍后当我们过渡到 zip 树时我们将需要它）是跳表的最顶层将跳表的其余元素划分为不同的范围。你可以在这里看到这个：
\n
直观上，如果我们能够跳过查看大多数元素，那么跳跃列表搜索将会“快速”。例如，想象一下，跳表的倒数第二层仅存储跳表的所有其他元素。在这种情况下，遍历倒数第二层的速度是遍历底层的两倍，因此我们预计从倒数第二层开始的查找所需的时间是从倒数第二层开始的查找所需的时间的一半底层。类似地，想象一下该层之上的层仅存储其之下层的所有其他元素。然后，在该层中搜索所需的时间大约是搜索其下方层所需时间的一半。更一般地说，如果每层仅存储其下方层的大约一半元素，那么我们可以在搜索过程中跳过跳过列表中的大量元素，从而获得良好的性能。
\n跳表通过使用以下规则来实现这一点：每当我们将一个元素插入到跳表中时，我们都会抛一枚硬币，直到出现正面。然后，我们将新插入节点的高度设置为我们最终抛出的硬币数量。这意味着它有 50% 的机会留在当前层，有 50% 的机会移动到其上方的层，这意味着，总的来说，大约一半的节点将仅位于底层，大约一半的节点将位于底层。左边将是上面的一层，剩下的大约一半将是上面的一层，等等。
\n（对于那些有数学背景的人来说，您也可以说跳跃列表中每个节点的高度是一个 Geom(1/2) 随机变量。）
\n下面是使用高度 1 将 42 插入到上面所示的跳跃列表中的示例：
\n
从跳表中删除也是一个相当简单的操作：我们只需将它从它恰好所在的链表中拼接出来。这意味着，如果我们要删除刚刚从上面的列表中插入的 42，我们最终会得到使用与我们开始时相同的跳过列表。
\n可以证明，基于每个列表中的项目数大约是其下一个列表中的项目数的一半这一事实，跳跃列表中的插入、删除或查找的预期成本为 O(log n) 。（这意味着我们期望看到 O(log n) 层，并且在每层中只采取恒定数量的步骤。）
\n从滑雪者到滑索树
\n现在我们已经回顾了跳过列表，让我们谈谈 zip 树的来源。
\n让我们假设您正在查看跳过列表数据结构。您确实喜欢每个操作的预期 O(log n) 性能，并且喜欢它在概念上的简单性。只有一个问题 - 你真的不喜欢链表，并且用一层又一层的链表构建东西的想法不会让你兴奋。另一方面，你真的很喜欢二叉搜索树。它们有一个非常简单的结构 - 每个节点只有两个指针离开它，并且有一个关于所有内容放置位置的简单规则。那么这个问题自然而然地出现了：除了 BST 形式之外，您能否获得跳表的所有好处？
\n事实证明，有一个非常好的方法可以做到这一点。让我们假设您有此处显示的跳过列表：
\n
现在，假设您在此跳跃列表中执行查找。该搜索将如何进行？好吧，你总是从扫描跳过列表的顶层开始，向前移动，直到找到一个比你要查找的键大的键，或者直到你到达列表的末尾并发现有顶层不再有节点。然后，您可以从那里“下降”一级进入仅包含您访问的最后一个节点和超出的节点之间的键的子跳转列表。
\n可以将此完全相同的搜索建模为 BST 遍历。具体来说，我们可以将跳表的顶层表示为 BST：
\n
请注意，所有这些节点都链接到右侧，其想法是“在跳过列表中向前扫描”对应于“访问越来越大的键”。在 BST 中，从一个节点移动到更大的节点对应于向右移动，因此节点链向右移动。
\n现在，BST 中的每个节点最多可以有两个子节点，在上图中，每个节点要么有 0 个子节点，要么有 1 个子节点。如果我们通过标记它们对应的范围来填充缺失的子项，我们就会得到这个。
\n
\n
嘿，等一下！看起来 BST 确实以与跳跃列表相同的方式对键的空间进行分区。这是有希望的，因为它表明我们正在做一些事情。另外，它为我们提供了一种填充树的其余部分的方法：我们可以递归地将跳表的子范围转换为它们自己的 BST，并将整个事物粘合在一起。如果我们这样做，我们就会得到这棵编码跳跃列表的树：
\n
\n
我们现在有一种将跳表表示为二叉搜索树的方法。很酷！
\n现在，我们可以反过来吗？也就是说，我们可以从 BST 转到跳跃列表吗？一般来说，没有一种独特的方法可以做到这一点。毕竟，当我们将跳表转换为 BST 时，我们确实丢失了一些信息。具体来说，跳表中的每个节点都有一个关联的高度，虽然 BST 中的每个节点也有一个高度，但它与跳表节点高度没有紧密联系。为了解决这个问题，我们用它来自的跳表节点的高度来标记每个 BST 节点。如下所示：
\n
\n
现在，一些不错的模式出现了。首先，请注意每个节点的关联编号都大于其左子节点的编号。这是有道理的，因为向左的每一步都对应于下降到跳跃列表的子范围，其中节点的高度较低。同样，每个节点的关联数都大于或等于其右子节点的数。这又是有道理的——向右移动意味着
\n- \n
- 在我们已经所在的同一高度继续前进，在这种情况下高度保持不变，或者 \n
- 到达范围的末端并下降到子范围，在这种情况下高度会降低。 \n
我们可以更多地谈论树的形状吗？我们当然可以！例如，在跳跃列表中，每个节点的高度是通过翻转硬币来选择的，直到得到正面，然后计算我们总共翻转了多少枚硬币。（或者，像以前一样，它以 1/2 的概率呈几何分布）。因此，如果我们想象构建一个与跳跃列表相对应的 BST，我们希望分配给节点的数字以相同的方式计算。
\n将这三个规则放在一起，我们得到以下规则，它定义了我们的树（zip 树）的形状！
\n\n\nzip树是二叉搜索树，其中
\n\n
\n- 每个节点都有一个关联的数字，称为其等级。通过翻转硬币直到正面翻转，然后计算总共抛出了多少枚硬币，将排名随机分配给每个节点。
\n- 每个节点的等级严格大于其左子节点的等级。
\n- 每个节点的等级都大于或等于其右子节点的等级。
\n
令人惊奇的是，像跳表这样的东西可以通过写出如此简单的规则来表示为 BST！
\n插入元素：解压
\n假设您有一个 zip 树。您将如何向其中插入新元素？
\n原则上我们可以通过纯粹查看上面给出的规则来回答这个问题，但我认为通过记住zip 树是伪装的跳跃列表，可以更容易地解决这个问题。例如，这是上面的 zip 树及其关联的跳过列表：
\n\n
现在，假设我们想要将 18 插入到这个 zip 树中。为了看看结果如何，想象一下我们决定给 18 赋予 2 的等级。我们不看 zip 树，而是看看如果我们插入到跳表中会发生什么。这将产生这个跳过列表：
\n
如果我们采用这个跳表并将其编码为 zip 树，我们将得到以下结果：
\n
有趣的是，即使我们不知道如何执行插入，我们也可以看到插入后树需要是什么样子。然后，我们可以通过从这些“之前”和“之后”图片进行逆向工程来尝试找出插入逻辑需要是什么样子。
\n让我们考虑一下这个插入对我们的 zip 树做了什么改变。首先，让我们回想一下我们如何将跳过列表编码为 zip 树的直觉。具体来说，跳跃列表中同一级别的节点链（没有中间的“更高”元素）映射到 zip 树中向右倾斜的节点链。将元素插入到跳表中相当于将一些新元素添加到其中一个级别中，其效果是（1）将新元素添加到跳表的某个级别中，以及（2）获取跳表中先前存在的元素链在某种程度上相邻，然后打破这些联系。
\n例如，当我们将 18 插入此处显示的跳跃列表时，我们向此处突出显示的蓝色链添加了新内容，并且破坏了此处显示的所有红色链：
\n
这会在我们的 zip 树中转化为什么呢？好吧，我们可以突出显示此处插入项目的蓝色链接，以及被剪切的红色链接：
\n
让我们看看是否能弄清楚这里发生了什么。幸运的是，这里的蓝色链接很容易找到。想象一下，我们进行常规 BST 插入，将 18 添加到我们的树中。当我们这样做时，我们会在到达这一点时暂停：
\n
请注意，我们按下了与我们具有相同等级的键。这意味着，如果我们继续向右移动，我们就会追踪到跳跃列表的这个区域：
\n
为了找到蓝色边缘——我们要去的地方——我们只需要沿着这条节点链向下走，直到找到一个比我们大的节点。然后，蓝色边缘（我们的插入点）由该节点与其上方节点之间的边缘给出。
\n我们可以用不同的方式识别这个位置：我们找到了蓝色边缘 - 我们的插入点 - 当我们到达要插入的节点 (1) 的排名比左侧节点更高的点时， (2) 具有大于或等于右侧节点的等级，并且 (3) 如果右侧节点具有相同的等级，则要插入的新项目小于右侧的项目。前两条规则确保我们插入到跳跃列表的正确级别，最后一个规则确保我们插入到跳跃列表该级别的正确位置。
\n现在，我们的红色边缘在哪里？直观上，这些是被“剪切”的边，因为 18 已添加到跳跃列表中。这些项目以前位于蓝色边缘相对两端的两个节点之间，但需要将哪些节点划分到由该蓝色边缘的分割版本定义的新范围中。
\n幸运的是，这些边缘出现在非常好的地方。这是它们映射到的位置：
\n
（在这张图中，我将新节点 18 放置在我们在跳跃列表中标识的蓝色边缘的中间。这会导致结果不再是 BST，但我们将立即修复该问题。）
\n请注意，如果我们要完成常规 BST 插入，这些边与我们遇到的边完全相同 - 这是通过查找 18 追踪出的路径！这里发生了一些非常美好的事情。请注意
\n- \n
- 每次我们向右移动时，节点在被切割时都会移至 18 的右侧，并且 \n
- 每次我们向左移动时，该节点在被切割时都会移至 18 的左侧。 \n
换句话说，一旦我们找到插入的蓝色边缘，我们就会继续行走，就好像我们像往常一样进行插入，跟踪我们向左走的节点和我们向右走的节点。然后，我们可以将向左移动的所有节点链接在一起，并将向右移动的所有节点链接在一起，将结果粘合在新节点下。如下所示：
\n
此操作称为解压缩，这就是我们获得“zip 树”名称的来源。这个名字有点道理——我们采用两个交错结构（左链和右链）并将它们分成两个更简单的线性链。
\n总结一下：
\n\n\n将 x 插入 zip 树的工作原理如下：
\n\n
\n- 通过翻转硬币并计算需要翻转多少次才能获得正面，为 x 分配一个随机排名。
\n- 搜索 x。一旦到达某个节点就停止搜索
\n\n
\n- 该节点的左子节点的等级低于 x，
\n- 该节点的右子节点的等级小于或等于 x，并且
\n- 该节点的右子节点，如果它与 x 具有相同的等级，则具有比 x 更大的键。
\n\n
\n- 执行解压缩。具体来说：
\n- 像以前一样继续搜索 x，记录我们何时向左移动和何时向右移动。
\n- 通过使每个节点成为先前访问的左移动节点的左子节点，将我们向左移动的所有节点链接在一起。
\n- 通过使每个节点成为先前访问的右移节点的右子节点，将我们向右移动的所有节点链接在一起。
\n- 使这两条链成为节点 x 的子节点。
\n
您可能会注意到，此“解压缩”过程与执行不同操作时所得到的过程等效。您可以通过照常插入 x 来获得相同的结果，然后使用树旋转将 x 在树中拉得越来越高，直到它停在正确的位置。这是执行插入的完全有效的替代策略，尽管它有点慢，因为需要对树进行两次遍历（自上而下的遍历在叶子处插入，然后自下而上的遍历进行旋转）。
\n删除元素：压缩
\n现在我们已经了解了如何插入元素，那么我们如何删除它们呢？
\n让我们从一个有用的观察开始：如果我们将一个项目插入到 zip 树中然后将其删除，我们最终会得到与开始时完全相同的树。要了解这是为什么，我们可以回顾一下跳跃列表。如果您添加然后从跳跃列表中删除某些内容，那么您最终会得到与之前相同的跳跃列表。因此，这意味着 zip 树最终需要看起来与我们添加然后删除元素后的初始状态相同。
\n要了解如何执行此操作，我们需要执行两个步骤：
\n- \n
- 撤消解压缩操作，将形成的两条节点链重新转换为线性节点链。 \n
- 撤消蓝色边缘的中断，恢复 x 的插入点。 \n
让我们从如何撤消解压缩操作开始。幸运的是，这还不算太糟糕。当我们将 x 插入 zip 树时，我们可以相当容易地识别通过解压缩操作创建的节点链 - 我们只需查看 x 的左子节点和右子节点，然后分别纯粹向左移动和纯粹向左移动。正确的。
\n现在，我们知道这些节点曾经在一条链中链接在一起。我们将它们重新组装成什么顺序？举个例子，看看 zip 树的这一部分，我们要删除 53。53 左右两侧的链被突出显示：
\n
如果我们查看构成左右链的节点，我们会发现只有一种方法可以重新组装它们。重组链的最顶层节点必须是 67，因为它的排名为 3，并且排名高于所有其他项目。之后，下一个节点必须是 41，因为它是 2 级元素中较小的一个，并且具有相同等级的元素在顶部具有较小的项目。通过重复这个过程，我们可以简单地使用 zip 树的结构规则来重建节点链，如下所示：
\n
这种将两条链交错为一条链的操作称为zipping。
\n总而言之，删除的工作原理如下：
\n\n\n从 zip 树中删除节点 x 的工作原理如下：
\n\n
\n- 找到树中的节点 x。
\n- 对其左右子树执行压缩。具体来说：\n
\n\n
\n- 维护“lhs”和“rhs”指针，最初指向左子树和右子树。
\n- 虽然这两个指针都不为空：\n3. 如果 lhs 的等级比 rhs 更高，则将 lhs 的右孩子设为 rhs，然后将 lhs 前进到曾经是 lhs 的右孩子的位置。\n4. 否则，使 rhs 的左子节点成为 lhs，然后将 rhs 前进以指向曾经是 rhs 的左子节点。
\n- 重新连接 x 的父级以指向 zip 操作的结果而不是 x。
\n
更多探索
\n回顾一下我们的要点：我们了解了如何使用排名的思想将跳表表示为 BST。这就产生了 zip 树，它使用排名规则来确定父/子关系。这些规则是使用 zip 和 unzip 操作来维护的，因此得名。
\n对 zip 列表进行全面分析基本上是通过类比推理来完成的。例如，我们可以通过指向等效的跳表并注意到等效操作的时间复杂度为 O(log n) 来证明插入或删除的预期运行时间为 O(log n)。我们可以类似地证明，这些不仅仅是预期的时间界限，而且是很有可能发生的预期时间界限。
\n存在一个问题：如何实际存储维护 zip 树所需的信息。一种选择是简单地将每个项目的排名写在节点本身中。这是可行的，但由于几何随机变量的性质，排名不太可能超过 O(log n)，这会浪费大量空间。另一种选择是在节点地址上使用哈希函数来生成某个范围内的随机、均匀分布的整数，然后找到最低有效 1 位的位置来模拟我们的硬币抛掷。由于计算哈希码的开销，这增加了插入和删除的成本，但也减少了空间使用。
\nZip 树并不是第一个将跳跃列表和 BST 映射在一起的数据结构。Dean 和 Jones 在 2007 年对这一想法提出了另一种表达方式。还有另一种方法可以利用这种联系。在这里，我们从随机跳跃列表开始，并用它来导出随机BST。但我们也可以反向运行 - 我们可以从确定性平衡 BST 开始，并使用它来导出确定性跳跃列表。Munro、Papadakis 和 Sedgewick 找到了一种通过连接 2-3-4 树和跳跃列表来实现此目的的方法。
\nzip 树并不是唯一的随机平衡 BST。陷阱是第一个做到这一点的结构，通过一点数学，你可以证明陷阱的预期高度往往比拉链树稍低。然而，权衡是每个节点需要比 zip 树更多的随机位。（然而，在 2023 年，\xe2\x80\x9czip zip 树\xe2\x80\x9d 被发明，每个节点仅使用 O(log log n) 位，并与 treap 的高度边界匹配。）
\n希望这可以帮助！
\n