我有一棵 2-3 的树，其中每片叶子包括:
- key
- 值(value)
树按键排序。
我想在最坏情况 O(logn) 内找到 2 个键 i < j(在域 [i,j] 中)之间的最大值。
我很清楚我需要存储额外的信息，例如“子树中的最大值”。但是，我无法想出遍历所有相关子树来实现我的目标的精确算法。
[编辑] 我正在寻找类似于以下线程的内容:
Search max value between 2 AVL nodes
唯一的区别是我对 2-3 树感兴趣。
最佳答案
在每个节点中保留maxTreeValue，表示该子树中的最大值(每次修改后都要更新，自下而上从修改的节点开始)。
同时开始搜索 i,j，在搜索路径分开的节点处停止。
从该节点搜索 i。
对于路径中的每个节点，找到每条边的子树之间的最大值，从i的搜索路径中的下一条边不包含到最右边的边 inclusive，或者到j搜索路径的边缘 exclusive，它们之间的第一个。
然后对j对称地做同样的事情，并返回它们之间的最大值。
关于algorithm - 搜索两个 2-3 树叶之间的最大值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28528929/