红黑树插入后黑高度增加的场景及其他示例咨询

你提到的以黑色根起始、红叶子结尾的完美交替层级树确实是典型场景，但并非唯一会导致插入后黑高度增加的情况。核心判定标准是：插入操作触发的红-红冲突通过Case 1（父红且叔父红）持续向上传播至根节点，最终根节点先被染为红色，再强制染回黑色，从而使全树黑高度+1。

只要满足「插入路径上的每一层父节点的兄弟（叔父）均为红色」，就会触发冲突逐层上推至根，以下是两个非完美树的示例：

示例1：非对称的红节点分布树 #

黑（根）
       /   \
      红    红
     /  \   |
    红  红  红
   /
  红

• 插入操作：在最底层左红节点的左子树插入新红色节点。
• 冲突传播：
  1. 新节点父为红，叔父（父的兄弟）为红，触发Case 1：父与叔父变黑，祖父（第三层左红节点）变红。
  2. 祖父变红后，其父（第二层左红节点）为红，叔父（第二层右红节点）为红，再次触发Case 1：祖父的父与叔父变黑，根节点变红。
  3. 根节点强制染回黑色，全树黑高度增加1。

示例2：局部缺失叶子的红黑树 #

黑（根）
         /   \
        红    红
       /  \  /  \
      红  红 红  红
     /
    红

• 插入操作：在最底层左红节点的左子树插入新红色节点。
• 冲突传播：
  1. 新节点父为红，叔父为红，触发Case 1：父与叔父变黑，祖父（第三层左红节点）变红。
  2. 祖父变红后，其父（第二层左红节点）为红，叔父（第二层右红节点）为红，触发Case 1：祖父的父与叔父变黑，根节点变红。
  3. 根节点染回黑色，黑高度增加1。

这类场景的关键是插入路径上的每一层都存在红叔父节点，使得冲突通过Case 1持续向上传递，最终波及根节点，而非树的整体结构是否完美对称。

内容的提问来源于stack exchange，提问作者iSkull