保持有效的订购，您可以在订购中“之间”插入其他两个元素？

Question

想象一下，我对这样的元素进行了订购：

箭头$ x leftarrow y $表示$ x <y $。它也是传递的：$ left（x <y right） wedge left（y <z right） nimn Ingrive left（x <z right）$。

为了有效地回答$ a stackrel {？} {<} d $之类的查询，需要某种标签或数据结构。例如，您可以从左到右编号节点，因此您可以简单地进行整数比较即可回答查询：$ a stackrel {？} {？} {<} d nime 1 <4 含义为t $。看起来像这样：

数字是订购的地方，字母只是一个名称。

但是，如果您需要在订购中的其他两个元素之间插入元素，例如：

您如何保持这样的订单？使用简单的编号，您会遇到一个问题，即在“ $ 2,3 $之间”使用整数。

Answer 1

这被称为 “订单维护”问题. 。有一个相对简单的解决方案，使用$ O（1）$摊销时间用于查询和插入。现在，通过“相对简单”，我的意思是您必须了解一些构建块，但是一旦得到这些构建块，其余的就不难看到。

http://courses.csail.mit.edu/6.851/spring12/lectures/l08.html

基本思想是两级数据结构。顶级就像Realz Slaw的AVL树解决方案一样，但是

• 节点直接标记为长度$ o（ lg n）$的位字符串，并带有与他们在树中的订单相匹配的订单。因此比较需要恒定时间

• 旋转比AVL树少的树被使用，例如替罪羊树或重量平衡的树，因此重新标记发生的频率较低。

底部是树的叶子。该级别使用相同长度的标签，$ o（ lg n）$，但在简单的链接列表中仅保留$ o（ lg n）$项目。这为您提供了足够的额外位置，可以积极地重新标记。

叶子每$ o（ lg n）$插入太小或太小）。摊销，这仅是$ o（1）$。

在$ O（1）$最差的时间内执行更新的情况更为复杂。

Answer 2

与其简单的编号，您可以将数字传播到大型（恒定尺寸）范围内，例如CPU整数的整数最小值和最大值。然后，您可以通过平均两个周围的数字来继续将数字“介于两者之间”。如果这些数字变得太拥挤（例如，您最终会有两个相邻的整数，而两者之间没有数字），则可以对整个订购进行一次重新分配，从而在整个范围内均匀地重新分布数字。

当然，您可以遇到一个限制，即使用大常数范围内的所有数字。首先，这不是通常的问题，因为机器上的整数大小足够大，因此，如果您有更多的元素，则可能不适合记忆。但是，如果这是一个问题，您可以简单地用更大的整数范围恢复它们。

如果输入顺序不是病理性的，则此方法可能会摊销重量。

回答查询

一个简单的整数比较可以回答查询$ left（x stackrel {？} {<} y right）$。

如果使用机器整数，则查询时间将非常快（$ MATHCAL {O} left（1 右）$），因为这是一个简单的整数比较。使用较大的范围将需要较大的整数，并且比较将采用$ Mathcal {o} left（ log {| integer |} right）$。

插入

首先，您将维护问题中证明的订购的链接列表。在此处插入，给定将新元素放入之间的节点为$ Mathcal {o} left（1 右）$。

标记新元素通常是快速的$ MATHCAL {O} left（1 右）$，因为您可以通过平均周围的数字轻松地计算新的数字。有时，您可能会用完“之间”的数字，这会触发$ Mathcal {o} left（n 右）$ time renumbering Procedion。

避免重新编织

您可以使用浮子而不是整数，因此，当您获得两个“相邻”整数时，它们 能够 平均。因此，当面对两个整数浮子时，您可以避免重新登录：只需将它们分成一半即可。但是，最终，浮点类型的精度将用尽，并且两个“ adcent”浮子将无法平均（周围数字的平均值可能等于周围数字之一）。

您可以同样使用“小数点”整数，在该整数中维护两个整数；一个用于该数字，一个用于小数。这样，您可以避免重新登录。但是，十进制整数最终将溢出。

