2-3树叶间最大值的搜索
2-3树叶间最大值的搜索
提问于 2015-02-15 17:31:24
我有一棵2-3棵树，每一片叶子包括：
- 钥匙
- 价值
这棵树是按钥匙排列的。
我希望在最坏的情况下，在O(logn)中，在2键i
我很清楚，我需要存储更多的信息，比如“子树中的最大值”。然而，我不能想出精确的算法去遍历所有相关的子树来实现我的目标。
编辑我正在寻找类似于以下线程的内容：
Search max value between 2 AVL nodes
唯一的区别是我对2-3棵树感兴趣。
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-02-19 00:32:35
将maxTreeValue保存在每个节点中，表示该子树中的最大值(每次修改后应该更新，从修改的节点开始自下而上)。
同时开始搜索两个i,j，在搜索路径分离的节点处停止。
从该节点搜索i。对于路径中的每个节点，查找每个边缘的子树之间的最大值，从i's search path 独占中的下一个边缘到最右边的包含，或者到j 独占的搜索路径上的边缘，这是它们之间的第一个。
然后对称地对j执行相同的操作，并在它们之间返回最大值。
Stack Overflow用户
发布于 2015-02-19 01:30:30
不需要在树节点中存储额外的信息。
每个2-3个节点都有一个或两个键和2到3个链接.将变量best_seen设置为nil。从树根开始，考虑以下详尽的情况：
- 节点中的所有键都在右侧< i. Recurse。如果有任何满足标准的密钥，则必须位于该节点的右侧。
- 节点中的所有键都是左侧的>j.Recurse。如果有满足条件的密钥，则必须位于此节点的左侧。
- 其中一个或两个键位于i和j之间；选择i和j之间的较大键作为
best_seen，并在best_seen的右侧进行递归。如果有比best_seen更大的密钥满足条件，则该密钥的右侧。 - 节点为
nil，返回best_seen
断言:永远不会用较小的值替换best_seen。(这是因为我们总是在设置best_seen之后向右递归。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28528929
复制相关文章
相似问题
腾讯云开发者
