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

enter image description here

箭头$ 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 $。看起来像这样:

enter image description here

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

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

enter image description here

enter image description here

enter image description here

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

有帮助吗?

解决方案

这被称为 “订单维护”问题. 。有一个相对简单的解决方案,使用$ 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)$最差的时间内执行更新的情况更为复杂。

其他提示

与其简单的编号,您可以将数字传播到大型(恒定尺寸)范围内,例如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”浮子将无法平均(周围数字的平均值可能等于周围数字之一)。

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

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


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


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

您可以维护无钥匙的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 $开始

列表:

list step 1

树:

tree step 1

第2步

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

列表:

list step 2

树:

tree step 2

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

步骤3

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

列表:

list step 3

树:

tree step 3 before rotation

AVL旋转:

tree step 3 after rotation

第4步

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

列表:

list step 4

树:

tree step 4

无需旋转。

步骤5

插入$ e $,$ d <e < emptyset $

列表:

list step 5

树:

tree step 5

步骤6

插入$ f $,$ b <f <c $

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

列表:

list step 6

树:

tree step 6 before rotation

AVL旋转:

tree step 6 after rotation

比较操作演示

$ 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

图源

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top