data-structures - 将不可变双端队列实现为平衡二叉树？

Question

我一直在思考如何将双端队列（即双端队列）实现为不可变的数据结构。

似乎有不同的方法可以做到这一点。AFAIK，不可变数据结构通常是分层的，因此它的主要部分可以在修改操作（例如插入或删除项目）后重用。

Eric Lippert 在他的博客上有两篇 关于此主题的文章，以及 C# 中的示例实现。

他的两个实现都让我觉得比实际需要的更复杂。不能将双端队列简单地实现为二叉树，其中元素只能在树的“左”（前）和“右”（后）插入或删除？

                               o
                              / \
                             …   …
                            /     \
                           …       …
                          / \     / \
              front -->  L   …   …   R  <-- back

此外，树将通过旋转保持合理的平衡：

• 在前面插入或从后面取出时向右旋转，以及
• 从前面移除或从后面插入时左旋转。

在我看来，Eric Lippert 是一个非常聪明的人，我非常尊重他，但他显然没有考虑过这种方法。因此，我想知道，这是有充分理由的吗？我建议的实现双端队列的方法是否幼稚？

Answer 1

正如 Daniel 所指出的，使用众所周知的平衡搜索树（如 AVL 或红黑树）实现不可变双端队列会给出 Θ(lg n) 最坏情况复杂度。Lippert 讨论的一些实现乍一看可能看起来很复杂，但是有许多不可变的双端队列具有 o(lg n) 最差或平均或摊销复杂性，它们是由平衡树以及两个简单的想法构建的：

1. 扭转脊椎

   要在传统的平衡搜索树上执行双端队列操作，我们需要访问末端，但我们只能访问中心。为了到达左端，我们必须导航左子指针，直到最终到达死胡同。最好有一个指向左端和右端的指针，而不需要所有的导航工作。事实上，我们真的不需要经常访问根节点。让我们存储一个平衡的搜索树，以便访问末端是 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;
   };
   

   从某种意义上说，最左边的孩子现在是树的“根”。如果你这样画树，看起来会很奇怪，但是如果你只是简单地把树的正常绘制和左脊椎上的所有箭头反转，LeftSpine 结构的含义应该会变得更清楚。现在可以立即访问树的左侧。右侧脊柱也可以这样做：

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

   如果您同时存储左右脊椎以及中心元素，则可以立即访问两端。插入和删除可能仍然是 Ω(lg n)，因为重新平衡操作可能需要遍历整个左侧或右侧脊椎，但现在简单地查看左侧和最右侧的元素是 O(1)。

   此策略的一个示例用于使用 SML 和 Java 中的实现进行纯功能性的陷阱（更多文档）。这也是其他几个具有 o(lg n) 性能的不可变双端队列的关键思想。

