algorithm - 红黑树再平衡

Question

我想在我的树中插入 7 个项目 -3、-2、-1、0、1、2 和 3。当我按以下顺序插入时，我得到了一个高度为 3 的平衡良好的树而没有进行旋转:0， -2、2、-1、1、-3、3。但是当我按升序插入所有项目时，根节点的右侧部分会重新平衡，但根节点的左侧部分不会。我见过的所有重新平衡算法都是从插入节点到根节点进行重新平衡，然后它们停止。他们不应该继续到根节点的对面吗？而且我觉得如果我按升序插入很多项目(比如 0 到 100)，情况会变得更糟。最后树是平衡的，但没有优化高度。

Answer 1

没有一种平衡的二叉搜索树(R/B 树、AVL 树等)提供绝对平衡，也就是说它们都没有提供最小的可能高度。这是因为不可能快速进行这种“完整”的再平衡。如果我们希望始终保持尽可能低的高度，则通常需要对树操作进行大量重新平衡，因此重新平衡在 O(log N) 中不起作用。结果，所有操作(插入、更新、删除等)也不会在 O(log N) 时间内完成，这将破坏平衡树的整个想法。

平衡树做保证的是对树高的不那么严格的要求:树高是O(log N)，即C *log N 为一些常量 C。所以这棵树并不能保证达到理想的平衡，但平衡总是离理想不远。