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

Question

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

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

Answer 1

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

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

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

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

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