红黑树再平衡
Red Black Trees Rebalancing
我想在我的树中插入 7 个项目 -3、-2、-1、0、1、2 和 3。当我按此顺序插入时，我得到了一个高度为 3 的平衡良好的树而没有进行旋转： 0、-2、2、-1、1、-3、3。但是当我按升序插入所有项目时，根节点的右侧部分会重新平衡，但根节点的左侧部分不会。我见过的所有重新平衡算法都是从插入节点到根节点进行重新平衡，然后它们停止。他们不应该继续到根节点的对面吗？而且我觉得如果我按升序插入很多项目（比如 0 到 100），情况会变得更糟。最后树是平衡的，但没有优化高度。
None 的平衡二叉搜索树（R/B 树、AVL 树等）提供了绝对平衡，即其中的 none 提供了可能的最小高度。这是因为不可能快速进行 "complete" 重新平衡。如果我们希望始终保持尽可能低的高度，则树操作通常需要进行大量的重新平衡，因此重新平衡在 O(log N) 中不起作用。结果，所有操作（插入、更新、删除等）也将在 O(log N) 时间内无法正常工作，这将破坏平衡树的整个概念。
什么平衡树做保证是对树高的要求不那么严格：树高是O(log N)，也就是C*log N一些常数 C。所以这棵树并不能保证是理想平衡的，但平衡总会离理想不远。
我想在我的树中插入 7 个项目 -3、-2、-1、0、1、2 和 3。当我按此顺序插入时，我得到了一个高度为 3 的平衡良好的树而没有进行旋转： 0、-2、2、-1、1、-3、3。但是当我按升序插入所有项目时，根节点的右侧部分会重新平衡，但根节点的左侧部分不会。我见过的所有重新平衡算法都是从插入节点到根节点进行重新平衡，然后它们停止。他们不应该继续到根节点的对面吗？而且我觉得如果我按升序插入很多项目（比如 0 到 100），情况会变得更糟。最后树是平衡的，但没有优化高度。
None 的平衡二叉搜索树（R/B 树、AVL 树等）提供了绝对平衡，即其中的 none 提供了可能的最小高度。这是因为不可能快速进行 "complete" 重新平衡。如果我们希望始终保持尽可能低的高度，则树操作通常需要进行大量的重新平衡，因此重新平衡在 O(log N) 中不起作用。结果，所有操作（插入、更新、删除等）也将在 O(log N) 时间内无法正常工作，这将破坏平衡树的整个概念。
什么平衡树做保证是对树高的要求不那么严格：树高是O(log N)，也就是C*log N一些常数 C。所以这棵树并不能保证是理想平衡的，但平衡总会离理想不远。