[数据结构与算法]红黑树

1.红黑树是内存最优的二叉树。

2.特点：（1）每个节点不是红色就是黑色。

? ? ? ? ? ? ? （2)根节点是黑色 。

? ? ? ? ? ? ? ? (3)每个叶子节点(null节点，空节点)是黑色的 。

? ? ? ? ? ? ? ? (4)如果一个节点是红色的，则他的子节点必须是黑色的。?

? ? ? ? ? ? ? ? (5)从一个节点到该节点的所有子孙节点的所有路径上包含相同数目的黑色节点。

3.红黑树都是2节点的。

4.将2-3-4树转换成红黑树时，有的节点里只有一个数（2节点）那么这个节点就是黑色的，而遇到? ? ?3节点和4节点的情况，就需要将其换成2节点，将3节点换成2节点就是将一个数字拉出来放上面? ? ?为黑色，另一个数字在下面为红色（大小放上面都可以），将4节点换成2节点就是将中间的一? ? ? ?个数放上面为黑色，左右两个数为下面左右两个节点。

例：

2节点转换：

?

?

3节点换成2节点：

4节点换成2节点：

（叶子节点都省略了哦）

?