七张图带你了解红黑树变色、左旋和右旋

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，

红黑树五大特性

1、所有节点非红即黑

2、根节点是黑色

3、页节点是黑色

4、不能有连续的红色

5、任意节点到叶子节点路径中有相同数量的黑色节点

变色

如果当前节点的父亲节点和叔叔节点均是红色，那么执行以下变色操作：

父 --> 黑

叔 --> 黑

爷 --> 红

开始分析爷爷是否满足红黑树特性

左旋

条件：

父亲是红色

叔叔是黑色

当前是右子树

执行：

已父亲进行旋转

右旋

条件：

父亲是红色

叔叔是黑色

当前是左子树

执行：

父亲节点 变为 黑色

爷爷节点变为红色

再已爷爷节点进行旋转

流程

下面已一个具体的实例进行分析红黑树的执行过程：

新插入一个节点6（所有新插入节点均为红色），不满足条件4（不能有连续的红色），且当前节点父亲和叔叔均为红色 --> 则进行变色

此时5、12不满足”不能有连续的红色“，又因为12的父亲是红色，叔叔是黑色，且当前是右子树 --> 已父亲 5 左旋

此事5、12不满足”不能有连续的红色“，5的父亲是红色，叔叔是黑色，且在左子树 —> 先父亲变黑色、爷爷变红色 —> 已爷爷节点 19 右旋

至此：一个红黑树就完成了