红黑树大学学过，但是只是在脑海里留下了一个印象，具体细节还是说不上来。最近在画各种数据结构图，发现不是很清楚红黑树的特性，还真画不出来。
先来回顾一下红黑树的概念。
一，什么是红黑树
红黑树是一种自平衡二叉查找树。典型的用途是实现关联数组。
什么是自平衡呢？自平衡指的是在新增、删除节点元素的时候，红黑树能够自动调整达到平衡的状态。
二，红黑树的特性
红黑树是具有下列着色性质的二叉查找树：
1，每一个节点，要么是红色，要么是黑色。
2，根节点是黑色。
3，如果一个节点是红色的，那么它的2个子节点必须是黑色。关于这一点，要说明一下，如果一个节点是黑色，那么它的子节点可以是黑色，也可以是红色。并且，还可以2个节点都是红色或者都是黑色。
4，从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。
上面的规则能够保证：红黑树的高度最多是2log(n+1)。
三，红黑树的自平衡策略
当红黑树增加或者删除节点时，可能会破坏红黑树的平衡状态，此时需要一种机制来保证红黑树达到新的平衡状态，这种机制就叫红黑树的自平衡策略。
红黑树的自平衡策略有三种：左旋转、右旋转、重新着色。
四，为什么使用红黑树
首先，要搞清楚一个关键点，就是红黑树的时间复杂度。红黑树的操作，包括查询，新增，修改，删除，都能保证logn的时间复杂度。这是红黑树能够广泛使用的一个关键点。
五，红黑树的应用场景
1，在Java中， TreeMap，Java 8中HashMap中TreeNode节点都采用了红黑树实现。
2，C++中，STL的map和set也应用了红黑树；
3，Linux进程调度Completely Fair Scheduler；
4，用红黑树管理进程控制块epoll在内核中的实现，用红黑树管理事件块；
5，Nginx中，用红黑树管理timer等；
下面我们结合TreeMap来看一下红黑树的具体实现。
首先看一下TreeMap的Entry<K, V>定义，有6个属性，如下：
K key;
V value;
Entry<K, V> left;
Entry<K, V> right;
Entry<K, V> parent;
boolean color = BLACK; // 新节点默认黑色
六，画一颗红黑树
我们先来看一颗百科上的红黑树。
