algorithm - 红黑树的直觉

Question

我想了解红黑树的工作原理。我了解算法，如何在插入和删除操作后修复属性，但我不清楚。为什么红黑树比二叉树更平衡？我想理解直觉，为什么旋转和固定树属性会使红黑树更加平衡。

谢谢。

Answer 1

假设您通过按顺序插入以下项来创建普通二叉树:1、2、3、4、5、6、7、8、9。每个新项将始终是树中最大的项，并且因此插入为最右边的可能节点。你的“树”看起来像这样:

1
 \
  2
   \
    3
     .
      .
       .
        9

在红黑树(或任何类型的平衡二叉树)中执行的旋转确保任何节点的左子树或右子树都不会明显比另一个更深(通常，高度差为 0 或 1，但任何常数因子都可以。)这样，运行时间取决于树的高度 h 的操作总是 O(lg n)，因为旋转保持 h = O(lg n)，而在上面显示的最坏情况下 h = O(n)。

特别是对于红黑树，节点着色只是一种簿记技巧，有助于证明旋转始终保持 h = O(lg n)。不同类型的平衡二叉树(AVL 树、2-3 树等)使用不同的簿记技术来维护相同的属性。