你如何保持普通的二叉树（不是 BST）平衡？
How would you keep an ordinary binary tree (not BST) balanced?
我知道使用旋转来保持二叉搜索树 balanced/self-balancing 的方法。
我不确定我的案子是否需要那么复杂。我不需要像自平衡 BST 那样维护任何排序顺序 属性。我只有一个普通的二叉树，我可能需要删除节点或插入节点。我需要尝试在树上保持平衡。为了简单起见，我的二叉树类似于线段树，每删除一个节点，从根到该节点的路径上的所有节点都会受到影响（在我的例子中，它只是节点值的一些减法） .同样，每插入一个节点，从根节点到插入节点的最终位置的所有节点都会受到影响（这次是对节点值的加法）。
保持这样一棵树平衡的最直接的方法是什么？它不需要像 AVL 树那样严格地保持高度平衡，但像 RB 树或平衡性稍差的东西也是可以接受的。
平衡非 BST 时，要问的大问题是
Can your tree efficiently support rotations?
某些类型的二叉树，如 k-d 树，具有特定的逐层结构，使得旋转不可行。其他的，比如范围树，在每个节点中都有辅助元数据，轮换后更新起来很昂贵。但是如果你能处理轮换，那么你几乎可以使用任何平衡策略。最简单的选择可能是在 treap 上对树建模：将随机选择的权重字段放入每个节点，然后在插入期间向上旋转新添加的叶子，直到其权重小于其父节点。要删除，请重复旋转节点及其较轻的子节点，直到它成为叶子，然后删除它。
如果您不能支持轮换，您将需要一个不需要轮换的重新平衡策略。也许最简单的选择是在替罪羊树之后为你的树建模，其工作原理是延迟检测太深的节点以致于树无法平衡，然后将可能的最小不平衡子树重建为完美平衡的树以将所有内容恢复到命令。一旦节点数量下降了某个常数因子，就会通过重建整棵树来处理删除。
如果一个新节点不必插入到特定点——可能由它自己的值和树中的值决定——但你是完全自由的选择它的位置，然后您可以将树的形状保持为 complete tree:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
数组是完整树的一种非常有效的数据结构，因为您可以在广度优先遍历中按顺序存储节点。因为给出的树是完整的，数组没有空隙。这种结构常用于heaps:
Heaps are usually implemented with an array, as follows:
- Each element in the array represents a node of the heap, and
- The parent / child relationship is defined implicitly by the elements' indices in the array.
Example of a complete binary max-heap with node keys being integers from 1 to 100 and how it would be stored in an array.
In the array, the first index contains the root element. The next two indices of the array contain the root's children. The next four indices contain the four children of the root's two child nodes, and so on. Therefore, given a node at index i, its children are at indices 2i + 1 and 2i + 2, and its parent is at index floor((i-1)/2). This simple indexing scheme makes it efficient to move "up" or "down" the tree.
运营
在您的情况下，您可以按如下方式定义 insert/delete 操作：
- Insert：将节点追加到数组末尾。然后执行其祖先所需的突变（如您在问题中所述）
- 删除：将要删除的节点替换为当前位于数组末尾的节点，并将数组减1。进行后续需要的更新来自这两个位置的变化——因此从根到节点的两条路径受到影响。
我知道使用旋转来保持二叉搜索树 balanced/self-balancing 的方法。
我不确定我的案子是否需要那么复杂。我不需要像自平衡 BST 那样维护任何排序顺序 属性。我只有一个普通的二叉树，我可能需要删除节点或插入节点。我需要尝试在树上保持平衡。为了简单起见，我的二叉树类似于线段树，每删除一个节点，从根到该节点的路径上的所有节点都会受到影响（在我的例子中，它只是节点值的一些减法） .同样，每插入一个节点，从根节点到插入节点的最终位置的所有节点都会受到影响（这次是对节点值的加法）。
保持这样一棵树平衡的最直接的方法是什么？它不需要像 AVL 树那样严格地保持高度平衡，但像 RB 树或平衡性稍差的东西也是可以接受的。
平衡非 BST 时，要问的大问题是
Can your tree efficiently support rotations?
某些类型的二叉树，如 k-d 树，具有特定的逐层结构，使得旋转不可行。其他的，比如范围树，在每个节点中都有辅助元数据，轮换后更新起来很昂贵。但是如果你能处理轮换，那么你几乎可以使用任何平衡策略。最简单的选择可能是在 treap 上对树建模：将随机选择的权重字段放入每个节点，然后在插入期间向上旋转新添加的叶子，直到其权重小于其父节点。要删除，请重复旋转节点及其较轻的子节点，直到它成为叶子，然后删除它。
如果您不能支持轮换，您将需要一个不需要轮换的重新平衡策略。也许最简单的选择是在替罪羊树之后为你的树建模，其工作原理是延迟检测太深的节点以致于树无法平衡，然后将可能的最小不平衡子树重建为完美平衡的树以将所有内容恢复到命令。一旦节点数量下降了某个常数因子，就会通过重建整棵树来处理删除。
如果一个新节点不必插入到特定点——可能由它自己的值和树中的值决定——但你是完全自由的选择它的位置，然后您可以将树的形状保持为 complete tree:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
数组是完整树的一种非常有效的数据结构，因为您可以在广度优先遍历中按顺序存储节点。因为给出的树是完整的，数组没有空隙。这种结构常用于heaps:
Heaps are usually implemented with an array, as follows:
- Each element in the array represents a node of the heap, and
- The parent / child relationship is defined implicitly by the elements' indices in the array.
Example of a complete binary max-heap with node keys being integers from 1 to 100 and how it would be stored in an array.
In the array, the first index contains the root element. The next two indices of the array contain the root's children. The next four indices contain the four children of the root's two child nodes, and so on. Therefore, given a node at index i, its children are at indices 2i + 1 and 2i + 2, and its parent is at index floor((i-1)/2). This simple indexing scheme makes it efficient to move "up" or "down" the tree.
运营
在您的情况下，您可以按如下方式定义 insert/delete 操作：
- Insert：将节点追加到数组末尾。然后执行其祖先所需的突变（如您在问题中所述）
- 删除：将要删除的节点替换为当前位于数组末尾的节点，并将数组减1。进行后续需要的更新来自这两个位置的变化——因此从根到节点的两条路径受到影响。