二叉查找树

红黑树的起源得从二叉查找树（二叉排序树）说起。先来看二叉查找树的定义：

1、要么为一颗空树，要么就是一颗具有如下特性的二叉树。

2、左子节点的值必须小于等于父节点的值。

3、右子节点的值必须大于等于父节点的值。

每个节点都符合这个特性，所以易于查找，如下图：

平衡二叉树

定义：

1、要么为一颗空树，要么就是一颗具有如下特性的二叉树。

2、它的左子树和右子树都是平衡二叉树。

3、它的左子树和右子树的深度差的绝对值不超过1。

红黑树

红黑树是一种特殊的二叉查找树，在满足二叉查找树的特性外，在每个节点上增加了存储颜色的标识，颜色要么是红色，要么是黑色，定义：

1、每个节点要么是黑色，要么是红色。

2、根节点是黑色。

3、所有叶子节点是黑色，即空节点（NIL）。

4、如果一个节点是红色的，则它的两个子节点必须是黑色的，也就是父子节点不能都为红色。

5、从一个节点到其所有叶子节点的所有路径上包含相同数目的黑节点。

注意：

(1) 特性3中的叶子节点，是只为空(NIL或null)的节点。

(2) 特性5，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。因此在最坏情况下，红黑树能保证时间复杂度为O( lgn )

红黑树示意图

TreeMap的数据结构

TreeMap采用红黑树的数据结构来实现。树节点Entry实现了Map.Entry，采用内部类的方式实现：

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
    // 其他省略
}

节点很简单，存储了父节点，左右子节点，以及红黑颜色，元素的key以及value信息。

再来看下TreeMap中支持红黑树的数据成员：

public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    // 用于接收外部比较器，插入时用于比对元素的大小
    private final Comparator<? super K> comparator;
    // 红黑树的根节点
    private transient Entry<K,V> root;
    // 树中元素个数
    private transient int size = 0;
    // 其他省略
}

为什么不用平衡二叉树作为底层实现

那是因为平衡二叉是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 如果插入一个node引起了树的不平衡，平衡二叉树和红黑树都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，平衡二叉树需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而红黑树最多只需3次旋转，只需要O(1)的复杂度, 所以平衡二叉树需要rebalance的频率会更高，因此红黑树在大量插入和删除的场景下效率更高