R-B Tree，成为红黑树，每个节点上都有存储表示节点颜色的标记

大概了解一下的，只是简单介绍一下红黑树特点，不做树的旋转等操作分析。
具体代码可以研究jdk1.8中HashMap的静态内部类TreeNode 的源代码。
贴出TreeNode属性

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

红黑树的特点

1.每个节点不是红色的就是黑色的

2. 根节点是黑色的

3.每个叶子节点（null节点）都是黑色的

4.每个红色节点下的两个子节点一定是黑色的

5.从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点

本不是标准的平衡二叉树，但是因为加上了特点5作为一种平衡方法，使得性能得到提高