红黑树的直觉

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