红黑树 | LDK's Blog

概念

一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 (“RED” or “BLACK”)，用于确保树在插入和删除时保持平衡。

红黑树是 4 阶 B 树（2-3-4 树）的变体。

特点

红黑树本身也是二叉搜索树，具有所有二叉搜索树的特点。

一棵合法的红黑树必须遵循以下性质：

（节点颜色）所有节点为红色或黑色。
（根节点）根节点必须是黑色。
（叶子节点）NIL 节点（空叶子节点）都是黑色。
（红色节点）红色节点的左右子节点都为黑色（从每个NIL节点到根节点的路径上不能有连续的两个红色节点）。
（黑色节点）从任意节点到其所在子树的 NIL 节点的每条路径上的黑色节点数量相同（简称黑高）。

下图为一个合法的红黑树：

红黑树

扩展特点

最长路径不超过最短路径的两倍。
由上一特点可得：任一节点的左右子树的高度差不会超过2倍。

对比平衡二叉树：平衡二叉树要求左右子树高度相差不超过1，而红黑树要求左右子树高度差不超过2倍。由此看来平衡二叉树对平衡的要求更严格，插入时进行的旋转操作更多。

实现

插入

插入的新节点默认是红色节点。因为如果对一个红黑树插入一个黑色节点，无论黑色节点插在哪里，都会违反红黑树基本特点中的第5条（因为插入之前的红黑树肯定满足以上所有特点，但插入后一定会破坏第5条）。

那么在插入红色节点的情况下，可能会违反基本特点中的第4条特点（不能有两个连续的红色节点）。如果没有违反特点，则不需要调整。如果违反了特点，就需要进行旋转，分为三种情况：

新插入的节点是根节点：直接将根节点变黑（只有在插入之前树为空的情况下才会发生）。
新插入节点的叔叔节点（父节点的兄弟节点）是红色：
- 调整新插入的节点的父亲、叔叔、爷爷三个节点的颜色：红色变为黑色，黑色变为红色。
- 令爷爷节点当作新插入节点，重新判断（循环或者递归）。
新插入节点的叔叔节点是黑色：
- 判断LL, LR, RR, RL四种失衡类型，然后旋转。因为只有连续两个红色节点才需要旋转，所以可以确定新插入节点的父节点一定是红色的。据此判断失衡类型。
  - LL：
  - LR：
  - RR：
  - RL：

删除

删除操作是红黑树逻辑最复杂的操作，主要是删除黑色节点时，会导致被删除节点所在路径上的黑色节点数量减1，导致违反上述基本性质中的第5条性质。而删除红色节点则相对简单。

删除的情况分类

对被删除节点的情况进行分类。

被删除节点只有左孩子/只有右孩子

此时被删除节点一定为黑色节点，因为如果是红色节点，那么一定是左右子树都存在或者左右子树都不存在，否则就会违背上述第5条性质。

确定了被删除节点一定为黑色后，可以推得：被删除节点的仅有的孩子节点一定是红色。因为被删除节点的其中一个子树是空的，那么剩下的那个非空的子树中一定不会存在黑色节点，否则就会违反基本性质中的第5条性质。

具体情况和对应操作见下图：

可见，只需要将唯一的那个子节点向上提升，替代要删除的节点即可。
被删除节点左右孩子都有

可以转换为其他两种情况：用要删除的节点的右子树上的最小节点替换要删除的节点，然后删除右子树上的最小节点。如此递归，可转化为另外两种情况。
被删除节点没有孩子
- 被删除节点为黑色：
  
  因为删除了黑色节点后，从该节点到根节点的路径上少了一个黑色节点，破坏了第5条性质，所以需要观察兄弟节点和父亲节点颜色，分情况处理这缺失的一个黑色节点：
  - 兄弟节点为黑色：
    - 并且兄弟节点有一个与它方向一致的红色节点。父亲节点颜色随意:
      
      方向一致：指的是brother是father的左子节点并且son是brother的左子节点，或者brother是father的右子节点并且son是brother的右子节点。即：father、brother、son<三点共线>。
      
      此时执行左旋(RR情况下)或者右旋(LL情况下)。并且在旋转之前，先按步骤进行变色：son变为黑色，brother变为father的颜色，father变为黑色。
    - 并且兄弟节点有一个与它方向相反的红色节点，同时兄弟节点没有与它方向一致的红色子节点。父亲节点颜色随意：
      
      方向相反：参考方向一致。father、brother、son三点不共线，即认为是方向相反。
      
      先让兄弟节点son变为父亲节点father的颜色，再让父亲节点father颜色变黑。最后分析情况执行左右双旋或者右左双旋。
    - 并且兄弟节点没有红色子节点。父亲节点为红色：
      
      兄弟节点变红，父亲节点变黑。
    - 并且兄弟节点没有红色子节点。父亲节点为黑色：
      
      兄弟节点变为红色，双黑标记上移至父亲节点（将父亲节点当作被删除节点）。递归判断父亲节点的情况。
  - 兄弟节点为红色：
    
    此时兄弟节点没有红色子节点，也不可能有红色子节点（性质4）。同时父亲节点必定为黑色（性质4）。执行操作：
    
    兄弟节点变黑色，父亲节点变红色。然后左旋或者右旋父亲节点。（将父亲节点下移，兄弟节点上移）
- 被删除节点为红色：
  
  最简单的情况。直接删除该节点。（因为没有左右孩子，并且不影响红黑树基本性质，所以可以直接删除，不做任何额外操作）