红黑树初识

为什么需要红黑树？

由于AVL树是以增加增加、删除节点来保证树的基本平衡，从而保证查询效率在O(logN)左右。
红黑树就是在不牺牲太大的增加、删除操作的代价，而且也能保证稳定高效的查找效率。

红黑树的特性

1. 每个节点要么是红色，要么就是黑色
2. 根节点是黑色
3. 每个叶子节点（null）是黑色
4. 如果一个节点是红色的，则它的子节点必须是黑色的
5. 没有一条路径会比会比其他路径长处两倍（虽然不是AVL中高度差不能超过为2的严格平衡）

红黑树查找性能

• 查找性能：基本维持在O(logN)，但是最差的情况是最短路径的两倍减一，所以要比AVL树差一点
• 插入性能：需要至多两次旋转和变色，也为O(logN)
• 删除性能：删除性能要比AVL树好很多，至多进行三次旋转操作。而不用像AVL树检查每一层的平衡因子可能涉及到多次旋转，所以删除性能要比AVL树好很多。