红黑树分析笔记

阅读本文的前提

1、知道二叉查找树的概念，插入、删除和查找操作；
2、知道二叉树的左旋和右旋。
3、了解二叉平衡树（AVL树）的概念

红黑树的概念

红黑树是一种自平衡的二叉查找树，查找、插入和删除的平均时间复杂度是O(logN)。红黑树的每个节点都有一个颜色值（红或黑），具有以下性质：
1、每个节点不是黑色就是红色；
2、根节点是黑色；
3、如果一个节点是红色，则该节点的左、右孩子节点必须是黑色；
4、每一个null叶子节点是黑色；
5、从任一个节点到null叶子节点的所有路径上必须包含相同数量的黑色节点。

null叶子节点

在红黑树里，存在两种叶子节点，一种叶子节点是我们常说的叶子节点——左右孩子节点都为null，另外一种是null叶子节点，如下图的红黑树：

blob.jpg

插入操作

红黑树的插入操作分两步：插入、调整。
插入操作和二叉查找树的操作一样，找到合适的位置创建节点插入；
由于插入新节点后，可能会违背红黑树的性质，因此需要做调整处理。

规定插入节点为红色

原因：如果新插入的节点为红色，首先肯定不会违背性质5，方便接下来的调整。

调整规则

定义：
【当前节点】：插入节点
【父亲节点】：【当前节点】的父亲节点
【叔叔节点】：【当前节点】的父亲节点的兄弟节点
【祖父节点】：【当前节点】的父亲节点的父亲节点
注：1、【当前节点】的值可能在调整过程中发生变化，不一定是开始的插入节点，【父亲节点】、【叔叔节点】、【祖父节点】的值依赖于【当前节点】。
2、【叔叔节点】可以是NULL节点

case 1 : 【父亲节点】是黑色
处　理：无须处理

case 2 : 【父亲节点】是红色，【叔叔节点】节点是红色
处　理：【父亲节点】和【叔叔节点】变黑，【祖父节点】变红，将【祖父节点】设为【当前节点】，继续按规则反复调整。

image

case 3 : 【父亲节点】是红色，【叔叔节点】节点是黑色
处　理：这种情况又分4种小情况来处理
3-1-1【父亲节点】是【祖父节点】的左孩子节点，【当前节点】是【父亲节点】的左孩子节点
处　理：【父亲节点】变黑，【祖父节点】变红，以【祖父节点】右旋；

image

3-1-2【父亲节点】是【祖父节点】的左孩子节点，【当前节点】是【父亲节点】的右孩子节点
处　理：以【父亲节点】左旋，变成上述3-1-1情形，旋转后的【父亲节点】设为【当前节点】，继续调整；

image

3-2-1 【父亲节点】是【祖父节点】的右孩子节点、【当前节点】是【父亲节点】的左孩子节点
处　理：以【父亲节点】右旋，变成下述3-2-2情形，旋转后的【父亲节点】设为【当前节点】，继续调整;

image

3-2-2【父亲节点】是【祖父节点】的右孩子节点、【当前节点】是【父亲节点】的右孩子节点
处　理：以【祖父节点】左旋，【祖父节点】变红，【父亲节点】变黑；

image

删除操作

首先要明白二叉查找树的删除规则：
1、删除节点是叶子节点，直接删除；
2、删除节点存在一个非空的子节点，删除节点后，将子节点移至删除节点位置；
3、删除节点左右孩子节点均非空，则要从左或右子树中查找到后继节点【后续节点的概念请看二叉查找树】，用后继节点替换删除节点，此时后继节点成为新的删除节点，后继节点最多只有一个非空的子节点，此时转化为情况2。

红黑树的删除规则和二叉查找树一致，关键要把握住一点，下面所说的删除节点不一定是指一开始要删除的节点，可能是情况3中的后续节点。