搜索两个 2-3 树叶之间的最大值
Searching for max value between two 2-3 Tree leafs
我有一棵 2-3 的树，其中每片叶子包括：
- 密钥
- 价值
树按键排序。
我想在最坏情况下 O(logn) 内找到 2 个键 i < j（在域 [i,j] 中）之间的最大值。
我很清楚我需要存储额外的信息，例如 "maximum in a subtree"。但是，我无法想出遍历所有相关子树来实现我的目标的精确算法。
[编辑]
我正在寻找类似于以下线程的内容：
Search max value between 2 AVL nodes
唯一不同的是我对 2-3 树感兴趣。
在每个节点中保留maxTreeValue，代表该子树中的最大值（每次修改后都要更新，从修改的节点开始自下而上）。
同时开始搜索i,j，在搜索路径分开的节点处停止。
从该节点搜索 i。
对于路径中的每个节点，求每条边的子树之间的最大值，从i的搜索路径中的下一条边独占到最右边的边inclusive，或者到 j exclusive 的搜索路径上的边缘，它们之间的第一个。
然后对 j 对称地做同样的事情，return 它们之间的最大值。
不需要在树节点中存储额外的信息。
每2-3个节点有1个或2个键，2到3个链接。将变量 best_seen 设置为 nil。从树的根开始，考虑以下详尽的情况：
节点中的所有键都
节点中的所有键都 > j。向左递归。 [如果有满足条件的key，一定在这个节点的左边。]
一个或两个键在i和j之间；选择i和j中较大的key作为best_seen，向best_seen的右边递归。 [如果有任何大于 best_seen 的键满足条件，它将在该键的右侧。]
节点为nil,returnbest_seen
断言：best_seen 永远不会被替换为更小的值。 （这是因为我们总是在设置best_seen后向右递归。）
我有一棵 2-3 的树，其中每片叶子包括：
- 密钥
- 价值
树按键排序。
我想在最坏情况下 O(logn) 内找到 2 个键 i < j（在域 [i,j] 中）之间的最大值。
我很清楚我需要存储额外的信息，例如 "maximum in a subtree"。但是，我无法想出遍历所有相关子树来实现我的目标的精确算法。
[编辑] 我正在寻找类似于以下线程的内容：
Search max value between 2 AVL nodes
唯一不同的是我对 2-3 树感兴趣。
在每个节点中保留maxTreeValue，代表该子树中的最大值（每次修改后都要更新，从修改的节点开始自下而上）。
同时开始搜索i,j，在搜索路径分开的节点处停止。
从该节点搜索 i。
对于路径中的每个节点，求每条边的子树之间的最大值，从i的搜索路径中的下一条边独占到最右边的边inclusive，或者到 j exclusive 的搜索路径上的边缘，它们之间的第一个。
然后对 j 对称地做同样的事情，return 它们之间的最大值。
不需要在树节点中存储额外的信息。
每2-3个节点有1个或2个键，2到3个链接。将变量 best_seen 设置为 nil。从树的根开始，考虑以下详尽的情况：
节点中的所有键都
节点中的所有键都 > j。向左递归。 [如果有满足条件的key，一定在这个节点的左边。]
一个或两个键在i和j之间；选择i和j中较大的key作为
best_seen，向best_seen的右边递归。 [如果有任何大于best_seen的键满足条件，它将在该键的右侧。]节点为
nil,returnbest_seen
断言：best_seen 永远不会被替换为更小的值。 （这是因为我们总是在设置best_seen后向右递归。）