红黑树的直觉

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树等)使用不同的簿记技术来维护相同的属性。

Answer 2

为什么红黑树比二叉树更平衡？

因为红黑树保证O(logN)的插入、删除和查找任何操作顺序的性能。

为什么旋转和固定树属性使红黑树更加平衡？

除了任何二进位搜索树必须遵守的一般属性外，红-黑树还服从以下属性：

1. 没有一个节点有两个红色链接连接到它。
2. 从根到空链接的每一条路径都有相同数量的黑色链接。
3. 红色链接向左倾斜。

现在我们要证明以下命题：

Proposition.在最坏情况下，树高为≤2 lg N。

证明.由于从根到任何空链接的每一条路径都有相同数量的黑色链接，并且两个红色链接从来不在一行中，所以在最坏的情况下，最大高度总是小于或等于2logN。

Answer 3

虽然很晚了，但由于我最近正在学习RBT，并且一直在挣扎于为什么某种神奇的旋转和着色平衡了树的直觉，并且思考着与OP相同的问题。

为什么旋转和固定树属性使红黑树更加平衡。

在进行了几天的“研究”之后，我有了“尤里卡”的时刻，并决定把它写得详细些。我不会在这里复制粘贴，因为有些格式是不正确的，所以任何感兴趣的人都可以从github查看它。我试着用很多图像和模拟来解释。希望有一天它能帮助那些碰巧在这个线程中搜索相同问题的人：)