java - 平衡与不平衡二叉树 - 需要澄清

Question

我需要澄清一下，这可能是一个非常愚蠢的问题，我已经进行了研究，但找不到我的问题的明确答案。我的问题是，平衡二叉树和不平衡二叉树之间有哪些属性差异？我在一次采访中被问到这个问题（java问题），我已经向面试官解释了差异，但是他提到他想知道区分两者的属性（二叉树 - 不平衡与平衡）。

如果有人可以为我澄清这一点，我将不胜感激。

标签： javabinary-tree

Answer 1

通过“属性”，我相信面试官是在询问 Big-O 性能的复杂性。

对于平衡树，访问¹是O(log n)。
对于不平衡树，访问¹是O(n)（最坏情况）。

这是因为从排序数据构建的不平衡树实际上与链表相同。

两种树的空间复杂度相同。

^{1) 访问包括查找、插入和删除操作。}