代码之家 › 专栏 › 技术社区 › Addem

使用2-3树维护列表

tree list algorithm

0

Addem · 技术社区 · 7 年前

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

我是应该继续努力实现这一点,还是我最初的决定是将计数存储在应该考虑重新设计树的节点上?

0 回复 | 直到 7 年前

1

2

SecularisticSloth 7 年前

(我要回答wrt。一棵红黑的树而不是2-3棵树,因为这更容易推理。这个答案需要稍作调整,以适应2-3棵树)

与其让每个顶点都在其左边存储元素的数量,不如让每个顶点在它作为根的子树中存储元素的数量。在树中从根向下导航时,请保持累计和你左手边的元素。无论何时移动到顶点的右子对象五 ,添加五的左子树到 s .

连接两个列表和 B (也就是说, B 附加到 )只需创建一个新顶点五 A B 它分别是左、右孩子。更新根目录的子树中的元素数五元素个数之和和 B

将一个列表一分为二,只需移除要切掉的列表根的边。

但是,根据列表的大小,树可能会变得不平衡。在一定数量的“不平衡”连接或拆分之后,您必须重新平衡树。我必须承认,我不太清楚这件事的时间复杂性。我很确定你不能得到固定时间的摊销,但你可能可以得到O(logn)时间的摊销。