algorithm - 红黑树中具有相同字符串的最大整数

Question

我有一棵包含一组数字的树，其中每个数字都有 2 个关联的字符串:a 和 b。所以结构看起来像:

a-number-b

对于每个节点。

我想在 O(log n) 最坏情况运行时间内获得树中 a=b 的最大数。

我的方法:试过红黑树。如果数字在右子树中，则其复杂度为 O(log n)。但是如果数字在左子树中则为 O(n)。

不能使用常规 BST，至于最坏的情况，它的运行时间为 O(n)。

Answer 1

如果您为每个子树在树的节点中存储了最大可能值，则这是可能的。

对于给定的树，您需要的最大值可以从根部读取。

在插入/删除/轮换过程中，该属性可以在O(log n)时间内保持。

Cormen 等人的算法导论(通常称为 CLR 书)中有一章名为扩充数据结构。对此。

我建议你阅读它。相关的定理是定理 14.1，它指出

Let f be a field that augments a red-black tree T of n nodes and suppose that the contents of f for a node x can be computed using only information in nodes x, left(x) and right(x), including f(left(x)) and f(right(x)). Then we can maintain the values of f in all nodes of T during insertion and deletion without asymptotically affecting the O(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)。