使用2-3树来维护列表
假设我们尝试使用2-3棵树来维护一个列表结构，并希望有高效的操作来创建列表、连接、拆分和获取索引处的值。我尝试这样做的第一个尝试是将列表元素看作2-3树中的叶子，每个内部节点都存储左边的叶子数量。这样，如果您想要搜索索引，那么如果您搜索的索引小于任何内部节点的值，它将向左查找，否则将向右查找。如果它找不到叶子，那么索引就越界了。
但是，我不确定在连接列表时如何有效地维护这个不变量。我可以将L2的树表示添加到L1树中最右侧的位置，然后尝试更新计数，然后尝试实现类似于2-3棵树的插入算法……但至少我的直觉告诉我，我不能让它变得有效(即O(log(N )。
我应该继续尝试让它工作，还是我最初的决定是将计数存储在我应该考虑重新设计树的节点上？
回答 1
Stack Overflow用户
发布于 2019-02-22 05:11:56
(我将回答wrt。红黑树而不是2-3树，因为它更容易推理。这个答案需要稍微调整一下才能与2-3棵树一起工作)
让每个顶点存储其左侧元素的数量，而不是让每个顶点存储它所在的子树中的元素数量。当在树中从根向下导航时，保留左侧元素的累积和s。每当移动到顶点v的右子对象时，将v的左子对象子树中的元素数添加到的中。
当你连接或拆分两个列表时，这个不变量不需要更新。
要连接两个列表A和B (即，将B附加到A)，只需创建一个新顶点v，并将A和B分别设置为其左右两个子节点。将以v为根的子树中的元素数更新为A和B中的元素数之和。
将一个列表一分为二，只需去掉要截取的列表根部的边缘即可。
(更新)
但是，根据列表的大小，树可能会变得不平衡。经过一定数量的“不平衡”连接或拆分后，您将不得不重新平衡树。我必须承认，我不完全确定这是什么时间复杂度。我很确定你不能得到分期不变的时间，但你也许可以得到O(log )的分期时间。
https://stackoverflow.com/questions/54814659
复制相似问题
腾讯云开发者
