algorithm - 使用 2-3 树维护列表

Question

假设我们尝试使用 2-3 棵树来维护一个列表结构，并希望有高效的操作来创建列表、连接、拆分和获取索引处的值。我尝试这样做的第一次尝试是将列表元素视为 2-3 树中的叶子，并且每个内部节点都存储左侧叶子的数量。这样如果你想搜索一个索引，那么如果你搜索的索引小于任何内部节点的值，它将向左查找，否则向右查找。如果找不到叶子，则索引超出范围。

但是，我不确定在连接列表时如何以有效的方式维护这个不变量。我可以将 L2 的树表示添加到 L1 树中最右边的可用位置，然后尝试更新计数，然后尝试为 2-3 棵树实现一些插入算法……但至少我的直觉告诉我，我无法做到这一点(即 O(log(n)) )。

我应该继续努力使这项工作成功，还是我最初的决定是将计数存储在我应该考虑重新设计树的节点上？

Answer 1

(我将回答 wrt。红黑树而不是 2-3 树，因为它更容易推理。这个答案需要稍微调整以使用 2-3 树)

不是让每个顶点存储其左侧的元素数量，而是让每个顶点存储其作为根的子树中的元素数量。在树中从根向下导航时，请保持左侧元素的累积和 s。每当您移动到顶点 v 的右 child 时，将 v 的左 child 的子树中的元素数添加到 s。

当您连接或拆分两个列表时，此不变量不需要更新。

要连接两个列表 A 和 B(即 B 附加到 A)，只需创建一个新顶点v，并分别将A 和B 作为它的左右子节点。将以 v 为根的子树中的元素数更新为 A 和 B 中的元素数之和。

Two 将列表一分为二，只需删除要切断的列表根部的边即可。

(更新)

但是，根据列表的大小，树可能会变得不平衡。在一定数量的“不平衡”连接或拆分之后，您将不得不重新平衡树。我必须承认，我不完全确定它的时间复杂度是多少。我很确定你不能摊销固定时间，但你可以摊销 O(log n) 时间。