红黑树

红黑树

概述

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫•贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。

五个性质

红黑树的五个性质：

1. 每个结点或是红色的，或是黑色的。
2. 根结点是黑色的。
3. 每个叶结点(NIL)是黑色的。
4. 如果一个结点是红色的，则它的两个子结点都是黑色的。
5. 对每个结点，从该结点到其所有叶子结点的简单路径上，均包含相同数目的黑色结点。

插入

按照BST的规则增加结点并标记它为红色，为什么是红色呢？原因如下：

• 若设置为黑色，就会导致根到叶子的路径上有一条路径上多了一个黑色结点，很难调整(性质5)。
• 设置为红色结点后，可能会导致出现两个连续红色结点的冲突，那么可以通过颜色调换和数旋转来调整(性质4)。

1.新结点位于树根

新节点位于树根，直接变为黑色即可。

2.新结点的父结点为黑色(黑父)

该条件下，插入一个红色结点不会影响红黑树的平衡。

• 新增结点为红色的，任何一条简单路径都没有增加黑色结点的个数。
• 该种情况较为常见，从而使得红黑树需要旋转调整的几率相对AVL树少一些。
  

3.新结点的父结点为红色(红父)

新结点的父结点是红色，祖父结点一定是黑色，需要根据叔叔结点来决定进行什么样的操作。

叔叔结点也是红色

• 祖父结点变为红色。
• 父结点变为黑色。
• 叔叔结点变为红色。

叔叔结点为黑色或者没有叔叔

情形1：新结点N为父结点P的右孩子，而P是其父结点的左孩子

• 进行先左再右旋转。
• 新结点变为黑色，祖父结点变为红色。

情形2：新结点N是父结点的左孩子，P是父结点的右孩子

• 进行先右再左旋转。
• 新结点变为黑色，祖父结点变为红色。

情形3：新结点N和父结点P都是左孩子

• 进行右旋转。
• 父结点变为黑色，祖父结点变为红色。

情形4：新结点N和父结点P都是右孩子

• 先进行左旋转。
• 父结点变为黑色，祖父结点变为红色。

以上四种旋转结束后，根均为黑色，不需要向上继续进行平衡操作。

 

分类: 数据结构与算法