在给定的二叉树中，计算每个子树中大于根节点的节点数，时间复杂度为O(n log n)。

Question

我们有一棵树，有n个节点，以指向其根节点的指针的形式给出，其中每个节点包含指向其父节点、左子节点和右子节点的指针，以及一个整数键。对于每个节点v，我想添加额外的字段v.bigger，其中应该包含以v为根节点的子树中键大于v.key的节点数。将这样的字段添加到树的所有节点中应该总共需要O(n log n)时间。

我正在寻找任何可以帮助我解决这个问题的提示。我尝试了几种启发式方法——例如，在考虑从底向上的方式解决这个问题时，对于一个固定的节点v，v.left和v.right可以为v提供某种集合（平衡BST？），其中操作bigger(x)会对于给定的x在logarithmic时间内返回该集合中大于x的元素数量。问题在于，我们需要在O(log n)中合并这些集合，因此似乎行不通，因为我不知道任何有序集合数据结构支持快速合并。

我还考虑了自上而下的方法——如果仅当u位于到根路径的简单路径上且u < v时，节点v才会向某个u.bigger添加1。因此，v可以以某种方式更新所有这些u，但是我无法想出任何合理的方法来做到这一点...

那么，解决这个问题的正确方法是什么？

- qiubit

Answer 1

在给定树中执行深度优先搜索（从根节点开始）。

当任何节点首次被访问时（来自父节点），将其键添加到某个顺序统计数据结构（OSDS）中。同时查询OSDS以获取大于当前键的键数，并使用此查询的结果的负值初始化v.bigger。

当任何节点最后一次被访问时（来自右子节点），查询OSDS以获取大于当前键的键数，并将结果添加到v.bigger。

您可以将此算法应用于任何有根树（不一定是二叉树）。它不一定需要父指针（您可以使用DFS堆栈代替）。

对于OSDS，您可以使用增强型二叉搜索树或树状数组。在使用树状数组的情况下，您需要预处理给定树，使键的值被压缩：只需将所有键复制到数组中，排序，去除重复项，然后用它们在此数组中的索引替换键。

- Evgeny Kluev

---

太简单了...我简直不敢相信我没想到那个 ;) - qiubit

Answer 2

基本思想：

采用自下而上的方法，每个节点将获得两个有序子树值列表，并查找其中多少个更大。完成后，向上传递合并的有序列表。

详细信息：

1. 叶子节点：
   叶子节点显然具有 v.bigger=0。其上方的节点创建一个包含两个值的列表，更新自身并将自己的值添加到列表中。
2. 所有其他节点：
   从子节点获取两个列表并以有序方式合并它们。由于它们已经排序，这是 O(子树中节点数)。在合并过程中，还可以找到符合条件的节点数量并获取节点的 v.bigger 值。

为什么是O(n logn)？

树中的每个节点通过其子树中的节点数进行计数。这意味着根节点计算树中的所有节点，根节点的子节点各自计算（合并）树中的节点数（是的，是的，对于根节点为-1），同一高度的所有节点一起计算低于它们的节点数。这使我们得出计数的节点数为节点数*树的高度 - 这是O(n logn)

- shapiro yaacov

---

你的答案在最坏情况下不是 O(n log n)（每个节点只有一个子节点，除了叶子节点）。我不会点踩，因为作者从未澄清他是在寻找最坏情况复杂度还是期望情况复杂度。此外，为了获得期望情况下的 O(n log n) 复杂度，有更简单的解决方案。 - Haozhun

@Haozhun - 我有点不同意。在你最坏的情况下，我们把所有的孩子都放在一条长枝上（在我的母语中，我们称之为“鞋带”、“绳子”或“字符串”），每个节点将从一个儿子那里收到一个空列表和另一个儿子的（长）列表。合并这些列表是O(1)。你还提到了其他方法？请详细说明。 - shapiro yaacov

让我们考虑这样的树：T(i) = tree(T(i-1), T(0)), T(0) = tree(nil, nil)。在这种情况下，T(m) 是一个具有 m*2+1 个节点的树，并且深度为 m。 - Haozhun

@Haozhun - 你说得对 - 那个例子的时间复杂度将会是 O(n^2)。那么你所提到的解决方案是什么呢？ - shapiro yaacov

Answer 3

如果对于每个节点，我们都维护一个独立的二叉搜索树(BST)，其中包含以该节点为根的子树的节点。

对于位于第k层的节点v，合并两个具有O(n/2^(k+1))个元素的子树v.left和v.right的时间为O(n/2^k)。在形成该节点的BST之后，我们可以仅通过计算BST的右（传统上）子树中的元素来在O(n/2^(k+1))的时间内找到v.bigger。总结一下，对于位于第k层的单个节点，我们有O(3*n/2^(k+1))个操作。共有2^k个第k级节点，因此我们有O(2^k*3*n/2^(k+1))，简化为O（n）（去掉3/2常数）。第k层的操作数量为O（n）。有log(n)层，因此总操作次数为O(n*log(n))。

- Selçuk Cihan

---

现在计算一下最坏情况下你需要存储多少个节点。它将是O(N^2)。 - SashaMN

@SashaMN 我不明白你的意思，你是在指空间复杂度吗？你不必同时维护所有的BST，一旦形成一个层级，你可以丢弃下面一层（值更低的层级）的BST。 - Selçuk Cihan

虽然我不同意这个踩踏，但我可以解释一下 @SashaMN 在评论中的意思。你的解决方案假设树是相当平衡的，即树的深度是 O(log N)，这并不一定是真的。（OP没有说。）如果没有这个假设，你的解决方案就是 O(N^2)。 - Haozhun