red_black_tree.md

自平衡二分搜索树：红黑树（Red-black Tree）

图：红黑树示例

红黑树具有如下性质：

1. 每个节点非红即黑。
2. 根节点为黑色。
3. 叶子节点（最后NIL节点）为黑色。
4. 如果一个节点为红色，则其子节点为黑色。
5. 从任意节点到叶子节点，经过的黑色节点数目相同。

B 类树：2-3 树

• 2-3 树满足二分搜索树的基本性质。
• 2-3 树是一颗绝对平衡的树。

2节点      3节点
{a}       {b,c}
/ \       / | \

注：2-3 树的两类节点

# Add 42
{42}

# Add 37
{37,42}

# Add 12
{12,37,42}             {37}
            ----->    /    \
                    {12}   {42}
# Add 18
    {37}
  /      \
{12,18} {42}

# Add 6
    {37}                {37}                  {12,37}
  /      \     ---->   /    \     ---->      /   |   \
{6,12,18} {42}       {12}  {42}            {6}  {18} {42}
                     /  \
                   {6}  {18}

# Add 11
     {12,37}
    /   |   \
{6,11} {18} {42}

# Add 5
      {12,37}                     {12,37}
    /    |    \     ----->      /    |    \
{5,6,11} {18} {42}            {6}   {18}  {42}
                              /  \
                            {5} {11}
            {6,12,37}                      {12}
----->    /   |   |   \     ----->       /       \
        {5} {11} {18} {42}             {6}      {37}
                                       / \       / \
                                     {5} {11} {18} {42}

注：2-3 树添加节点

红黑树与 2-3 树的等价性

# 2-3 树
2节点      3节点
{a}       {b,c}
/ \       / | \

# 红黑树
 a{B}        b{B} - c{B}          c{B}
/ \         / \      \    ---->   / \
                                 b{R}
                                / \

注：红黑树与 2-3 树的等价性

再看红黑树的性质。

• 性质 1：每个节点非红即黑。

红黑树定义。

• 性质 2：根节点为黑色。

红黑树对应到 2-3 树的两类节点中，其根节点均是黑色。

• 性质 3：叶子节点（最后NIL节点）为黑色。

红黑树定义。如果树为空树，也满足第二条性质。

• 性质 4：如果一个节点为红色，则其子节点为黑色。

红黑树红色节点对应到 2-3 树 3 节点的左侧，2-3 树 3 节点的子节点不是 2 节点就是 3 节点，对应回红黑树中，即为黑色节点。

• 性质 5：从任意节点到叶子节点，经过的黑色节点数目相同。

2-3 树是绝对平衡树，从任意节点到叶子节点所经过的节点数目都相同，对应到红黑树中即为性质5。

红黑树操作

当我们对一棵平衡二叉搜索树进行插入、删除操作时，很可能会让这棵树失衡（最坏可能导致所有祖先结点失衡，但是父结点和非祖先结点都不可能失衡），为了达到平衡，需要对树进行平衡维持。而红黑树能够达到自平衡，靠的就是左旋、右旋、变色操作。