一、红黑树简介

自平衡二叉查找树

O(logN)时间内完成查找、增加、删除等操作

二、为什么需要红黑树

二叉平衡树插入数据为随机的时，那么它就是接近平衡的二叉树，平衡的二叉树操作效率较高O(logN)。如果插入有序，则节点集中于树的一侧，变成链表，操作效率降低，时间复杂度变为O(N)，二叉树的时间复杂度介于O(N)和O(logN)之间。

红黑树是接近平衡的二叉树，没有AVL平衡二叉树的严格平衡因子，而是通过红黑节点的5条性质来维持。

三、红黑树特性

每个节点存储颜色：红/黑

保证最长路径是最短路径的两倍：最长路径：红黑交替，最短路径全黑，从根节点到叶子节点的黑色节点个数相同。

5条特性：

1、节点是红色或黑色

2、根是黑色

3、叶子节点都是黑色，这里的叶子节点指空节点NULL

4、红色节点子节点、父节点是黑色，不存在两个连续红色节点

5、任意节点到叶子节点的所有路径包含相同数目的黑色节点

判断是否是红黑树：

不是，实际的叶节点是空NULL，所有路径经过黑节点数量不一致。

四、红黑树效率

查找、插入、删除的时间复杂度都是O(logN)

查找：与普通相对平衡二叉树效率一致。

插入有序：插入数据有序效率比二叉搜索树高

插入、删除：每次操作需平均旋转一次、变换颜色，效率略低，但仍为O(logN)

与AVL树比较：时间复杂度略低于AVL，但计算机CPU性能高，可忽略；插入更便于控制；整体性能略优于AVL树（旋转小）

五、红黑树等价变换

红黑树等价于一个四阶B树（一个节点最多访问三个数据）

等价过程红色节点移到他们的父节点的同一高度上：

简化为：

等价变化结论：

1、红黑树，4阶B树（2-3-4树）具有等价性

2、黑色节点和红色节点融合在一起，形成一个B树节点

3、红黑树黑色节点个数等价于B树节点个数

4、B树节点，永远黑色放中间，红色放两边

分类：

六、红黑树操作

1、旋转操作

分为左旋、右旋

右旋1：

左旋2：

2、插入操作

3、删除操作

七、AVL树vs红黑树

参考：http://t.csdn.cn/G0xE7