实现一个不可变的deque作为平衡二叉树?

正如Daniel所指出的,使用众所周知的平衡搜索树(如AVL树或红黑树)实现不可变的deques会使情况最复杂。Lippert讨论的一些实现乍一看似乎很详细,但有许多不可变的问题,其中O(lg n)最差,平均或分摊的复杂性是由平衡树和两个简单的想法构建的:

1. 倒转脊椎

   要在传统的平衡搜索树上执行deque操作,我们需要访问端点,但只能访问中心。为了到达左端,我们必须导航左子指针,直到最后到达死胡同。最好有一个指向左端和右端的指针,而不需要所有的导航工作。实际上,我们确实不需要经常访问根节点。让我们存储一个平衡的搜索树,以便访问端点为O(1)。

   下面是C中的一个示例,说明如何正常存储AVL树:

   struct AVLTree {
     const char * value;
     int height;
     struct AVLTree * leftChild;
     struct AVLTree * rightChild;
   };
   

   为了建立树以便我们可以从边缘开始并向根移动,我们更改树并沿从根到左和右的路径存储所有指针 颠倒 . (这些路径称为 左边 和 右脊柱 ,分别)。就像颠倒一个单独链接的列表一样,最后一个元素成为第一个元素,所以最左边的子元素现在很容易访问。

   这有点难理解。为了有助于解释,假设您只对左脊柱进行了此操作:

   struct LeftSpine {
     const char * value;
     int height;
     struct AVLTree * rightChild;
     struct LeftSpine * parent;
   };
   

   在某种意义上,最左边的孩子现在是树的“根”。如果你用这种方式画树,看起来会很奇怪,但是如果你只是简单地用正常的方式画一棵树,并反转左脊柱上的所有箭头,那么左脊柱结构的含义应该会变得更清楚。现在可以立即访问树的左侧。右脊柱也可以这样做:

   struct RightSpine {
     double value;
     int height;
     struct AVLTree * leftChild;
     struct RightSpine * parent;
   };
   

   如果同时存储左右脊椎和中心元素,则可以立即访问两端。插入和删除可能仍然是Ω(lg n),因为重新平衡操作可能需要遍历整个左或右脊椎,但现在只需查看左和右大部分元素就可以得到O(1)。

   这个策略的一个例子 is used to make purely functional treaps with implementations in SML and Java ( more documentation )这也是其他几个具有O(lg n)性能的不可变deques中的一个关键思想。

