什么是压缩树，它是如何工作的？
What is a zip tree, and how does it work?
我听说过一种新的平衡 BST 数据结构，称为 zip tree。什么是拉链树？它是如何工作的？
在高层次上，zip 树是
- 随机平衡二叉搜索树，
- 这是一种将跳过列表编码为 BST 的方法，并且
- 使用一对称为 zipping 和 unzipping 的操作而不是树旋转。
第一个要点——zip 树是随机的、平衡的 BST——给人一种 zip 树在高层次上实现的感觉。它是一种平衡的二叉搜索树，与 treaps 但不像 red/black 树一样，它使用随机化来平衡树。从这个意义上说，zip 树并不能保证是平衡树，而是有很高的平衡概率。
第二个要点——zip 树是 skiplists 的编码——显示了 zip 树从何而来，以及为什么直觉上它们是平衡的。您可以将 zip 树视为采用随机跳过列表数据结构的一种方式，它支持预期时间 O(log n) 内的所有主要操作，并将其表示为二叉搜索树。这提供了关于 zip 树从何而来以及为什么我们期望它们如此之快的直觉。
第三个要点 - zip 树使用 zipping 和 unzipping 而不是树旋转 - 说明了 zip 树的名称和编写代码是什么感觉。 Zip 树与其他类型的平衡树（例如，red/black 树或 AVL 树）的不同之处在于，节点不是通过旋转而是通过一对操作在树周围移动，将较大的节点链转换为两个较小的节点链链或 vice-versa.
此答案的其余部分更深入地探讨了 zip 树的来源、它们的工作原理以及它们的结构。
回顾：跳过列表
要了解 zip 树从何而来，让我们先回顾一下另一种数据结构，即跳表。 skiplist 是一种数据结构，类似于二叉搜索树，按排序顺序存储元素集合。但是，跳过列表不是树结构。相反，跳过列表通过多层 linked 列表按排序顺序存储元素。此处显示了示例跳过列表：
如您所见，元素按排序顺序表示。每个元素都有一个关联的 height，并且是多个 linked 列表的一部分，等于它的高度。 skiplist 的所有元素都参与底层。理想情况下，大约一半的节点将位于其上方的层中，大约四分之一的节点将位于其上方的层中，大约八分之一的节点将位于其上方的层中，等等。（更多关于这稍后工作。）
要在跳过列表中进行查找，我们从最顶层开始。我们在跳过列表中向前走，直到 (1) 找到我们正在寻找的元素，(2) 找到比我们正在寻找的元素更大的元素，或者 (3) 我们到达列表的末尾。在第一种情况下，我们打开香槟庆祝，因为我们发现了我们正在寻找的物品，没有什么可做的了。在第二种情况或第三种情况下，我们 "overshot" 我们正在寻找的元素。但这没什么好担心的——事实上，这很有用，因为这意味着我们要查找的内容必须在我们命中 "overshot" 的节点和它之前的节点之间。所以我们将转到上一个节点，向下一层，然后从那里开始我们的搜索。
例如，下面是我们搜索 47 的方式：
此处，蓝色边缘表示我们向前移动的 link 秒，红色边缘表示我们超越并决定下降一层的位置。
跳过列表如何工作的一个强大的直觉——我们稍后在过渡到 zip 树时将需要它——是跳过列表的最顶层将跳过列表的其余元素划分到不同的范围。你可以在这里看到：
直觉上，如果我们能够跳过查看大多数元素，则跳过列表搜索将是 "fast"。想象一下，例如，skiplist 的 second-to-last 层仅存储 skiplist 的所有其他元素。在这种情况下，遍历 second-to-last 层的速度是遍历底层的两倍，因此我们预计从 second-to-last 层开始的查找花费的时间是从 second-to-last 层开始的查找所花时间的一半底层。同样，假设该层之上的层仅存储其下层的所有其他元素。然后在 that 层中搜索将花费大约一半的时间来搜索它下面的层。更一般地说，如果每一层只存储其下层的大约一半元素，那么我们可以在搜索过程中跳过跳过列表中的大量元素，从而获得良好的性能。
skiplist 通过使用以下规则完成此操作：每当我们将一个元素插入 ski列表，我们掷硬币直到正面朝上。然后我们将 newly-inserted 节点的高度设置为我们最终抛出的硬币数。这意味着它有 50% 的机会留在当前层，有 50% 的机会移动到它上面的层，这意味着，总的来说，大约一半的节点将只在底层，大约一半的节点左边会在上面一层，剩下的大约一半会在上面一层，等等
（对于有数学背景的同学，也可以说skiplist中每个节点的高度是一个Geom(1/2)随机变量。）
下面是一个使用高度 1 将 42 插入到上面显示的跳过列表中的示例：
从跳过列表中删除也是一个相当简单的操作：我们只需将它从它恰好所在的 linked 列表中拼接出来。这意味着如果我们要删除我们刚刚插入的 42上面的列表，我们最终会得到与开始时相同的跳过列表。
可以证明，在跳表中插入、删除或查找的预期成本是 O(log n)，基于每个列表中的项目数大约是项目数的一半这一事实在它下面的那个。 （这意味着我们希望看到 O(log n) 层，并且在每一层中只采取恒定数量的步骤。）
从跳过列表到压缩树
既然我们已经回顾了跳过列表，让我们来谈谈 zip 树的来源。
假设您正在查看跳过列表数据结构。您真的很喜欢每个操作的预期 O(log n) 性能，并且您喜欢它在概念上的简单性。只有一个问题 - 你 真的 不喜欢 linked 列表，并且用一层又一层的 linked 列表构建东西的想法并不让你兴奋。另一方面，您 真的 喜欢二叉搜索树。他们有一个非常简单的结构——每个节点只有两个指针离开它，并且有一个关于所有东西放置位置的简单规则。那么这个问题自然而然地出现了：除了 BST 形式，你能得到跳过列表的所有好处吗？
事实证明，有一种非常好的方法可以做到这一点。假设您有此处显示的跳过列表：
现在，假设您在此跳过列表中执行查找。该搜索将如何工作？好吧，你总是从扫描跳过列表的顶层开始，向前移动直到你找到一个比你要找的那个大的键，或者直到你到达列表的末尾并发现没有顶层有更多节点。从那里，你然后 "descend" 一级进入 sub-skiplist 只包含你访问的最后一个节点和超出的节点之间的键。
可以将此完全相同的搜索建模为 BST 遍历。具体来说，下面是我们如何将跳过列表的顶层表示为 BST：
注意所有这些节点都向右链接，其想法是 "scanning forward in the skiplist" 对应于 "visiting larger and larger keys." 在 BST 中，从一个节点移动到更大的节点对应于向右移动，因此右边的节点链。
现在，BST 中的每个节点最多可以有两个 children，在上图中每个节点有 0 个 children 或一个 child。如果我们通过标记它们对应的范围来填充缺失的 children，我们得到这个。
嘿，等一下！看起来 BST 确实以与 skiplist 相同的方式对键的 space 进行分区。这是有希望的，因为它表明我们在这里有所作为。另外，它为我们提供了一种填充树的其余部分的方法：我们可以递归地将跳过列表的子范围转换为它们自己的 BST，并将整个东西粘合在一起。如果我们这样做，我们将得到这棵编码跳过列表的树：
我们现在有一种将跳过列表表示为二叉搜索树的方法。很酷！
现在，我们可以反过来吗？也就是说，我们可以从 BST 转到跳表吗？一般来说，没有一种独特的方法可以做到这一点。毕竟，当我们将 skiplist 转换为 BST 时，我们确实丢失了一些信息。具体来说，skiplist 中的每个节点都有一个关联的高度，虽然我们 BST 中的每个节点也有一个高度，但它与 skiplist 节点的高度没有紧密联系。为了解决这个问题，让我们用它来自的跳过列表节点的高度来标记每个 BST 节点。此处显示：
现在，出现了一些不错的模式。对于初学者，请注意 每个节点的关联编号大于其左侧 child 的编号 。这是有道理的，因为向左的每一步都对应于下降到跳表的子范围，其中节点的高度较低。同理，每个节点的关联数大于等于numb右边的 r child. 这又是有道理的 - 向右移动要么意味着
- 在我们已经所在的同一高度继续前进，在这种情况下高度保持不变，或者
- 到达范围的末尾并下降到子范围，在这种情况下高度会降低。
我们能多说说树的形状吗？我们当然可以！例如，在跳表中，每个节点的高度是通过掷硬币直到我们得到正面，然后计算我们掷了多少硬币来选择的。 （或者，和以前一样，它以 1/2 的概率呈几何分布）。因此，如果我们想象构建一个对应于跳过列表的 BST，我们希望分配给节点的数字以相同的方式计算。
将这三个规则放在一起，我们得到以下内容，它定义了我们树的形状，zip 树！
A zip tree is a binary search tree where
- Each node has an associated number called its rank. Ranks are assigned randomly to each node by flipping coins until heads is flipped, then counting how many total coins were tossed.
- Each node's rank is strictly greater than its left child's rank.
- Each node's rank is greater than or equal to its right child's rank.
通过写出如此简单的规则，像跳过列表这样的东西可以表示为 BST，真是太神奇了！
插入元素：解压缩
假设您有一个 zip 树。您将如何向其中插入新元素？
我们原则上可以通过纯粹查看上面给出的规则来回答这个问题，但我认为通过记住 zip 树是变相的跳过列表来弄清楚这个问题要容易得多.例如，这是上面的 zip 树及其关联的跳过列表：
现在，假设我们要将 18 插入到这个 zip 树中。为了解结果如何，假设我们决定将 18 的等级设为 2。让我们不看 zip 树，而是看一下如果我们向跳过列表中插入会发生什么。这将产生这个跳过列表：
如果我们采用此跳过列表并将其编码为 zip 树，我们将得到以下结果：
有趣的是，即使我们不知道如何执行插入，我们也可以看到插入后树的样子。然后我们可以尝试通过 reverse-engineering 从这些 "before" 和 "after" 图片中找出插入逻辑需要是什么样子。
让我们想想这个插入对我们的 zip 树做了什么改变。首先，让我们回想一下我们如何将跳过列表编码为压缩树的直觉。具体来说，没有中间 "higher" 元素的跳过列表中同一级别的节点链映射到向右倾斜的 zip 树中的节点链。向跳过列表中插入一个元素对应于将一些新元素添加到其中一个级别中，其效果是（1）将新元素添加到跳过列表的某个级别中，以及（2）在跳过列表中获取之前的元素链在某种程度上是相邻的，然后断开了这些连接。
例如，当我们将 18 插入此处显示的跳过列表时，我们向此处突出显示的蓝色链中添加了一些新内容，并且我们打破了此处显示的所有红色链：
这将在我们的 zip 树中转换成什么？好吧，我们可以突出显示此处插入项目的蓝色 link，以及被剪切的红色 link：
让我们看看能不能弄清楚这里发生了什么。幸运的是，这里的蓝色 link 很容易找到。想象一下，我们进行常规 BST 插入以将 18 添加到我们的树中。当我们这样做时，我们将在到达这一点时暂停：
请注意，我们按了与我们相同等级的键。这意味着，如果我们继续向右移动，我们将追踪到跳过列表的这个区域：
要找到蓝色边缘——我们要去的地方——我们只需要沿着这个节点链向下走，直到找到一个比我们大的节点。蓝色边 - 我们的插入点 - 然后由该节点与其上方的节点之间的边给出。
我们可以用不同的方式识别这个位置：我们找到了蓝色边缘 - 我们的插入点 - 当我们到达要插入的节点 (1) 比要插入的节点具有更大等级的点时左侧，(2) 的等级大于或等于右侧的节点，并且 (3) 如果右侧的节点具有相同的等级，我们要插入的新项目小于右侧的项目。前两条规则确保我们插入到跳过列表的正确级别，最后一条规则确保我们插入到跳过列表该级别的正确位置。
现在，我们的红色边缘在哪里？直观地说，这些是 "cut" 的边，因为 18 已添加到跳过列表中。这些将是以前位于蓝色边缘相对两端的两个节点之间的项目，但是需要将哪个节点划分到由该蓝色边缘的拆分版本定义的新范围中。
幸运的是，这些边缘出现在非常好的地方。这里他们映射到的位置：
（在这张图片中，我将新节点 18 放置在我们在跳过列表中识别的蓝色边缘的中间。这导致结果不再是 BST，但我们将在分钟。)
请注意，如果我们完成常规 BST 插入，这些边与我们遇到的边完全相同 - 这是通过查找 18 追踪出的路径！这里发生了一些非常好的事情。请注意
- 每次向右移动，节点在切开的时候，都在18的右边，
- 每次我们向左移动时，节点在切割时会转到18的左侧。
换句话说，一旦我们找到插入的蓝色边缘，我们就会继续走，就好像我们像往常一样进行插入，跟踪我们向左走的节点和向右走的节点。然后我们可以将我们向左走的所有节点链接在一起，并将我们向右走的所有节点链接在一起，将结果粘合在我们的新节点下。此处显示：
这个操作叫做unzipping，这就是我们得到名字"zip tree"的地方。这个名字有点意思——我们采用两个交错结构（左链和右链）并将它们分成两个更简单的线性链。
总结：
Inserting x into a zip tree works as follows:
- Assign a random rank to x by flipping coins and counting how many flips were needed to get heads.
- Do a search for x. Stop the search once you reach a node where
- the node's left child has a lower rank than x,
- the node's right child has a rank less than or equal to x, and
- the node's right child, if it has the same rank as x, has a larger key than x.
- Perform a unzip. Specifically:
- Continue the search for x as before, recording when we move left and when we move right.
- Chain all the nodes together where we went left by making each the left child of the previously-visited left-moving node.
- Chain all the nodes together where we went right by making each the right child of the previously-visited right-moving node.
- Make those two chains the children of the node x.
您可能会注意到，此 "unzipping" 过程与您执行不同操作时得到的结果相同。您可以通过像往常一样插入 x 来获得相同的结果，然后使用树旋转将树中的 x 拉得越来越高，直到它停在正确的位置。这是进行插入的完全有效的替代策略，尽管它有点慢，因为需要在树上进行两次遍历（top-down 遍历以在叶子处插入，然后 bottom-up 遍历以进行旋转).
删除元素：压缩
既然我们已经了解了如何插入元素，那么我们如何删除它们呢？
让我们从一个有用的观察开始：如果我们将一个项目插入一个 zip 树然后删除它，我们最终应该得到与我们开始时完全相同的树。要了解这是为什么，我们可以返回一个跳过列表。如果您添加然后从跳过列表中删除某些内容，那么您最终会得到与之前相同的跳过列表。因此，这意味着 zip 树需要最终看起来与我们添加然后删除元素后的开始方式相同。
要了解如何执行此操作，我们需要执行两个步骤：
- 撤销解压缩操作，将形成的两个节点链转换回线性节点链。
- 取消蓝边的打断，恢复x的插入点。
让我们从如何撤消解压缩操作开始。幸运的是，这还不算太糟糕。当我们将 x 插入 zip 树时，我们可以很容易地识别我们通过解压缩操作创建的节点链 - 我们只需查看 x 的左右 children，然后分别移动到纯粹的向左，完全向右。
现在，我们知道这些节点曾经 link 在一条链中连接在一起。我们将它们重新组合成什么顺序？例如，看一下 zip 树的这一部分，我们要在其中删除 53。突出显示 53 左右两侧的链：
如果我们查看组成左链和右链的节点，我们会发现只有一种方法可以重新组装它们。重组链的最顶端节点必须是 67，因为它的等级为 3 并且将超过所有其他项目。在那之后，下一个节点必须是 41，因为它是 rank-2 元素中较小的一个，并且具有相同 rank 的元素在顶部有较小的项目。通过重复这个过程，我们可以重建节点链，如下所示，只需使用 zip 树的结构规则：
这种将两条链交织成一条链的操作称为 zipping.
总而言之，删除的工作原理如下：
Deleting a node x from a zip tree works as follows:
- Find the node x in the tree.
- Perform a zip of its left and right subtrees. Specifically:
- Maintain "lhs" and "rhs" pointers, initially to the left and right subtrees.
- While both those pointers aren't null:
- If lhs has a higher rank than rhs, make lhs's right child rhs, then advance lhs to what used to be lhs's right child.
- Otherwise, make rhs's left child lhs, then advance rhs to point to what used to be rhs's left child.
- Rewire x's parent to point to the result of the zip operation rather than x.
探索更多内容
回顾一下我们的要点：我们看到了如何使用秩的概念将跳过列表表示为 BST。这就产生了 zip 树，它使用排名规则来确定 parent/child 关系。这些规则是使用 zip 和 unzip 操作维护的，因此得名。
对 zip 列表进行全面分析基本上是通过对 skiplist 进行类比推理来完成的。例如，我们可以通过指向等效的跳表并注意到等效操作的时间复杂度为 O(log n) 来证明插入或删除的预期 运行 时间为 O(log n) .我们可以类似地证明这些不仅仅是预期的时间范围，而且是很有可能发生的预期时间范围。
有一个问题如何实际存储维护 zip 树所需的信息。一种选择是简单地将每个项目的等级写在节点本身中。这是可行的，尽管由于几何随机变量的性质，秩不太可能超过 O(log n)，这会浪费很多 space。另一种方法是在节点地址上使用哈希函数来生成一个随机的 uniformly-distributed 某个范围内的整数，然后找到最 least-significant 1 位的位置来模拟我们的抛硬币。由于计算哈希码的开销，这增加了插入和删除的成本，但也减少了 space 的使用。
Zip 树并不是第一个将跳过列表和 BST 映射在一起的数据结构。 Dean 和 Jones 在 2007 年提出了这个想法的另一种表达方式。还有另一种方法可以利用这种联系。在这里，我们从 randomized skiplist 开始，并用它来导出 randomized BST。但是我们也可以 运行 反过来 - 我们可以从 deterministic 平衡 BST 开始，然后用它来导出 deterministic skiplist . Munro、Papadakis 和 Sedgewick 找到了一种通过连接 2-3-4 树和跳表来做到这一点的方法。
zip 树并不是唯一的随机平衡 BST。 treap 是第一个这样做的结构，通过一点数学你可以证明 treap 的预期高度往往比 zip 树略低。不过，需要权衡的是，与 zip 树相比，每个节点需要更多的随机位。
希望对您有所帮助！
我听说过一种新的平衡 BST 数据结构，称为 zip tree。什么是拉链树？它是如何工作的？
在高层次上，zip 树是
- 随机平衡二叉搜索树，
- 这是一种将跳过列表编码为 BST 的方法，并且
- 使用一对称为 zipping 和 unzipping 的操作而不是树旋转。
第一个要点——zip 树是随机的、平衡的 BST——给人一种 zip 树在高层次上实现的感觉。它是一种平衡的二叉搜索树，与 treaps 但不像 red/black 树一样，它使用随机化来平衡树。从这个意义上说，zip 树并不能保证是平衡树，而是有很高的平衡概率。
第二个要点——zip 树是 skiplists 的编码——显示了 zip 树从何而来，以及为什么直觉上它们是平衡的。您可以将 zip 树视为采用随机跳过列表数据结构的一种方式，它支持预期时间 O(log n) 内的所有主要操作，并将其表示为二叉搜索树。这提供了关于 zip 树从何而来以及为什么我们期望它们如此之快的直觉。
第三个要点 - zip 树使用 zipping 和 unzipping 而不是树旋转 - 说明了 zip 树的名称和编写代码是什么感觉。 Zip 树与其他类型的平衡树（例如，red/black 树或 AVL 树）的不同之处在于，节点不是通过旋转而是通过一对操作在树周围移动，将较大的节点链转换为两个较小的节点链链或 vice-versa.
此答案的其余部分更深入地探讨了 zip 树的来源、它们的工作原理以及它们的结构。
回顾：跳过列表
要了解 zip 树从何而来，让我们先回顾一下另一种数据结构，即跳表。 skiplist 是一种数据结构，类似于二叉搜索树，按排序顺序存储元素集合。但是，跳过列表不是树结构。相反，跳过列表通过多层 linked 列表按排序顺序存储元素。此处显示了示例跳过列表：
如您所见，元素按排序顺序表示。每个元素都有一个关联的 height，并且是多个 linked 列表的一部分，等于它的高度。 skiplist 的所有元素都参与底层。理想情况下，大约一半的节点将位于其上方的层中，大约四分之一的节点将位于其上方的层中，大约八分之一的节点将位于其上方的层中，等等。（更多关于这稍后工作。）
要在跳过列表中进行查找，我们从最顶层开始。我们在跳过列表中向前走，直到 (1) 找到我们正在寻找的元素，(2) 找到比我们正在寻找的元素更大的元素，或者 (3) 我们到达列表的末尾。在第一种情况下，我们打开香槟庆祝，因为我们发现了我们正在寻找的物品，没有什么可做的了。在第二种情况或第三种情况下，我们 "overshot" 我们正在寻找的元素。但这没什么好担心的——事实上，这很有用，因为这意味着我们要查找的内容必须在我们命中 "overshot" 的节点和它之前的节点之间。所以我们将转到上一个节点，向下一层，然后从那里开始我们的搜索。
例如，下面是我们搜索 47 的方式：
此处，蓝色边缘表示我们向前移动的 link 秒，红色边缘表示我们超越并决定下降一层的位置。
跳过列表如何工作的一个强大的直觉——我们稍后在过渡到 zip 树时将需要它——是跳过列表的最顶层将跳过列表的其余元素划分到不同的范围。你可以在这里看到：
直觉上，如果我们能够跳过查看大多数元素，则跳过列表搜索将是 "fast"。想象一下，例如，skiplist 的 second-to-last 层仅存储 skiplist 的所有其他元素。在这种情况下，遍历 second-to-last 层的速度是遍历底层的两倍，因此我们预计从 second-to-last 层开始的查找花费的时间是从 second-to-last 层开始的查找所花时间的一半底层。同样，假设该层之上的层仅存储其下层的所有其他元素。然后在 that 层中搜索将花费大约一半的时间来搜索它下面的层。更一般地说，如果每一层只存储其下层的大约一半元素，那么我们可以在搜索过程中跳过跳过列表中的大量元素，从而获得良好的性能。
skiplist 通过使用以下规则完成此操作：每当我们将一个元素插入 ski列表，我们掷硬币直到正面朝上。然后我们将 newly-inserted 节点的高度设置为我们最终抛出的硬币数。这意味着它有 50% 的机会留在当前层，有 50% 的机会移动到它上面的层，这意味着，总的来说，大约一半的节点将只在底层，大约一半的节点左边会在上面一层，剩下的大约一半会在上面一层，等等
（对于有数学背景的同学，也可以说skiplist中每个节点的高度是一个Geom(1/2)随机变量。）
下面是一个使用高度 1 将 42 插入到上面显示的跳过列表中的示例：
从跳过列表中删除也是一个相当简单的操作：我们只需将它从它恰好所在的 linked 列表中拼接出来。这意味着如果我们要删除我们刚刚插入的 42上面的列表，我们最终会得到与开始时相同的跳过列表。
可以证明，在跳表中插入、删除或查找的预期成本是 O(log n)，基于每个列表中的项目数大约是项目数的一半这一事实在它下面的那个。 （这意味着我们希望看到 O(log n) 层，并且在每一层中只采取恒定数量的步骤。）
从跳过列表到压缩树
既然我们已经回顾了跳过列表，让我们来谈谈 zip 树的来源。
假设您正在查看跳过列表数据结构。您真的很喜欢每个操作的预期 O(log n) 性能，并且您喜欢它在概念上的简单性。只有一个问题 - 你 真的 不喜欢 linked 列表，并且用一层又一层的 linked 列表构建东西的想法并不让你兴奋。另一方面，您 真的 喜欢二叉搜索树。他们有一个非常简单的结构——每个节点只有两个指针离开它，并且有一个关于所有东西放置位置的简单规则。那么这个问题自然而然地出现了：除了 BST 形式，你能得到跳过列表的所有好处吗？
事实证明，有一种非常好的方法可以做到这一点。假设您有此处显示的跳过列表：
现在，假设您在此跳过列表中执行查找。该搜索将如何工作？好吧，你总是从扫描跳过列表的顶层开始，向前移动直到你找到一个比你要找的那个大的键，或者直到你到达列表的末尾并发现没有顶层有更多节点。从那里，你然后 "descend" 一级进入 sub-skiplist 只包含你访问的最后一个节点和超出的节点之间的键。
可以将此完全相同的搜索建模为 BST 遍历。具体来说，下面是我们如何将跳过列表的顶层表示为 BST：
注意所有这些节点都向右链接，其想法是 "scanning forward in the skiplist" 对应于 "visiting larger and larger keys." 在 BST 中，从一个节点移动到更大的节点对应于向右移动，因此右边的节点链。
现在，BST 中的每个节点最多可以有两个 children，在上图中每个节点有 0 个 children 或一个 child。如果我们通过标记它们对应的范围来填充缺失的 children，我们得到这个。
嘿，等一下！看起来 BST 确实以与 skiplist 相同的方式对键的 space 进行分区。这是有希望的，因为它表明我们在这里有所作为。另外，它为我们提供了一种填充树的其余部分的方法：我们可以递归地将跳过列表的子范围转换为它们自己的 BST，并将整个东西粘合在一起。如果我们这样做，我们将得到这棵编码跳过列表的树：
我们现在有一种将跳过列表表示为二叉搜索树的方法。很酷！
现在，我们可以反过来吗？也就是说，我们可以从 BST 转到跳表吗？一般来说，没有一种独特的方法可以做到这一点。毕竟，当我们将 skiplist 转换为 BST 时，我们确实丢失了一些信息。具体来说，skiplist 中的每个节点都有一个关联的高度，虽然我们 BST 中的每个节点也有一个高度，但它与 skiplist 节点的高度没有紧密联系。为了解决这个问题，让我们用它来自的跳过列表节点的高度来标记每个 BST 节点。此处显示：
现在，出现了一些不错的模式。对于初学者，请注意 每个节点的关联编号大于其左侧 child 的编号 。这是有道理的，因为向左的每一步都对应于下降到跳表的子范围，其中节点的高度较低。同理，每个节点的关联数大于等于numb右边的 r child. 这又是有道理的 - 向右移动要么意味着
- 在我们已经所在的同一高度继续前进，在这种情况下高度保持不变，或者
- 到达范围的末尾并下降到子范围，在这种情况下高度会降低。
我们能多说说树的形状吗？我们当然可以！例如，在跳表中，每个节点的高度是通过掷硬币直到我们得到正面，然后计算我们掷了多少硬币来选择的。 （或者，和以前一样，它以 1/2 的概率呈几何分布）。因此，如果我们想象构建一个对应于跳过列表的 BST，我们希望分配给节点的数字以相同的方式计算。
将这三个规则放在一起，我们得到以下内容，它定义了我们树的形状，zip 树！
A zip tree is a binary search tree where
- Each node has an associated number called its rank. Ranks are assigned randomly to each node by flipping coins until heads is flipped, then counting how many total coins were tossed.
- Each node's rank is strictly greater than its left child's rank.
- Each node's rank is greater than or equal to its right child's rank.
通过写出如此简单的规则，像跳过列表这样的东西可以表示为 BST，真是太神奇了！
插入元素：解压缩
假设您有一个 zip 树。您将如何向其中插入新元素？
我们原则上可以通过纯粹查看上面给出的规则来回答这个问题，但我认为通过记住 zip 树是变相的跳过列表来弄清楚这个问题要容易得多.例如，这是上面的 zip 树及其关联的跳过列表：
现在，假设我们要将 18 插入到这个 zip 树中。为了解结果如何，假设我们决定将 18 的等级设为 2。让我们不看 zip 树，而是看一下如果我们向跳过列表中插入会发生什么。这将产生这个跳过列表：
如果我们采用此跳过列表并将其编码为 zip 树，我们将得到以下结果：
有趣的是，即使我们不知道如何执行插入，我们也可以看到插入后树的样子。然后我们可以尝试通过 reverse-engineering 从这些 "before" 和 "after" 图片中找出插入逻辑需要是什么样子。
让我们想想这个插入对我们的 zip 树做了什么改变。首先，让我们回想一下我们如何将跳过列表编码为压缩树的直觉。具体来说，没有中间 "higher" 元素的跳过列表中同一级别的节点链映射到向右倾斜的 zip 树中的节点链。向跳过列表中插入一个元素对应于将一些新元素添加到其中一个级别中，其效果是（1）将新元素添加到跳过列表的某个级别中，以及（2）在跳过列表中获取之前的元素链在某种程度上是相邻的，然后断开了这些连接。
例如，当我们将 18 插入此处显示的跳过列表时，我们向此处突出显示的蓝色链中添加了一些新内容，并且我们打破了此处显示的所有红色链：
这将在我们的 zip 树中转换成什么？好吧，我们可以突出显示此处插入项目的蓝色 link，以及被剪切的红色 link：
让我们看看能不能弄清楚这里发生了什么。幸运的是，这里的蓝色 link 很容易找到。想象一下，我们进行常规 BST 插入以将 18 添加到我们的树中。当我们这样做时，我们将在到达这一点时暂停：
请注意，我们按了与我们相同等级的键。这意味着，如果我们继续向右移动，我们将追踪到跳过列表的这个区域：
要找到蓝色边缘——我们要去的地方——我们只需要沿着这个节点链向下走，直到找到一个比我们大的节点。蓝色边 - 我们的插入点 - 然后由该节点与其上方的节点之间的边给出。
我们可以用不同的方式识别这个位置：我们找到了蓝色边缘 - 我们的插入点 - 当我们到达要插入的节点 (1) 比要插入的节点具有更大等级的点时左侧，(2) 的等级大于或等于右侧的节点，并且 (3) 如果右侧的节点具有相同的等级，我们要插入的新项目小于右侧的项目。前两条规则确保我们插入到跳过列表的正确级别，最后一条规则确保我们插入到跳过列表该级别的正确位置。
现在，我们的红色边缘在哪里？直观地说，这些是 "cut" 的边，因为 18 已添加到跳过列表中。这些将是以前位于蓝色边缘相对两端的两个节点之间的项目，但是需要将哪个节点划分到由该蓝色边缘的拆分版本定义的新范围中。
幸运的是，这些边缘出现在非常好的地方。这里他们映射到的位置：
（在这张图片中，我将新节点 18 放置在我们在跳过列表中识别的蓝色边缘的中间。这导致结果不再是 BST，但我们将在分钟。)
请注意，如果我们完成常规 BST 插入，这些边与我们遇到的边完全相同 - 这是通过查找 18 追踪出的路径！这里发生了一些非常好的事情。请注意
- 每次向右移动，节点在切开的时候，都在18的右边，
- 每次我们向左移动时，节点在切割时会转到18的左侧。
换句话说，一旦我们找到插入的蓝色边缘，我们就会继续走，就好像我们像往常一样进行插入，跟踪我们向左走的节点和向右走的节点。然后我们可以将我们向左走的所有节点链接在一起，并将我们向右走的所有节点链接在一起，将结果粘合在我们的新节点下。此处显示：
这个操作叫做unzipping，这就是我们得到名字"zip tree"的地方。这个名字有点意思——我们采用两个交错结构（左链和右链）并将它们分成两个更简单的线性链。
总结：
Inserting x into a zip tree works as follows:
- Assign a random rank to x by flipping coins and counting how many flips were needed to get heads.
- Do a search for x. Stop the search once you reach a node where
- the node's left child has a lower rank than x,
- the node's right child has a rank less than or equal to x, and
- the node's right child, if it has the same rank as x, has a larger key than x.
- Perform a unzip. Specifically:
- Continue the search for x as before, recording when we move left and when we move right.
- Chain all the nodes together where we went left by making each the left child of the previously-visited left-moving node.
- Chain all the nodes together where we went right by making each the right child of the previously-visited right-moving node.
- Make those two chains the children of the node x.
您可能会注意到，此 "unzipping" 过程与您执行不同操作时得到的结果相同。您可以通过像往常一样插入 x 来获得相同的结果，然后使用树旋转将树中的 x 拉得越来越高，直到它停在正确的位置。这是进行插入的完全有效的替代策略，尽管它有点慢，因为需要在树上进行两次遍历（top-down 遍历以在叶子处插入，然后 bottom-up 遍历以进行旋转).
删除元素：压缩
既然我们已经了解了如何插入元素，那么我们如何删除它们呢？
让我们从一个有用的观察开始：如果我们将一个项目插入一个 zip 树然后删除它，我们最终应该得到与我们开始时完全相同的树。要了解这是为什么，我们可以返回一个跳过列表。如果您添加然后从跳过列表中删除某些内容，那么您最终会得到与之前相同的跳过列表。因此，这意味着 zip 树需要最终看起来与我们添加然后删除元素后的开始方式相同。
要了解如何执行此操作，我们需要执行两个步骤：
- 撤销解压缩操作，将形成的两个节点链转换回线性节点链。
- 取消蓝边的打断，恢复x的插入点。
让我们从如何撤消解压缩操作开始。幸运的是，这还不算太糟糕。当我们将 x 插入 zip 树时，我们可以很容易地识别我们通过解压缩操作创建的节点链 - 我们只需查看 x 的左右 children，然后分别移动到纯粹的向左，完全向右。
现在，我们知道这些节点曾经 link 在一条链中连接在一起。我们将它们重新组合成什么顺序？例如，看一下 zip 树的这一部分，我们要在其中删除 53。突出显示 53 左右两侧的链：
如果我们查看组成左链和右链的节点，我们会发现只有一种方法可以重新组装它们。重组链的最顶端节点必须是 67，因为它的等级为 3 并且将超过所有其他项目。在那之后，下一个节点必须是 41，因为它是 rank-2 元素中较小的一个，并且具有相同 rank 的元素在顶部有较小的项目。通过重复这个过程，我们可以重建节点链，如下所示，只需使用 zip 树的结构规则：
这种将两条链交织成一条链的操作称为 zipping.
总而言之，删除的工作原理如下：
Deleting a node x from a zip tree works as follows:
- Find the node x in the tree.
- Perform a zip of its left and right subtrees. Specifically:
- Maintain "lhs" and "rhs" pointers, initially to the left and right subtrees.
- While both those pointers aren't null:
- If lhs has a higher rank than rhs, make lhs's right child rhs, then advance lhs to what used to be lhs's right child.
- Otherwise, make rhs's left child lhs, then advance rhs to point to what used to be rhs's left child.
- Rewire x's parent to point to the result of the zip operation rather than x.
探索更多内容
回顾一下我们的要点：我们看到了如何使用秩的概念将跳过列表表示为 BST。这就产生了 zip 树，它使用排名规则来确定 parent/child 关系。这些规则是使用 zip 和 unzip 操作维护的，因此得名。
对 zip 列表进行全面分析基本上是通过对 skiplist 进行类比推理来完成的。例如，我们可以通过指向等效的跳表并注意到等效操作的时间复杂度为 O(log n) 来证明插入或删除的预期 运行 时间为 O(log n) .我们可以类似地证明这些不仅仅是预期的时间范围，而且是很有可能发生的预期时间范围。
有一个问题如何实际存储维护 zip 树所需的信息。一种选择是简单地将每个项目的等级写在节点本身中。这是可行的，尽管由于几何随机变量的性质，秩不太可能超过 O(log n)，这会浪费很多 space。另一种方法是在节点地址上使用哈希函数来生成一个随机的 uniformly-distributed 某个范围内的整数，然后找到最 least-significant 1 位的位置来模拟我们的抛硬币。由于计算哈希码的开销，这增加了插入和删除的成本，但也减少了 space 的使用。
Zip 树并不是第一个将跳过列表和 BST 映射在一起的数据结构。 Dean 和 Jones 在 2007 年提出了这个想法的另一种表达方式。还有另一种方法可以利用这种联系。在这里，我们从 randomized skiplist 开始，并用它来导出 randomized BST。但是我们也可以 运行 反过来 - 我们可以从 deterministic 平衡 BST 开始，然后用它来导出 deterministic skiplist . Munro、Papadakis 和 Sedgewick 找到了一种通过连接 2-3-4 树和跳表来做到这一点的方法。
zip 树并不是唯一的随机平衡 BST。 treap 是第一个这样做的结构，通过一点数学你可以证明 treap 的预期高度往往比 zip 树略低。不过，需要权衡的是，与 zip 树相比，每个节点需要更多的随机位。
希望对您有所帮助！