使用每个标签的整数或钻头列表可以完全避免重新列出；这基本上等同于使用无限长度的十进制数字。比较将在词典上进行，并且比较时间将增加到所涉及的列表的长度。但是，这可能会使标签不平衡。有些标签可能只需要一个整数（没有小数），而另一些标签可能具有长长的列表（长小数）。这是一个问题，重新编号也可以在这里有所帮助，通过将编号（此处的数字列表）均匀地分布在所选范围内（此处可能意味着列表的长度），以便在此类重新编号之后，列表都是相同的长度。

---

实际上，此方法实际上是在 该算法 (执行,相关数据结构）；在算法过程中，必须保留任意排序，作者使用整数和重新编号来实现这一目标。

---

试图坚持数字会使您的关键空间有些限制。可以使用比较逻辑“仍然有两个问题要解决。

Answer 3

您可以维护无钥匙的AVL树或类似的AVL树。

它的工作如下：这棵树像正常的AVL树一样在节点上保持订购，但与其确定节点“应该”的位置，没有键，没有键，您必须在何处插入键，并且您必须在“之后”明确插入节点。 “两个节点”之间的“另一个节点（或换句话说”），其中“之后”意味着它在树上的顺序遍历中出现。因此，由于AVL的内置旋转，树将自然地维护您的订购，并且它也将平衡。这将使所有内容保持均匀分布。

插入

如问题所示，除了定期插入列表外，您还将维护一个单独的AVL树。插入列表本身为$ Mathcal {o} left（1 右）$，因为您的“之前”和“ after”节点。

插入到树上的时间为$ Mathcal {o} left（ log {n} right）$，与插入AVL树相同。插入涉及对您要插入的节点的引用，然后您只需将新节点插入右子节点的最左节点的左侧即可。该位置在树的顺序中是“下一个”（它是在订购遍历中的下一个）。然后进行典型的AVL旋转以重新平衡树。您可以对“插入”进行类似的操作；当您需要将某些内容插入列表的开头并且没有节点“之前”节点时，这将很有帮助。

回答查询

要回答$ left的查询（x stackrel {？} {<} y right）$，您只需在树上找到$ x $和$ y $的所有祖先，然后分析在其中的位置树祖先分歧；与“左”分歧的一个是两者中的较小者。

此过程采用$ Mathcal {O} left（ log {n} right）$时间将树爬上根并获得祖先列表。虽然这似乎比整数比较慢，但事实是，这是一样的。只有在CPU上进行的整数比较才由一个大常数界限，以使其$ Mathcal {O} left（1 right）$;如果溢出此常数，则必须维护多个整数（$ MATHCAL {O} left（ log {n} right）$ Integers）并执行相同的$ Mathcal {o} left（ log { log { n} right）$比较。另外，您可以按恒定数量“绑定”树高，而“作弊”就像机器在整数上一样：现在查询$ Mathcal {o} left（1 右）$。

插入操作演示

为了证明，您可以在问题中从列表中插入一些元素：

步骤1

从$ d $开始

列表：

树：

第2步

插入$ c $，$ emptyset <c <d $。

列表：

树：

请注意，您明确地将$ c $“在” $ d $之前放置，不是因为字母C在d之前，而是因为列表中的$ c <d $。

步骤3

插入$ a $，$ emptyset <a <c $。

列表：

树：

AVL旋转：

第4步

插入$ b $，$ a <b <c $。

列表：

树：

无需旋转。

步骤5

插入$ e $，$ d <e < emptyset $

列表：

树：

步骤6

插入$ f $，$ b <f <c $

我们只是简单地将其附加到$ b $的权利中，我们只是将其正确地“在” $ b $中。因此，$ f $现在是在$ b $的订购遍历之后。

列表：

树：

AVL旋转：

比较操作演示

$ a stackrel {？} {<} f $

ancestors(A) = [C,B]
ancestors(F) = [C,B]
last_common_ancestor = B
B.left = A
B.right = F
... A < F #left is less than right

$ d stackrel {？} {<} f $

ancestors(D) = [C]
ancestors(F) = [C,B]
last_common_ancestor = C
C.left = D
C.right = B #next ancestor for F is to the right
... D < F #left is less than right

$ b stackrel {？} {<} a $

ancestors(B) = [C]
ancestors(A) = [B,C]
last_common_ancestor = B
B.left = A
... A < B #left is always less than parent

---

图源

• gist.github.com/realazthat/9299877A83CBA4720AEC