红黑树中具有相同字符串的最大整数
Max integer with same strings, in a red black tree
我有一棵包含一组数字的树，其中每个数字都有 2 个关联的字符串：a 和 b。所以结构看起来像：
a-number-b
每个节点。
我想在 O(log n) 最坏情况 运行 时间内获得树中 a=b 的最大数量。
我的做法：
试过红黑树。如果数字在右子树中，则其复杂度为 O(log n)。
但是如果数字在左子树中，则为 O(n)。
不能使用常规 BST，至于最坏的情况，运行时间为 O(n)。
如果您为每个子树在树的节点中存储了最大可能值，那么这是可能的。
对于给定的树，您需要的最大值可以从根部读取。
在insertion/deletion/rotation期间，这个属性可以在O(log n)时间内维护。
Cormen 等人的算法导论（通常称为 CLR 书籍）中有一章名为 Augmenting Data Structures。对此。
我建议你读一读。相关定理是定理 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等
对于您的情况，如果 node.a == node.b，则将 g(node) 定义为 node.number，否则 -infinity。
定义 f(x) 为 max f(left(x)), f(right(x)), g(x).
一种解决方案是维护两棵树；一种是 a == b，另一种是 a != b。对于大多数函数，您可能需要同时调用两棵树，但这最终会导致相同的 big-O 复杂度，因为 2*O(log n) -> O(log n).
我有一棵包含一组数字的树，其中每个数字都有 2 个关联的字符串：a 和 b。所以结构看起来像：
a-number-b
每个节点。
我想在 O(log n) 最坏情况 运行 时间内获得树中 a=b 的最大数量。
我的做法： 试过红黑树。如果数字在右子树中，则其复杂度为 O(log n)。 但是如果数字在左子树中，则为 O(n)。
不能使用常规 BST，至于最坏的情况，运行时间为 O(n)。
如果您为每个子树在树的节点中存储了最大可能值，那么这是可能的。
对于给定的树，您需要的最大值可以从根部读取。
在insertion/deletion/rotation期间，这个属性可以在O(log n)时间内维护。
Cormen 等人的算法导论（通常称为 CLR 书籍）中有一章名为 Augmenting Data Structures。对此。
我建议你读一读。相关定理是定理 14.1，它指出
Let
fbe a field that augments a red-black treeTofnnodes and suppose that the contents offfor a nodexcan be computed using only information in nodesx,left(x)andright(x), includingf(left(x))andf(right(x)). Then we can maintain the values offin all nodes ofTduring insertion and deletion without asymptotically affecting theO(log n)performance of these operations.
left(x) 是x的左child等
对于您的情况，如果 node.a == node.b，则将 g(node) 定义为 node.number，否则 -infinity。
定义 f(x) 为 max f(left(x)), f(right(x)), g(x).
一种解决方案是维护两棵树；一种是 a == b，另一种是 a != b。对于大多数函数，您可能需要同时调用两棵树，但这最终会导致相同的 big-O 复杂度，因为 2*O(log n) -> O(log n).