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

Question

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

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

Answer 1

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

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

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

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

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