平衡二叉树 VS 非平衡二叉树——需要澄清

Question

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

- user12489040

---

您需要什么方面的澄清？您是否找到了一些关于平衡二叉树的资源，但是没有理解？ - kaya3

“properties” 究竟是什么意思？ - user12489040

这有点模糊，可能涉及到实现细节、操作的时间复杂度、定义树是否“平衡”的正式条件等。我建议您对所有这些方面进行调查，如果在面试中再次遇到这种问题，请向面试官要求澄清。 - kaya3

我明白了，非常感谢您的解释。我一定会研究这些内容，以防再次出现。好的，再次感谢！ - user12489040

只有一个“属性”可能不同，那就是每个节点下面的高度差异，在平衡树的情况下受到限制，在其他情况下则没有限制，这反过来导致了平衡树的性能上限。如果面试官真的是这样说的话，那么这是一个措辞不当的问题。 - user207421

谢谢您的澄清！但是，是的，我也这样认为。 - user12489040

Answer 1

通过“properties”，我认为面试官是在询问Big-O性能复杂度。

使用平衡树，访问¹的时间复杂度为O(log n)。
使用非平衡树，访问¹的时间复杂度为O(n)（最坏情况）。

这是因为由排序数据构建的非平衡树实际上等同于链表。

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

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

- Andreas

---

简单直接的谢谢！ - Mohamad Ghaith Alzin

Answer 2

我认为安德烈亚斯的回答很到位，但你需要了解二叉树和链表的内部工作原理才能欣赏它。似乎这就是面试官在考查你的内容：当他提到这个结构时，你知道他在说什么，并且能够轻松地遍历它以得出合理的答案吗？

思考这个问题的另一种方式是将焦点转移到平衡树上。什么使它保持平衡？对于每一层，左子树的高度与右子树的高度相同，因此该层的每个根节点都有两个节点或一个节点。不平衡的情况则相反。

现在你明白了不平衡和平衡树的样子，你可以开始比较它们的实现。二叉搜索的实现是什么？你不断将树减半直到找到目标位置。作为一个模式，每当你处理涉及减少输入数量一半的问题时，复杂度是log(N)，因为我们使用的是以x为底的对数。

log(aN) = x => a^x = N  

所以，平衡搜索树的最坏情况运行时间是O(log(N))，其中目标要么未找到，要么位于最后一个位置，你会将N个输入减半（log(N)）。对于不平衡的搜索树，最坏情况与目标未找到或位于最后一个位置相同，但由于树不平衡，你需要按线性方式遍历每个项目。因此，运行时间为O(N)。

不平衡树的运行时间与平衡树有何关系？如果考虑运行时间的顺序，O(N)比O(logN)慢，这就是为什么平衡树通常是更好的结构的原因。

- veron