【数据结构】红黑树详解

目录

前言：

红黑树的概念：

红黑树的性质:

红黑树节点的定义：

红黑树的插入：

情况1：cur为红，p为红，g为黑，u存在且为红 

情况2：cur为红，p为红，g为黑，u不存在或者u为黑（p和cur都在其父亲节点同一侧）

情况3：cur为红，p为红，g为黑，u不存在或者u为黑（p和cur在其父亲节点的不同侧）

红黑树验证：

AVL树和红黑树的比较：

红黑树应用：

结语：

---

前言：

如果有需要文章源码的友友请前往：红黑树源码

找到RBTree即红黑树源码。

红黑树的概念：

红黑树（RBTree），是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

下图就是一颗红黑树。

红黑树的性质:

（1）最长路径最多是最短路径的2倍。

（2）每个结点不是红色就是黑色。

（3）根节点是黑色的 。

（4） 如果一个节点是红色的，则它的两个孩子结点是黑色的（没有2个连续的红色节点） 

（5）对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

（6）每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。

红黑树节点的定义：

红黑树采用孩子双亲表示法，多了一个表示颜色的枚举类（只有BLACK和RED）.

public class RBTreeNode {
    public int val;
    public RBTreeNode left;
    public RBTreeNode right;
    public RBTreeNode parent;
    public COLOR color;
    public RBTreeNode(int val){
        this.val = val;
        color = COLOR.RED;
    }
}

其中COLOR是枚举类型具体代码如下： 

public enum COLOR{
    RED,BLACK
}

在看到上面红黑树的构造方法后，不知道友友们有没有对把新节点设置成红色感到疑惑尼？ 

提问：在节点的定义中，为什么要将节点的默认颜色给成红色的？

答：这是因为根据上面给出的性质（5），红黑树从某节点到其后代叶节点的路径上的黑色节点个数相同，那么这个时候如果直接插入一个黑色节点，那么为了维护性质（5）必须要在别的叶节点后面也插入黑色节点，但是我们本意是插入一个节点，故不能插入黑色节点。至于插入红色节点可能会违反性质（4）我们只要调节一下颜色即可。

红黑树的插入：

红黑树是在二叉搜索树的基础上，加上其平衡限制条件，因此红黑树的插入可分为两步：

（1）按照二叉搜索的树规则插入新节点。

（2）检测新节点插入后，红黑树的性质是否造到破坏。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整，但当新插入节点的双亲节点颜色为红色时，就违反了性质（4）不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

在这之前我们先来个规定