2. 绑定 Rabalancing 工作

   如上所述，在 AVL 树的左端或最右端插入可能需要 Ω(lg n) 时间来遍历脊柱。下面是一个演示这一点的 AVL 树示例：

   一个完整的二叉树通过归纳定义为：

   • 高度为 0 的完整二叉树是一个空节点。
   • 高度为 n+1 的完全二叉树有一个根节点，其中高度为 n 的完全二叉树作为子节点。

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

   （对此有两个注意事项：（a）您可以在不保留节点高度的情况下存储 AVL 树；相反，您只保留平衡信息（左高、右高，甚至）。这不会改变(b) 在 AVL 树中，你可能不仅需要更新 Ω(lg n) 平衡或高度信息，还需要进行 Ω(lg n) 重新平衡操作。我不记得这个细节了，它可能仅用于删除，而不是插入。）

   为了实现 o(lg n) 的双端队列操作，我们需要限制这项工作。由平衡树表示的不可变双端队列通常至少使用以下策略之一：

   • 预测需要重新平衡的地方。如果您正在使用需要 o(lg n) 重新平衡的树，但您知道需要重新平衡的位置并且可以足够快地到达那里，则可以在 o(lg n) 时间内执行双端队列操作。使用此策略的双端队列将不仅将两个指针存储到双端队列（左右脊椎的末端，如上所述），而且还会将一些跳转指针存储到沿脊椎更高的位置。然后双端队列操作可以在 O(1) 时间内访问跳转指针指向的树的根。如果为需要重新平衡（或更改节点信息）的所有位置维护 o(lg n) 跳转指针，则双端队列操作可能需要 o(lg n) 时间。

     （当然，这使得树实际上是一个 dag，因为跳转指针所指向的脊上的树也被脊上它们的孩子所指向。不可变数据结构通常不会与非树图相处，因为替换一个由多个其他节点指向的节点需要替换指向它的所有其他节点。我已经通过消除非跳转指针，将 dag 转回一棵树来解决这个问题。然后可以存储一个带有跳转指针的单链表作为列表的列表。每个从属列表包含该列表的头部与其跳转指针之间的所有节点。这需要小心处理部分重叠的跳转指针，并且可能是完整的解释不适合这个。）

     这是Tsakalidis 在他的论文“用于本地化搜索的 AVL 树”中使用的技巧之一，以允许在具有宽松平衡条件的 AVL 树上进行 O(1) 双端队列操作。这也是Kaplan 和 Tarjan 在他们的论文“Purely functional, real-time deques with catenation”中使用的主要思想，后来 Mihaesau 和 Tarjan 对其进行了改进。Munro 等人的“确定性跳过列表”在这里也值得一提，尽管通过使用树将跳过列表转换为不可变设置有时会更改允许在末端附近进行此类有效修改的属性。有关翻译的示例，请参阅Messeguer 的“Skip trees, an alternative data structure to Skip lists in a concurrent approach”Dean 和 Jones 的“探索跳跃列表和二叉搜索树之间的对偶性”，以及Lamoureux 和 Nickerson 的“关于 B 树和确定性跳跃列表的等价性”。

   • 批量完成工作。在上面的完整二叉树示例中，推送时不需要重新平衡，但 Ω(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 不是递归的并且不调用除 Ints 上的 plus 和 minus 以外的任何函数，您可以看到它需要 O(1) 时间。

     上面标题为“预测需要重新平衡的地方”一节中提到的一些双端队列实际上使用了一种不同的数字启发技术，称为“冗余数字系统”，将重新平衡工作限制在 O(1) 并快速定位。冗余的数字表示很吸引人，但对于这个讨论来说可能太遥远了。Elmasry 等人的“严格正则数字系统和数据结构”不是开始阅读该主题的好地方。Hinze 的“Bootstrapping one-sided flexible arrays”也可能有用。

     在“使数据结构持久化”中，Driscoll 等人。描述惰性重新着色，他们将其归因于 Tsakalidis。他们将其应用于红黑树，可以在插入或删除后通过 O(1) 旋转（但 Ω(lg n) 重新着色）重新平衡（参见Tarjan 的“在 O(1) 旋转中更新平衡树”）。这个想法的核心是标记需要重新着色但不旋转的节点的大路径。在旧版本的Brown & Tarjan 的“A fast merging algorithm”中，类似的想法被用于 AVL 树。（同一作品的较新版本使用 2-3 棵树；我没有读过较新的，也不知道他们是否使用了任何技术，例如延迟重新着色。）

   • 随机化。上面提到的 Treap 可以在功能设置中实现，以便它们平均在 O(1) 时间内执行双端队列操作。由于双端队列不需要检查它们的元素，因此该平均值不易受到恶意输入降低性能的影响，这与简单（无重新平衡）二叉搜索树不同，二叉搜索树的平均输入速度很快。Treaps 使用独立的随机位源，而不是依赖于数据的随机性。

     在持久设置中，trap 可能容易受到攻击者恶意输入的影响，攻击者既可以 (a) 使用旧版本的数据结构，也可以 (b) 测量操作的性能。因为它们没有任何最坏情况下的平衡保证，traps 可能会变得非常不平衡，尽管这种情况很少发生。如果对手等待需要很长时间的双端队列操作，她可以重复启动相同的操作，以测量和利用可能不平衡的树。

     如果这不是一个问题，trap 是一种非常简单的数据结构。它们非常接近上述的 AVL 脊柱树。

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

     用于限制再平衡工作的前两种技术需要对数据结构进行复杂的修改，同时通常对双端队列操作的复杂性进行简单分析。随机化以及下一种技术具有更简单的数据结构但更复杂的分析。Seidel 和 Aragon 的原始分析并非微不足道，并且使用比上面引用的论文更高级的数学对精确概率进行了一些复杂的分析——参见Flajolet 等人的“随机二叉搜索树中的模式”。

   • 摊销。有几个平衡树，当从根向上观察时（如上文“反转脊椎”中所述），提供 O(1)分期插入和删除时间。单个操作可能需要 Ω(lg n) 时间，但它们使树处于非常好的状态，以至于在昂贵操作之后的大量操作将变得很便宜。

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

     Chris Okasaki发明了一种在持久设置中获得摊销界限的方法。解释摊销如何在使用任意旧版本数据结构的能力中幸存下来并不简单，但如果我没记错的话，冈崎的第一篇（据我所知）关于这个主题的论文有一个非常清楚的解释。有关更全面的解释，请参阅他的论文或他的书。

     据我了解，有两个基本要素。首先，您实际上指定并设置特定的昂贵操作执行将为此付出代价的廉价操作。在某些情况下，操作被安排在许多干预廉价步骤之后才开始（和完成）。在其他情况下，该操作实际上仅在未来安排 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;
     }
     

     惰性结构包含在一些 ML 中，Haskell 默认是惰性的。在引擎盖下，懒惰是一种突变，这导致一些作者称其为“副作用”。如果这种副作用不能很好地与首先选择不可变数据结构的原因一起发挥作用，那可能会被认为是不好的，但是另一方面，将惰性视为副作用允许应用如Kaplan、Okasaki 和 Tarjan 题为“Simple Confluently Persistent Catenable Lists”的论文中提到的对持久数据结构的传统摊销分析技术。

     再次考虑上面的对手，他试图反复强制计算昂贵的操作。在懒惰值的第一个力量之后，每一个剩余的力量都是便宜的。

     在他的书中，Okasaki 解释了如何使用每个操作所需的 O(1) 摊销时间来构建双端队列。它本质上是一棵 B+-树，这是一棵树，其中所有元素都存储在叶子上，节点的子节点数量可能会有所不同，并且每个叶子的深度都相同。Okasaki 使用上面讨论的脊椎反转方法，他将脊椎挂起（即，存储为惰性值）叶元素上方。

     Hinze 和 Paterson的结构称为“手指树：一种简单的通用数据结构”，介于 Okasaki 设计的双端队列与 Kaplan 和 Tarjan 的“可连接排序列表的纯功能表示”之间。Hinze 和 Paterson 的结构变得非常流行。

     作为摊销分析难以理解的证据，Hinze 和 Paterson 的手指树经常 在没有惰性的情况下实现 ，使得时间界限不是 O(1)，而是 O(lg n)。一种似乎使用惰性的实现是functional-dotnet 中的实现。该项目还包括C# 中惰性值的实现，如果缺少我上面的解释，这可能有助于解释它们。

