我开始研究如何平衡面试中的树，我有一些问题
有可能平衡一个普通的二叉树吗？如果是，应该使用哪种算法？
我需要使用avl或红黑树来获得平衡树吗？这些是怎么工作的？你能提供尽可能简单的解释这些的链接吗？
我读了一些关于旋转，重量的书，但是我现在有点困惑
最佳答案
好。。。AVL和红黑树是“正常的二叉树”，它们是平衡的，并保持这种平衡（对于“平衡”的某些定义）我不是一个能自己解释算法的计算机科学老师，我想你不是在找维基百科上的剪贴画：-）
现在，对于平衡二叉树：如果树是一个搜索树（即“sorted”，但是“balanced”如果不是真的有那么多意义的话），你可以重新创建树。最简单的算法是使用一个数组，将树中的所有元素按排序顺序排列（很容易从无序遍历中获得）。然后围绕这个基本思想构建一个算法：
取数组的中间元素作为树的根。这将创建一个树节点和两个数组“left”和“right”，这两个数组用于形成左子树和右子树
递归地应用相同的算法，从“左”数组创建树，从“右”数组创建树。这两棵树成为父节点的子节点。
当数组有偶数个元素时，您可能需要小心：没有明显的“中间元素”，删除两个候选元素中的一个将创建不同大小的数组。我懒得进一步分析，看看这是否能抵消整个平衡的影响。
当然，每次更改树时都这样做并不是一个好主意；您真的希望使用像avl这样的自平衡树来实现这一点。在创建树之后执行此操作可能也没有那么有用：您可以只使用数组本身并对其执行二进制搜索，而不是生成树数组只是二叉树的另一种形式。。。
编辑：很多计算机科学家花费大量时间开发在某些情况下性能良好的数据结构和算法是有原因的。滚动你自己版本的平衡二叉树不太可能打败这些。。。