algorithm - 计算树高提供了左树高和右树高的条件

Question

假设我们用 leftheight(u) 和 rightheight(u) 表示节点 u 的左右子树的高度。

现在如果我们有一个常量 c > 0 使得对于树 T 中的所有节点 u，我们有

leftheight(u) ≤ rightheight(u) + c

关于这棵树的高度可以说些什么？是 O(log n) 还是什么？

此外，如果条件已更改为:

leftheight(u)−c ≤ rightheight(u) ≤ leftheight(u) + c

它如何影响树的高度？

Answer 1

要回答问题的第一部分，高度不是 O(log n)。考虑一棵具有 n 节点的树，该树通过以下方式退化为列表；对于每个节点 u，左子树都是空的，每个节点(除了单叶节点)都有一个非空的右子树，如下图所示。

 a
  \
   b
    \
     c

不平等

leftheight(u) ≤ rightheight(u) + c

对于每个常量 c 都成立，但树的高度是 n。