双端队列可以实现为二叉树吗？是的，如果持续使用，它们的最坏情况复杂性不会比 Eric Lippert 提出的更差。然而，Eric 的树实际上并不足以在持久设置中获得 O(1) 的双端队列操作，但如果您愿意接受摊销的性能，则只有很小的复杂度余量（使中心变得懒惰）。假设对手不太狡猾，一个不同但也很简单的陷阱视图可以在功能设置中获得 O(1) 的预期性能。在功能设置中使用树状结构获得 O(1) 最坏情况的双端队列操作需要比 Eric 的实现更复杂一些。

---

最后的两个注释（虽然这是一个非常有趣的话题，我保留稍后添加更多内容的权利）:-)

1. 上面提到的几乎所有双端队列也是手指搜索树。在功能设置中，这意味着它们可以在 O(lg(min(i,ni))) 时间内在第 i 个元素处拆分，并且两个大小为 n 和 m 的树可以在 O(lg(min(n,m) ）） 时间。

2. 我知道两种实现不使用树的双端队列的方法。冈崎在他的书和论文以及我上面链接的论文中提出了一个。另一种使用称为“全局重建”的技术，并在Chuang 和 Goldberg 的“实时双端队列、多头图灵机和纯函数式编程”中进行了介绍。

Answer 2

如果您使用平衡二叉树，则两端的插入和删除都是 O(lg N)（平均和最坏情况）。Eric Lippert 的实现中使用的方法更有效，在平均情况下以恒定时间运行（最坏的情况仍然是 O(lg N)）。

请记住，修改不可变树涉及重写您正在修改的节点的所有父节点。所以对于双端队列，你不希望树是平衡的；相反，您希望 L 和 R 节点尽可能靠近根，而树中间的节点可以更远。

Answer 3

其他答案都很棒。我要补充一点，我选择了双端队列的手指树实现，因为它对泛型类型系统进行了不寻常且有趣的使用。大多数数据结构的结构都是递归的，但这种技术也将递归置于我以前从未见过的类型系统中；我想这可能是普遍的兴趣。

Answer 4

不能将双端队列简单地实现为二叉树，其中元素只能在树的“左侧”（前面）和“右侧”（后面）插入或删除？

绝对地。高度平衡树的修改版本，特别是 AVL 树，将非常容易实现。n然而，这意味着用元素填充基于树的队列需要O(n lg n)时间——您应该寻找与可变对应物具有相似性能特征的双端队列。

您可以使用两个堆栈，一个左堆栈和一个右堆栈，为所有主要操作创建一个简单的不可变双端队列，并为所有主要操作创建分摊的常数时间操作。PushLeft 和 PushRight 分别对应左右栈的压栈值。您可以从 LeftStack.Hd 和 LeftStack.Tl 中获取 Deque.Hd 和 Deque.Tl；如果您的 LeftStack 为空，请设置 LeftStack = RightStack.Reverse 和 RightStack = 空堆栈。

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)

这是一个非常常见的实现，并且很容易优化以获得更好的性能。