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