如何保持普通二叉树（非BST）的平衡？

Question

我知道使用旋转保持二叉搜索树平衡/自平衡的方法。

我不确定我的情况是否需要那么复杂。我不需要像自平衡BST那样维护任何排序顺序属性。我只是有一个普通的二叉树，我可能需要删除节点或插入节点。我需要尝试在树中保持平衡。为简单起见，我的二叉树类似于段树，每次删除一个节点时，从根到这个节点的路径上的所有节点都会受到影响（在我的情况下，这只是节点值的一些减法）。类似地，每次插入一个节点时，从根到插入节点的最终位置的所有节点都将受到影响（这次添加了节点值）。

要保持这样一棵树的平衡，最简单的方法是什么？它不需要像AVL树那样严格地保持高度平衡，但像RB树或稍微不平衡的树这样的东西也是可以接受的。

Answer 1

在平衡非BST时，要问的一个大问题是

你的树能有效地支持旋转吗？

某些类型的二叉树，比如k-d树，具有特定的逐层结构，使得旋转不可行。其他的，比如范围树，在每个节点中都有辅助元数据，在旋转后更新成本很高。但是如果你能处理旋转，那么你可以使用几乎任何一种平衡策略。最简单的选择可能是在踏板上为你的树建模：在每个节点中放入一个随机选择的权重字段，然后在插入过程中，向上旋转你新添加的叶子，直到它的权重小于它的父节点。要删除，用它较轻的子节点重复旋转节点，直到它是一个叶子，然后删除它。

如果你不能支持轮换，你需要一个不需要轮换的再平衡策略。也许最简单的选择是以替罪羊树为基础对你的树进行建模。替罪羊树的工作原理是，懒洋洋地检测一个太深的节点，使树无法平衡，然后将最小的不平衡子树重建成一棵完全平衡的树，使一切恢复正常。一旦节点数量下降了某个常数因子，就可以通过重建整个树来处理删除。

Answer 2

如果一个新节点不必插入到特定的位置——可能由它自己的值和树中的值决定——但您完全可以自由选择它的位置，那么您可以将树的形状保持为完整的树：

在一个完整的二叉树中，除了最后一层之外，每一层都是完全填充的，最后一层中的所有节点都尽可能地左移。

对于一棵完整的树来说，数组是一种非常有效的数据结构，因为您可以按广度优先遍历的顺序存储节点。因为树是完整的，所以数组没有间隙。此结构通常用于堆：

堆通常使用数组实现，如下所示：

• 数组中的每个元素代表堆的一个节点，并且
• 父/子关系由数组中元素的索引隐式定义

一个完整的二进制最大堆的示例，其中节点密钥是1到100之间的整数，以及如何将其存储在数组中。

在数组中，第一个索引包含根元素。数组的下两个索引包含根的子级。接下来的四个索引包含根的两个子节点的四个子节点，以此类推。因此，给定索引i处的节点，其子节点位于索引2i 1和2i 2处，其父节点位于索引层（（i-1）/2）。这种简单的索引方案可以有效地“向上”或“向下”移动树。

在您的情况下，您将定义插入/删除操作如下：

• 插入：将节点附加到数组的末尾。然后对其祖先进行所需的突变（如您在问题中所述）
• 删除：将要删除的节点替换为当前位于阵列最末端的节点，并将阵列缩短1。根据这两个位置的更改进行所需的更新，从而影响从根到节点的两条路径