我有一棵包含一组数字的树,其中每个数字都有 2 个关联的字符串:a 和 b。所以结构看起来像:
a-number-b
对于每个节点。
我想在 O(log n) 最坏情况运行时间内获得树中 a=b 的最大数。
我的方法: 试过红黑树。如果数字在右子树中,则其复杂度为 O(log n)。 但是如果数字在左子树中则为 O(n)。
不能使用常规 BST,至于最坏的情况,它的运行时间为 O(n)。
最佳答案
如果您为每个子树在树的节点中存储了最大可能值,则这是可能的。
对于给定的树,您需要的最大值可以从根部读取。
在插入/删除/轮换过程中,该属性可以在O(log n)时间内保持。
Cormen 等人的算法导论(通常称为 CLR 书)中有一章名为扩充数据结构。对此。
我建议你阅读它。相关的定理是定理 14.1,它指出
Let
f
be a field that augments a red-black treeT
ofn
nodes and suppose that the contents off
for a nodex
can be computed using only information in nodesx
,left(x)
andright(x)
, includingf(left(x))
andf(right(x))
. Then we can maintain the values off
in all nodes ofT
during insertion and deletion without asymptotically affecting theO(log n)
performance of these operations.
left(x) 是 x 等的左 child
对于你的情况,定义 g(node)
为 node.number
如果 node.a == node.b
,并且 -infinity
否则。
定义 f(x)
为 max f(left(x)), f(right(x)), g(x)
。
关于algorithm - 红黑树中具有相同字符串的最大整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29976062/