algorithm - 计算二叉树中的节点数 O(logn)^2

Question

我有一个问题，我需要在时间复杂度为 ) 例如 (log of n )^2 中找到完整树中的节点数
O((log(n))^2，我的目标是
找出h哪个是h= log n(树的高度，总是向左移动它是一个完整的树）然后来到每个节点h-1并检查它是否有一个右节点，如果有，那么它必须有一个左节点（因为完整的树）如果它没有然后检查它是否有一个左节点，就像这样计算节点的数量。

问题是我认为这是O(n)因为h = log(n)这个高度的节点数量是这样的2^(h-1)，所以整个过程是O(n)而不是O( (log n)^2) ..

的输出 为 12，因为它有 12 个节点，时间复杂度为 O((log n)^2)

我会很感激帮助！谢谢你。

标签： algorithmbinary-treebig-o

Answer 1

left首先，通过遍历指针来计算到最左边叶子的距离。然后对right指针做同样的事情。如果两个数字都是n，那么您将拥有一棵具有 2^n - 1 个节点的完美树。

否则，它们不相等。然后第一个计数是一些数字n+1，第二个是n。我们需要探测 - 正如其他人所说的那样使用二分搜索 - 完整n的 -deep 节点层（将根计算为第 1 层）以找到最左边的具有 0 个或 1 个子节点的节点。有 2^(n-1) 个节点要探测。在示例中，n=3，因此我们正在探测 4 个节点。

我们可以通过考虑数字 0..2^(n-1) - 1 中的位来探测该层。在示例中，这是 0..3（即 n-2 位）。在从根到叶的遍历中，0 位表示“向左走”。1 表示“向右走”。出于下面讨论的原因，您希望使用从根到叶的从最高到最低的位（在示例中，位 1,0）。不难看出，使用 0..2^(n-1) - 1 作为路径遍历“指令”，您将从左到右到达该层中的每个顶点。例如，2 有 10 位。这意味着从根开始，从右到左，这会将您带到 F。

但当然你不想搜索 n 层中的每个顶点，因为这会使你的搜索 O(n)。相反，使用二进制搜索。首先尝试 [0..2^(n-1) - 1] 中点的“指令”。如果您找到 2 个孩子，则将搜索括号减少到大于中点的值。如果您找到 0 个孩子，则价值较小。以这种方式继续，直到您找到具有 1 个子节点的节点或括号大小为 1 并且有 0 个子节点。后者意味着您在图层中找到了没有子节点的最左侧节点。

现在我们可以很容易地找到孩子的总数。树的向下到第 n 层的部分有 2^(n-1) - 1 个节点，将您带到最终搜索节点的“指令”告诉您在第 n+1 层中有多少个节点。这些一起告诉你最终的答案。我会让你弄清楚最后的细节。