algorithm - 红黑树的直觉

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

最佳答案

假设您按顺序插入以下项来创建一个普通的二叉树：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)。不同类型的平衡二叉树（avl树、2-3树等）使用不同的簿记技术来保持相同的属性。