浅谈红黑树

1.红黑树简介

红黑树是一种自平衡二叉搜索树，不能保证非常严格的平衡性，但是其平衡性仍然足以确保以O(logN)的时间复杂度进行插入、删除和检索操作。
它需要更少的内存，并且可以更快的进行再平衡，所以它常在树需要被频繁修改的情况下使用。

2. 红黑树性质

1）每个节点要么是红色节点，要么是黑色节点
2）根节点是黑色节点
3）叶节点是空节点，也称为黑色节点
4）每个红色节点必须有两个黑色子节点，也就是说，一个红色节点不可能有红色子节点(虽然黑色节点可以有黑色子节点)
5）每一条从某一节点至叶节点的路径必须包含相同数量的黑色子节点

3. 为什么这样的树是平衡的

根据性质5)假设从某节点(根节点)到叶节点有路径1与路径2，每条路径均有b个黑色节点，最坏情况下，

• 红色节点最少数量为0，则路径1共有b个节点
• 红色节点最大数量为b(性质4决定红色节点数不会超过一半), 路径2共有2b个节点
  即使在最极端的情况下，两条路径的长度相差也不会超过一倍，这足以确保在O(logN)的时间复杂度内完成查找和插入操作

4. Java8中HashMap链表使用红黑树而不是AVL树

在ConcurrentHashMap中是加了锁的，实际上是读写锁，如果写冲突就会等待，如果插入时间过长必然等待时间更长，而红黑树相对AVL树插入更快

5. 既然红黑树那么好，为啥hashmap不直接采用红黑树，而是当大于8个的时候才转换红黑树

因为红黑树需要左旋、右旋操作，而单链表不需要
以下都是单链表与红黑树结构对比
如果元素小于8个，查询成本高，新增成本低
如果元素大于8个，查询成本低，新增成本高

6. 红黑树应用实例

JAVA: java.util.TreeMap、java.utils.TreeSet
C++ STL: map、multimap、multiset
Linux内核： 完全公平的调度程序， linux/rbtree.h