2. 束缚了教唆工作

   如上所述,在AVL树的最左端或最右端插入可能需要Ω(lg n)时间才能穿过脊椎。下面是一个AVL树的示例,演示了这一点:

   完整的二叉树通过归纳定义为:

   • 高度为0的完整二叉树是空节点。
   • 高度为n+1的完整二叉树具有根节点,高度为n的完整二叉树作为子级。

   将一个元素推到一个完整的二叉树的左侧必然会增加树的最大高度。由于上面的AVL树将这些信息存储在每个节点中,并且由于沿完整二叉树左脊柱的每一棵树也是完整二叉树,因此将一个元素推到恰好是完整二叉树的AVL DEQUE左侧需要沿左脊柱增加Ω(lg n)高度值。

   (关于这两个注意事项:(a)您可以存储AVL树而不保持节点中的高度;相反,您只保留平衡信息(左高、右高或甚至)。这不会改变上述示例的性能。(b)在AVL树中,您可能不仅需要Ω(lg n)平衡或高度信息更新,还需要Ω(lg n)重新平衡操作。我不记得这方面的细节,它可能只是删除,而不是插入。)

   为了实现O(lg n)deque操作,我们需要限制这项工作。由平衡树表示的不可变deques通常至少使用以下策略之一:

   • 预测需要重新平衡的地方 . 如果您使用的树需要O(lg n)重新平衡,但您知道在哪里需要重新平衡 和 你能足够快地到达那里,你能在O(lg n)时间内完成你的deque操作。将此作为策略的deques将不仅存储指向deque的两个指针(如上文所讨论的,左、右脊椎的末端),而且存储少量 跳转指针 沿着刺向更高的地方。然后,deque操作可以在o(1)时间内访问跳转指针指向的树的根。如果所有需要重新平衡(或更改节点信息)的地方都保持O(lg n)跳转指针,则deque操作可能需要O(lg n)时间。

     (当然,这使得这棵树实际上是一把匕首,因为跳跃指针指向的脊椎上的树也被他们的孩子指向脊椎上。不可变数据结构通常与非树图不符,因为替换由多个其他节点指向的节点需要替换指向它的所有其他节点。我已经看到了通过消除非跳跃指针,把匕首变回树来解决这个问题。然后可以将带有跳转指针的单链接列表存储为列表列表。每个从属列表包含该列表头与其跳转指针之间的所有节点。这需要注意处理部分重叠的跳转指针,而完整的解释可能不适合这样做。)

     这是 Tsakalidis in his paper "AVL Trees for localized search" 允许在松弛平衡条件下对AVL树进行O(1)deque操作。它也是 Kaplan and Tarjan in their paper "Purely functional, real-time deques with catenation" 和A later refinement of that by Mihaesau and Tarjan . Munro et al.'s "Deterministic Skip Lists" 这里也值得一提,尽管通过使用树将跳过列表转换为不可变的设置有时会更改允许在结尾处进行如此有效修改的属性。有关翻译的示例,请参见 Messeguer's "Skip trees, an alternative data structure to Skip lists in a concurrent approach" , Dean and Jones's "Exploring the duality between skip lists and binary search trees" 和 Lamoureux and Nickerson's "On the Equivalence of B-trees and deterministic skip lists" .

   • 做大量的工作 . 在上面的完整二叉树示例中,推送不需要重新平衡,但是Ω(lg n)节点需要更新其高度或平衡信息。您可以简单地将末端的脊椎标记为需要增量,而不是实际执行增量。

     理解这个过程的一种方法是通过类比二进制数。(2^n)-1以二进制形式由一个n 1的字符串表示。当向该数字添加1时,需要将所有1更改为0,然后在结尾添加1。下面的haskell将二进制数编码为非空的位串,最不重要的是首先。

     data Bit = Zero | One
     
     type Binary = (Bit,[Bit])
     
     incr :: Binary -> Binary
     incr (Zero,x) = (One,x)
     incr (One,[]) = (Zero,[One])
     incr (One,(x:xs)) = 
         let (y,ys) = incr (x,xs)
         in (Zero,y:ys)
     

     incr是一个递归函数,用于 (One,replicate k One) ,incr称自己为Ω(k)倍。

     相反,我们可以用组中的位数来表示等位的组。如果相邻的位或位组相等(值而不是数字),则将它们组合成一个组。我们可以增加O(1)时间:

     data Bits = Zeros Int | Ones Int
     
     type SegmentedBinary = (Bits,[Bits])
     
     segIncr :: SegmentedBinary -> SegmentedBinary
     segIncr (Zeros 1,[]) = (Ones 1,[])
     segIncr (Zeros 1,(Ones n:rest)) = (Ones (n+1),rest)
     segIncr (Zeros n,rest) = (Ones 1,Zeros (n-1):rest)
     segIncr (Ones n,[]) = (Zeros n,[Ones 1])
     segIncr (Ones n,(Zeros 1:Ones m:rest)) = (Zeros n,Ones (m+1):rest)
     segIncr (Ones n,(Zeros p:rest)) = (Zeros n,Ones 1:Zeros (p-1):rest)
     

     由于segincr不是递归的,并且不在int上调用除加号和减号以外的任何函数,所以您可以看到它需要0(1)个时间。

     上面题为“预计需要重新平衡的地方”的章节中提到的一些问题实际上使用了一种不同的数字激励技术,称为“冗余数字系统”,将重新平衡工作限制在o(1)并快速定位。冗余的数值表示法很吸引人,但对于这个讨论来说可能太遥远了。 Elmasry et al.'s "Strictly-regular number system and data structures" 是一个不错的地方开始阅读关于那个主题。 Hinze's "Bootstrapping one-sided flexible arrays" 也可能有用。

     在 "Making data structures persistent" ,Driscoll等人描述 惰性再着色 他们将其归因于沙卡利迪斯。他们将其应用于红黑树,在插入或删除后通过O(1)旋转(但Ω(lg n)重新着色)重新平衡(参见 Tarjan's "Updataing a balanced tree in O(1) rotations" )其核心思想是标记一条需要重新着色但不旋转的节点的大路径。在旧版本的AVL树上也使用了类似的想法。 Brown & Tarjan's "A fast merging algorithm" . (同一作品的较新版本使用2-3棵树;我没有读过较新的树,也不知道它们是否使用了懒惰的重新着色等技术。)

   • 随机化 . 如上所述,TREAP可以在功能设置中实现,以便它们平均在O(1)时间执行Deque操作。因为deques不需要检查它们的元素,所以这个平均值不容易受到恶意输入降低性能的影响,而不像简单(没有重新平衡)的二进制搜索树,它的平均输入速度很快。treaps使用随机位的独立源,而不是依赖数据的随机性。

     在持久性设置中,如果对手(a)使用旧版本的数据结构和(b)测量操作性能,则Treaps可能会受到恶意输入导致性能下降的影响。因为他们没有任何最坏情况下的平衡保证,叛徒可以变得相当不平衡,虽然这应该很少发生。如果对手等待一个deque操作需要很长时间,那么她可以重复地启动相同的操作,以测量并利用可能不平衡的树。

     如果这不是一个问题,那么treaps是一个吸引人的简单数据结构。它们非常接近上面描述的AVL脊椎树。

     上面提到的跳过列表也可能适用于使用O(1)平均时间deque操作的功能实现。

     限制再平衡工作的前两种技术需要对数据结构进行复杂的修改,同时通常提供对Deque操作复杂性的简单分析。随机化与下一种技术一起,具有更简单的数据结构,但更复杂的分析。 The original analysis by Seidel and Aragon is not trivial 和上面引用的论文相比,使用更高级的数学对确切概率进行了一些复杂的分析——见 Flajolet et al.'s "Patterns in random binary search trees" .

   • 摊销 . 当从树根向上看时(如上文“倒刺”所述),有几个平衡的树提供O(1) 摊销 插入和删除时间。单个操作可能需要Ω(lg n)时间,但它们使树处于这样一个良好的状态,因此在昂贵的操作之后进行大量操作将是便宜的。

     不幸的是,当旧版本的树仍然存在时,这种分析不起作用。用户可以多次在旧的、几乎失去平衡的树上执行操作,而无需任何干预的廉价操作。

     一种在持续设置中获得摊余界限的方法是由 Chris Okasaki . 要解释摊销是如何在使用任意旧版本的数据结构的能力下存活下来并不简单,但如果我记得正确, Okasaki's first (as far as I know) paper on the subject 有很清楚的解释。有关更全面的解释,请参见 his thesis 或 his book .

     据我所知,有两种基本成分。首先,不要仅仅保证在每次昂贵的操作(通常的摊销方法)之前发生一定数量的廉价操作,而是实际指定并设置 具体的 昂贵的操作 之前 执行廉价的操作来支付费用。在某些情况下,只有在许多干预性的廉价步骤之后,操作才能开始(和完成)。在其他情况下,操作实际上在未来只安排了O(1)个步骤,但是便宜的操作可能会完成昂贵操作的一部分,然后重新安排更多操作以备以后使用。如果一个对手想要一遍又一遍地重复一次昂贵的操作,那么实际上每次都会重复使用相同的计划操作。这种分享是第二种成分的来源。

     计算是用 懒惰 . 延迟值不会立即计算,但一旦执行,其结果将被保存。客户机第一次需要检查懒惰值时,会计算其值。稍后,客户机可以直接使用该缓存值,而不必重新计算它。

     #include <stdlib.h>
     
     struct lazy {
       int (*oper)(const char *);
       char * arg;
       int* ans;
     };
     
     typedef struct lazy * lazyop;
     
     lazyop suspend(int (*oper)(const char *), char * arg) {
       lazyop ans = (lazyop)malloc(sizeof(struct lazy));
       ans->oper = oper;
       ans->arg = arg;
       return ans;
     }
     
     void force(lazyop susp) {
       if (0 == susp) return;
       if (0 != susp->ans) return;
       susp->ans = (int*)malloc(sizeof(int));
       *susp->ans = susp->oper(susp->arg);
     }
     
     int get(lazyop susp) {
       force(susp);
       return *susp->ans;
     }
     

     惰性构造包含在一些MLS中,而haskell在默认情况下是惰性的。在这种情况下,懒惰是一种变异,导致一些作者称之为“副作用”。如果这种副作用在选择一个不变的数据结构的任何原因上都不能很好地发挥作用,那么这可能被认为是不好的,但是,另一方面,把懒惰作为副作用的思想允许将传统的摊余分析技术应用到持久的数据结构上,正如在一篇文章中提到的那样。按 Kaplan, Okasaki, and Tarjan entitled "Simple Confluently Persistent Catenable Lists" .

     再考虑一下上面的对手,他们正试图反复强迫计算一个昂贵的操作。在懒惰价值的第一股力量之后,每一股剩余的力量都是廉价的。

     在他的书中,冈崎解释了如何建立deques和O(1)摊销时间所需的每个操作。它本质上是一个B+树,这是一个树,其中所有元素都存储在叶上,节点可能因子节点的数量而不同,并且每个叶的深度相同。冈崎使用了上面讨论的脊椎反转方法,他将脊椎悬挂在叶元素上方(也就是说,作为一个惰性值存储)。

     一个结构 Hinze and Paterson called "Finger trees: a simple general-purpose data structure" 是在冈崎设计的Deques和 "Purely functional representations of catenable sorted lists" of Kaplan and Tarjan . hinze和paterson的结构已经非常流行。

     作为摊销分析有多复杂的证据,Hinze和Paterson的手指树 frequently implemented without 懒惰,使时间界限不是O(1),但仍然O(lg n)。一个似乎使用懒惰的实现是 one in functional-dotnet . 该项目还包括 implementation of lazy values in C# 如果我没有以上的解释,这可能有助于解释。

Deques可以实现为二叉树吗?是的,而且它们在持续使用时的最坏情况下的复杂性不会比EricLippert提出的更糟。然而,埃里克的树实际上 不够复杂 如果你愿意接受分期付款的表现,那么在一个持续的环境中获得O(1)deque操作,尽管只有很小的复杂性利润(使中心变得懒惰)。一个不同但也很简单的叛国者视图可以在一个功能设置中获得O(1)预期的性能,假设对手不是很狡猾。在功能设置中使用树型结构进行最坏情况下的deque操作比Eric的实现要复杂得多。

最后两条注释(尽管这是一个非常有趣的主题,我保留稍后添加更多内容的权利):-)

