红黑树算法、原理分析

红黑树

Red-Black Tree，自平衡(整体较平衡)的二叉查找树，查找性能较高。

五个重要特性：

• 节点为红色或黑色
• 根为黑色
• 叶子（NIL节点）节点为黑色
• 每个红色节点必须有两个黑色子节点（从每个叶子到根的所有路径上不能有连续的两个红色节点）
• 从任一节点到其每个叶子（NIL节点）的所有简单路径都包含相同数目的黑色节点

以上性质保证了红黑树具有：
从根到叶子的最长可能路径不多于最短可能路径的两倍（因为红黑树中最短可能路径都是黑色节点，最长可能路径为红黑节点交替，而两者由于性质4具有相同数量的黑色节点）
这一特征。从而使其在大致上是平衡的，插入、删除、查找操作的最坏情况与树的高度成比例，不会出现左右子树极其失衡的情况

下图为一红黑树：

红黑树插入操作

插入操作分为两步：

• 找到新节点在红黑树中插入的位置
• 调整红黑树，使其满足红黑树的5个特性

重点为第二步，调整红黑树的方式也可分为两种

• 重新定色(recolor)
• 旋转操作(rotation)

首先recolor，若调整颜色后仍无法满足红黑树的性质，则需要进一步rotation。

具体方式

• 1.假设新插入节点为X，标记其为红色（保证性质5）

• 2.若X为root，标记为黑色

• 3.若X父节点为黑色，无需处理

• 4.若X父节点为红色：

  • ① 若X叔父节点也为红色：
    • 将父节点与叔父节点标记为黑色
    • 将祖父节点标记为红色
    • 对X的祖父节点重复2、3操作

  

  • ② 若X叔父节点为黑色，可分为四种情况：
    • 左左（X为父P左节点，X父P为祖父G左节点）
      对祖父G进行右旋，然后交换父P和祖父G的颜色

• • • 左右（P为G左节点，X为P右节点）
      先对P进行左旋，用X节点替换P节点，再应用左左情况进行处理

• • • 右右（P为G右节点，X为P右节点）
      对G进行左旋，然后交换P、G的颜色

• • • 右左（P为G右节点，X为P左节点）
      先对P进行右旋，用X节点替换P节点，再应用右右情况进行处理

红黑树删除操作

基本思路

• 删除节点：
  • 若删除的节点无子节点，则直接删除
  • 若删除的节点有一个子节点，删除节点后，子节点顶替
  • 若删除的节点有两个子节点，可将问题转换为删除另一个只有一个子节点的节点
• 节点删除后，调整红黑树使其满足性质

删除带有两个子节点的节点

• 在删除有两个子节点的节点时，可以去寻找左子树的最大元素或者右子树的最小元素，将其值复制给要删除的节点（颜色不复制），然后删除找到的这个节点。

如下图所示：

（图中使用的是左子树最大元素6替换8，实际也可用右子树最小值来替换）

• 删除有一个子节点的节点操作（删除X，其子节点为N）

  • X为红色，删除后用N替换，红黑树性质未破坏

  

  • X为黑色：
    • 子节点N为红色
      删除X后用N替换，由于经过N的路径上少了一个黑色节点，所以将其改为黑色
    • 子节点N为黑色：
      • 1.节点X为根
        N成为新根，在所有路径上少了一个黑色节点， 但也多了一个黑色根，故红黑树性质未破坏
      • 2.兄弟节点S为红色
        对节点P左旋，互换P和S的颜色，然后按照步骤4、5、6进行处理

  

  • • 3.节点P、S、S的子节点均为黑色
      将节点S改为红色，转换为步骤2处理

  

  • • 4.节点P是红色，节点S和S子节点为黑色
      交换节点p和S的颜色即可。经过S的路径上黑色节点数不变，经过N的路径新增黑色节点P，正好填补了删除的黑色节点X

  

  • • 5.节点S为黑，S左子节点为红，S右子节点为黑，且N是P的左子节点
      对节点S右旋，交换L和S的颜色，然后按照步骤6处理

  

  • • 6.节点S为黑，S右子节点为红，N为P左子节点
      对节点p左旋，交换S和P的颜色，并将R改为黑色。如此，路径经过节点N、L、R的黑色数目保持不变

  

红黑树源码

...