红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，
红黑树五大特性
1、所有节点非红即黑
2、根节点是黑色
3、页节点是黑色
4、不能有连续的红色
5、任意节点到叶子节点路径中有相同数量的黑色节点
变色
如果当前节点的父亲节点和叔叔节点均是红色，那么执行以下变色操作：
父 --> 黑
叔 --> 黑
爷 --> 红
开始分析爷爷是否满足红黑树特性
左旋
条件：
父亲是红色
叔叔是黑色
当前是右子树
执行：
已父亲进行旋转
右旋
条件：
父亲是红色
叔叔是黑色
当前是左子树
执行：
父亲节点 变为 黑色
爷爷节点变为红色
再已爷爷节点进行旋转
流程
下面已一个具体的实例进行分析红黑树的执行过程：
新插入一个节点6（所有新插入节点均为红色），不满足条件4（不能有连续的红色），且当前节点父亲和叔叔均为红色 --> 则进行变色
此时5、12不满足”不能有连续的红色“，又因为12的父亲是红色，叔叔是黑色，且当前是右子树 --> 已父亲 5 左旋
此事5、12不满足”不能有连续的红色“，5的父亲是红色，叔叔是黑色，且在左子树 —> 先父亲变黑色、爷爷变红色 —> 已爷爷节点 19 右旋
至此：一个红黑树就完成了
网友评论