假设我们表示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

它将如何影响树的高度?

最佳答案

要回答问题的第一步,高度不会O(log n)考虑一个节点为n的树,该树退化为一个列表;对于每个节点u,左子树为空,每个节点(除了单个叶)都有一个非空的右子树,如下图所示。

 a
  \
   b
    \
     c

不平等
leftheight(u) ≤ rightheight(u) + c

对于每个常量c,都保持不变,但树的高度是n

10-07 19:07
查看更多