红黑树的代码实现，可在二分搜索树的代码上修改之后得到。

1 《算法导论》中的红黑树

1. 每个节点或者是红色的，或者是黑色的；
2. 根节点是黑色的
3. 每个叶子节点（最后的空节点）是黑色的；
4. 如果一个节点是红色的，那么他的孩子节点都是黑色的；
5. 从任意一个节点到叶子节点，经过的黑色节点是一样的。

   2 红黑树与2-3树

• 只看红黑树的定义是晦涩难懂的
• 其实红红黑树与2-3树是等价的：
  • 将2-3树中的3节点的左边的元素变成右边元素的左孩子，并标记成红色，那么，这就是一棵左倾红红黑树。
  • 所以1.2根节点一定是黑色的；
  • 1.3定义了空节点是黑色的；
  • 1.5红黑树是一棵黑平衡的二叉树。

3 添加元素

• 因为不会添加到空的位置，所以添加元素有两种境况：

  • 添加至2-节点，形成一个3-节点
  • 添加至3-节点，暂时形成一个4-节点

  • 永远添加红色节点

    3.1 保持根节点为黑色：

  • 当root为空时，直接new一个新节点出来即可；

  • 但是默认节点颜色为红色，所以需要进行 root.color = BLACK 操作

    public void add (K key, V value) {
    root = add(root, key, value);
    root.color = BLACK;
    }

    3.2 左旋转