algorithm - 使用 2-3 树来维护列表
问题描述
假设我们尝试使用 2-3 棵树来维护一个列表结构,并希望有高效的操作来创建列表、连接、拆分和获取索引处的值。我尝试这样做的第一个尝试是将列表元素视为 2-3 树中的叶子,每个内部节点都存储左侧的叶子数。这样,如果您想搜索索引,那么如果您搜索的索引小于任何内部节点的值,它将向左看,否则向右看。如果找不到叶子,则索引超出范围。
但是,我不确定在连接列表时如何以有效的方式保持这个不变量。我可以将 L2 的树表示添加到 L1 的树中最右边的可用位置,然后尝试更新计数,然后尝试为 2-3 棵树实现一些插入算法……但至少我的直觉告诉我,我将无法提高效率(即 O(log(n)) )。
我应该继续努力完成这项工作,还是我最初决定将计数存储在我应该考虑重新设计树的节点上?
解决方案
(我将回答 wrt。红黑树而不是 2-3 树,因为它更容易推理。这个答案需要稍微调整才能使用 2-3 树)
不是让每个顶点存储其左侧的元素数量,而是让每个顶点存储它作为根的子树中的元素数量。当在树中从根向下导航时, 请保留左侧元素的累积总和。每当您移动到顶点v的右孩子时,将v的左孩子的子树中的元素数添加到s。
当您连接或拆分两个列表时,此不变量不需要更新。
要连接两个列表A和B(即B附加到A),只需创建一个新顶点v,并将A和B分别设为其左右子节点。将以v为根的子树中的元素数更新为A和B中元素数的总和。
两个将列表一分为二,只需删除指向要切断的列表根的边缘即可。
(更新)
但是,根据列表的大小,树可能会变得不平衡。在一定数量的“不平衡”连接或拆分之后,您将不得不重新平衡树。我必须承认,我不完全确定它的时间复杂度是多少。我很确定你不能得到摊销的常数时间,但你可能能够得到摊销的 O(log n) 时间。
推荐阅读
- node.js - 在 vscode 测试运行脚本 (index.ts) 中传递命令行参数
- javascript - 在角度/电子应用程序中使用带有 socket.io 的 nodejs 脚本
- mysql - 复杂的mysql触发器与python代码的性能如何?
- matlab - 使用具有三个 10x5 双数组的单元格的 Matlab 组覆盖条字符
- unix - 如何将 sed 命令放入 while 循环中?
- json4s - JsonMethods 不是包 org.json4s.jackson 的成员
- json - Angular 项目未显示为 Chrome 扩展程序
- compilation - 创建静态链接共享库
- javascript - 被过滤的 AG-Grid 行未正确呈现
- python - 使用 Python 3 打开 Jupyter Notebook