1. 上面提到的几乎所有的deques都是手指搜索树。在功能设置中,这意味着它们可以在o(lg(m i n(i,n-i))时间中的第i个元素处拆分,并且大小为n和m的两个树可以在o(lg(m i n(n,m))时间中连接。

2. 我知道两种实现不使用树的deques的方法。冈崎在他的书和论文以及我上面链接的论文中提出了一个。另一种方法使用一种称为“全局重建”的技术,并在 Chuang and Goldberg's "Real-time deques, multihead Turing machines, and purely functional programming" .

其他的答案都很棒。我还要补充一点,我选择了deque的finger-tree实现,因为它对泛型类型系统的使用非同寻常且有趣。大多数数据结构都是递归的 结构 但是这种技术也将递归放在 类型系统 这是我以前没有见过的,我想这可能是大家都感兴趣的。

如果使用平衡二叉树,则两端的插入和删除都是O(lg n)(平均值和最差情况)。 在EricLippert的实现中使用的方法更高效,在平均情况下以恒定时间运行(最坏的情况仍然是O(lg n))。

记住,修改不可变树涉及到重写您正在修改的节点的所有父节点。因此,对于deque,您不希望树保持平衡;相反,您希望L和R节点尽可能靠近根,而树中间的节点可以更远。

不能简单地实现 作为二叉树,元素可以 只能插入或移除 非常“左”(前面)和 很“对”(后面)的树?

当然。高度平衡树的修改版本,特别是AVL树,将非常容易实现。但是,这意味着用 n 元素需要 O(n lg n) 时间——你应该为一个德克射击,它具有与可变对手相似的性能特征。

您可以使用两个堆栈(一个左堆栈和一个右堆栈)为所有主要操作创建一个简单的不可变deque和摊余的常量时间操作。PushLeft和PushRight分别对应于左堆栈和右堆栈上的推送值。您可以从leftstack.hd和leftstack.tl获取deque.hd和deque.tl;如果您的leftstack为空,则设置leftstack=rightstack.reverse和rightstack=empty stack。

type 'a deque = Node of 'a list * 'a list    // '

let peekFront = function
    | Node([], []) -> failwith "Empty queue"
    | Node(x::xs, ys) -> x
    | Node([], ys) -> ys |> List.rev |> List.head
let peekRear = function
    | Node([], []) -> failwith "Empty queue"
    | Node(xs, y::ys) -> y
    | Node(xs, []) -> xs |> List.rev |> List.head
let pushFront v = function
    | Node(xs, ys) -> Node(v::xs, ys)
let pushRear v = function
    | Node(xs, ys) -> Node(xs, v::ys)
let tl = function
    | Node([], []) -> failwith "Empty queue"
    | Node([], ys) -> Node(ys |> List.rev |> List.tail, [])
    | Node(x::xs, ys) -> Node(xs, ys)

这是一个非常常见的实现,它非常容易优化以获得更好的性能。