TreeMap（二）

6 二叉查找树

说完了二叉树，下面继续说二叉查找树；相比于二叉树来说，二叉查找树的特点更加明确。

二叉查找树规定：

如果二叉查找树的左子树不为空，那么它的左子树上的任意节点的值都小于根节点的值；
如果二叉查找树的右子树不为空，那么它的右子树上的任意节点的值都大于根节点的值；

也就是说，二叉查找树的左子树中任意节点的值都小于右子树中任意节点的值。而且，在左子树和右子树中也同样形成了二叉查找树；所以说二叉查找树的特点比二叉树更加明确。

此外，根据上面的特点，我们还可以使用二分查找在树中进行元素搜索：如果查找的元素大于根节点，则在树的右边进行搜索；如果小于根节点，则在树的左边进行搜索。如果等于根节点，则直接返回；所以二叉查找树的查询效率远远高于二叉树。

7 平衡二叉树（AVL树）

前几节中，笔者说过：可以将二叉树简单地理解为一个链表结构。当时，是为了能让各位能对二叉树有一个最直观的理解。

其实，在具体的实现中二叉树确实会形成一个链表结构。

试想下，如果一个二叉树的左子树为空，只有右子树，且右子树中又只有右节点（左节点），那么这个二叉树就形成了一个不折不扣的链表。对于二叉查找树来说，二分查找也就失去了原有的性能，变成了顺序查找。即元素的插入顺序是1、2、3、4、5、6的话，即可实现。

为了针对这一情况，平衡二叉树出现了（又称为AVL树），它要求左右子树的高度差的绝对值不能大于1，也就是说左右子树的高度差只能为-1、0、1。

8 红黑树

终于说到了今天的重中之重—红黑树，相比于之前讲过的数据结构，红黑树的难度有所增加，你要做好准备！

只要带有树字，它就远离不了二叉树的结构。

红黑树，本质上依旧一颗二叉查找树，它满足了二叉查找树的特点，即左子树任意节点的值永远小于右子树任意节点的值。

不过，二叉查找树还有一个致命的弱点，即左子树(右子树)可以为空，而插入的节点全部集中到了树的另一端，致使二叉查找树失去了平衡，二叉查找树搜索性能下降，从而失去了使用二分查找的意义。

为了维护树的平衡性，平衡二叉树（AVL树）出现了，它用左右子树的高度差来保持着树的平衡。而我们本节要介绍的红黑树，用的是节点的颜色来维持树的平衡。

那么，红黑树是怎么利用颜色来维持平衡的呢？接下来，让我们慢慢道来。

红黑树，即红颜色和黑颜色并存的二叉树，插入的元素节点会被赋为红色或者黑色，待所有元素插入完成后就形成了一颗完整的红黑树。如下图所示：

不过，你不要想当然的以为只是给二叉树的阶段随意赋为黑色或者红色，就可保证树的平衡。事情远没有你想象的那么简单。

一颗红黑树必须满足一下几点要求：

1. 树中每个节点必须是有颜色的，要么红色，要么黑色；

2. 树中的根节点必须是黑色的；

3. 树中的叶节点必须是黑色的，也就是树尾的NIL节点或者为null的节点；

4. 树中任意一个节点如果是红色的，那么它的两个子节点一点是黑色的；

5. 任意节点到叶节点（树最下面一个节点）的每一条路径所包含的黑色节点数目一定相同；

科普：NIL节点是就是一个假想的或是无实在意义的节点，所有应该指向NULL的指针，都看成指向了NIL节点。包括叶节点的子节点指针或是根节点的父指针（均是指向null的）

除了给节点赋颜色之外，还会对节点进行左旋、右旋操作，以来维持树的平衡。那么，左旋、右旋又什么？

首先，我们先来看下在红黑树中，每一个节点的数据结构是什么样子的？

public class TreeNode {
    //节点的值：
    private int data;
    //节点的颜色：
    private String color;
    //指向左孩子的指针：
    private TreeNode leftTreeNode;
    //指向右孩子的指针：
    private TreeNode rightTreeNode;
    //指向父节点的指针
    private TreeNode parentNode;
    public TreeNode(int data, String color, TreeNode leftTreeNode,
                    TreeNode rightTreeNode, TreeNode parentNode) {
        this.data = data;
        this.color = color;
        this.leftTreeNode = leftTreeNode;
        this.rightTreeNode = rightTreeNode;
        this.parentNode = parentNode;
    }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public String getColor() {return color;}
    public void setColor(String color) {this.color = color;}
    public TreeNode getLeftTreeNode() {
        return leftTreeNode;
    }
    public void setLeftTreeNode(TreeNode leftTreeNode) {
        this.leftTreeNode = leftTreeNode;
    }
    public TreeNode getRightTreeNode() {
        return rightTreeNode;
    }
    public void setRightTreeNode(TreeNode rightTreeNode) {
        this.rightTreeNode = rightTreeNode;
    }
    public TreeNode getParentNode() {return parentNode;}
    public void setParentNode(TreeNode parentNode) {this.parentNode = parentNode;}
}

如果用图片来形容的话：

8.1 旋转

上面说过，为了维护红黑树的平衡，不只是给节点着色那么简单，还有更复杂的处理逻辑。

而这更复杂的处理逻辑就是对节点进行旋转操作，其中旋转操作又分为左旋、右旋两种；

对于树的操作，最常见的就是添加、删除而已。不过，在添加或者删除之后，红黑树发生了改变，可能就不满足以上的5点要求，也就不是一颗红黑树了。于是我们需要通过对节点的旋转，使其重新成为一颗红黑树。

1. 左旋

左旋，顾名思义就是对节点进行向左旋转处理；

对节点X进行向左进行旋转，将其变成了一个左子节点；

这个左旋中的左，就是将被旋转的节点变成一个左节点；

其中，如果Y的的左子节点不为null，则将其赋值X的右子节点；

1. 右旋

右旋，同理，也就是对节点进行向右旋转处理；

对节点Y进行向右进行旋转，将其变成了一个右子节点；

这个右旋中的右，就是将被旋转的节点变成一个右节点；

其中，如果X节点的右子节点不为null，则赋值给Y的左子节点；

补充：在举个例子，让大家更直观的理解：（暂时先忽略红黑树，只关注旋转）

8.2 红黑树节点添加

本节中，笔者就来介绍下红黑树节点的添加。

在将一个节点插入到红黑树中，首选需要将红黑树当做一颗二叉树查找树来对待，将节点进行插入。然后，为新插入的节点进行着色；最后，通过旋转和重新着色的方式来修正树的平衡，使其成为一颗红黑树；

（1）对于红黑树来说，其底层依旧是一颗二叉查找树。当我们插入新的元素时，它依旧会对该元素进行排序比较，将其送入到左子树或者是右子树中。

（2）在将新节点安置好以后，在对其进行着色处理，必须着成红色。

你此时可能会问，为什么要着成红色，而不是黑色呢？

这就需要我们重新回顾下红黑树的规范了：

1. 树中每个节点必须是有颜色的，要么红色，要么黑色；
2. 树中的根节点必须是黑色的；
3. 树中的叶节点必须是黑色的，也就是树尾的NIL节点或者为null的节点；
4. 树中任意一个节点如果是红色的，那么它的两个子节点一点是黑色的；
5. 任意节点到叶节点（树最下面一个节点）的每一条路径所包含的黑色节点数目一定相同；

通过以上的规范，我们可以分析出，当将新增节点着成红色后，我们违背以上规范的条数最少，恢复平衡起来最省事，当新增节点为红色时：

1.不会违背第五条--黑色节点数目相同；
2.不会违背第一条--节点必须是红色，或者黑色；
3.不会违背第二条--根节点是黑色--当树中已有元素时候，我们新增节点并不会影响根节点的颜色（若树中没有元素，新增节点会被当成根节点，此时虽被着为红色，但在最后一步中还会对其重新着色，变成黑色）；
4.不会违背第三条--此处所指的叶节点指的是叶节点的子节点，也就是为null的元素；
5.可能会违背第四条--任意节点为红色，其子节点一定是黑色；

如果新插入的节点的父节点是红色的话，那么第四条一定会违背，所以说我们需要对其进行旋转处理；

（3）冲突来了，解决冲突（对节点进行旋转）

• 当被插入节点是根节点：

  新插入的节点后，如果为根节点，则直接将其变成黑色，并返回； 

• 当被插入节点的父节点是黑色：

  新插入的节点被着成红色后，发现其父节点是黑色，并不影响红黑树结构，所以并不需要对平衡性做处理，直接返回； 

• 当被插入节点的父节点是红色（最复杂）：

  新插入的节点被着成红色后，发现其父节点是红色，此时红黑树的平衡被打破，需要特别处理。

  说之前，简单的阐述下什么是该节点的祖父节点，什么是该节点的叔叔节点（画图一目了然）；

      

case1：叔叔节点为黑色（空节点默认为黑色）

A.2是3的左子节点，3是5的左子节点；
B.17是16的右子节点，16是15的右子节点；

C.17是15的右子节点，15是23的左子节点 
D.43是56的左子节点，46是41的右子节点；

其中，A、B称之为外侧插入，C、D称之为内测插入。

首先，来看A的解决方案：

将3设置为黑色，5设置为红色，再对5进行右旋，结果如下：

来看B的解决方案：

将16设置为黑色，15设置为红色，再对15进行左旋，结果如下：

来看C的解决方案：

将15进行左旋，成为17的左子节点，此时形成了A情况，再将17置为黑色，23置为红色，再对23进行右旋，结果如下：

来看D的解决方案：将46进行右旋，成为41的右子节点，此时形成了B情况，再将43置为黑色，41置为红色，再对41进行左旋，结果如下：

case2：叔叔节点为红色

当叔叔节点为红色时，处理的逻辑较为简单，主要对元素节点的颜色进行处理，无需左旋、右旋的操作。

在A情况中，无论新插入的元素是7还是12，处理过程都是一样的；

将10和27置为黑色，23置为红色，再将23置为黑色，新插入元素7（12）保持红色不变，结束返回；

同理，在B情况中，处理26或者35的逻辑也是相同的；

将15和30置为黑色，18置为红色，再将18置为黑色，新插入元素26（35）保持红色不变，结束返回；

同上，暂不画图了；

以上，就是红黑树添加节点的处理逻辑，希望以上的图片可以让你对着色、旋转有一个清晰的认识！

有兴趣的朋友，可以参考红黑树网站进行实际操作！

8.3 红黑树节点删除

暂省略；

9 TreeMap源码讲解（基于JDK1.7.0_75）

上面，我们通过图片的形式，对红黑树进行了全面的讲解。接下来，就让我们学习下红黑树在Java中的实现—TreeMap;

• TreeMap节点结构

TreeMap底层存储结构与HashMap基本相同，依旧是Entry对象，存储key—value键值对，子节点的引用和父节点的引用，以及默认的节点颜色（黑色）；

static final class Entry<K,V> implements Map.Entry<K,V> {
    //插入节点的key:
    K key;
    //插入节点的value:
    V value;
    //插入节点的左子节点：
    java.util.TreeMap.Entry<K,V> left = null;
    //插入节点的右子节点：
    java.util.TreeMap.Entry<K,V> right = null;
    //插入节点的父节点：
    java.util.TreeMap.Entry<K,V> parent;
    //插入节点默认的颜色：
    boolean color = BLACK;
    //Entry对象的构造函数：
    Entry(K key, V value, java.util.TreeMap.Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    public K getKey() {
        return key;
    }
    public V getValue() {
        return value;
    }
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }
    public int hashCode() {
        int keyHash = (key==null ? 0 : key.hashCode());
        int valueHash = (value==null ? 0 : value.hashCode());
        return keyHash ^ valueHash;
    }
    public String toString() {
        return key + "=" + value;
    }
}

• TreeMap构造函数

与HashMap不同，TreeMap底层不是数组结构，成员变量中并没有数组，而是用根节点root来替代，所有的操作都是通过根节点来进行的。

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 java.util.TreeMap.Entry<K,V> root = null;
    //集合元素数量：
    private transient int size = 0;
    //对TreeMap操作的数量：
    private transient int modCount = 0;
    //无参构造方法：comparator属性置为null
    //代表使用key的自然顺序来维持TreeMap的顺序，这里要求key必须实现Comparable接口
    public TreeMap() {
        comparator = null;
    }
    //带有比较器的构造方法：初始化comparator属性；
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    //带有map的构造方法：
    //同样比较器comparator为空，使用key的自然顺序排序
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
    //带有SortedMap的构造方法:
    //根据SortedMap的比较器来来维持TreeMap的顺序
    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }
}

• TreeMap元素添加

将新增节点的key—value插入到TreeMap当中，在上文中我们已经通过图文的形式介绍了新增的流程，如果你还不明白，可以结合源码进行理解；

首先找到新增节点的位置，其次在判断TreeMap是否处于平衡状态，若不平衡，则对节点进行着色、旋转操作；

//插入key-value:
public V put(K key, V value) {
    //根节点赋值给t:
    java.util.TreeMap.Entry<K,V> t = root;
    //如果根节点为null，则创建第一个节点，根节点
    if (t == null) {
        //对传入的元素进行比较，若TreeMap没定义了Comparator，则验证传入的元素是否实现了Comparable接口；
        compare(key, key);
        //根节点赋值：
        root = new java.util.TreeMap.Entry<>(key, value, null);
        //长度为1：
        size = 1;
        //修改次数+1
        modCount++;
        //直接返回：此时根节点默认为黑色
        return null;
    }
    //如果根节点不为null:
    int cmp;
    java.util.TreeMap.Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    //判断TreeMap中自定义比较器comparator是否为null：
    if (cpr != null) {
        // do while循环，查找新插入节点的父节点：
        do {
            // 记录上次循环的节点t，首先将根节点赋值给parent:
            parent = t;
            //利用自定义比较器的比较方法：传入的key跟当前遍历节点比较：
            cmp = cpr.compare(key, t.key);
            //判断结果小于0，处于父节点的左边 
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
            //判断结果大于0，处于父节点的右边 
                t = t.right;
            else
            //判断结果等于0，为当前节点，覆盖原有节点处的value：
                return t.setValue(value);
        // 只有当t为null，也就是找到了新节点的parent了
        } while (t != null);
    } else {
        //没有自定义比较器：
        if (key == null)
             TreeMap不允许插入key为null，抛异常：
            throw new NullPointerException();
        //将key转换为Comparable对象：若key没有实现Comparable接口，此处会报错
        Comparable<? super K> k = (Comparable<? super K>) key;
        //同上：寻找新增节点的父节点：
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    //构造新增节点对象：
    java.util.TreeMap.Entry<K,V> e = new java.util.TreeMap.Entry<>(key, value, parent);
    //根据之前的比较结果，判断新增节点是在父节点的左边还是右边
    if (cmp < 0)
        // 如果新节点key的值小于父节点key的值，则插在父节点的左侧
        parent.left = e;
    else
        // 如果新节点key的值大于父节点key的值，则插在父节点的右侧
        parent.right = e;
    //核心方法：插入新的节点后，为了保持红黑树平衡，对红黑树进行调整
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
//对插入的元素比较：若TreeMap没有自定义比较器，则调用调用默认自然顺序比较，要求元素必须实现Comparable接口；
//若自定义比较器，则用自定义比较器对元素进行比较；
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
}
//核心方法：维护TreeMap平衡的处理逻辑；（回顾上面的图文描述）
private void fixAfterInsertion(java.util.TreeMap.Entry<K,V> x) {
    //首先将新插入节点的颜色设置为红色
    x.color = RED;
    //TreeMap是否平衡的重要判断，当不在满足循环条件时，代表树已经平衡；
    //x不为null，不是根节点，父节点是红色（三者均满足才进行维护）：
    while (x != null && x != root && x.parent.color == RED) {
        //节点x的父节点 是 x祖父节点的左孩子：
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            //获取x节点的叔叔节点y:
            java.util.TreeMap.Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            //叔叔节点y是红色：
            if (colorOf(y) == RED) {
                //将x的父节点设置黑色：
                setColor(parentOf(x), BLACK);  
                //将x的叔叔节点y设置成黑色：
                setColor(y, BLACK);
                //将x的祖父节点设置成红色：
                setColor(parentOf(parentOf(x)), RED);
                //将x节点的祖父节点设置成x(进入了下一次判断)：
                x = parentOf(parentOf(x));
            } else {
                 /叔叔节点y不为红色：
                //x为其父节点的右孩子：
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //右旋：
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //节点x的父节点 是x祖父节点的右孩子：
             //获取x节点的叔叔节点y:
            java.util.TreeMap.Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            //判断叔叔节点y是否为红色：
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);12
                setColor(y, BLACK);5
                setColor(parentOf(parentOf(x)), RED);10
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //左旋：
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}
//获取节点的颜色：
  private static <K,V> boolean colorOf(java.util.TreeMap.Entry<K,V> p) {
    //节点为null,则默认为黑色；
    return (p == null ? BLACK : p.color);
}
//获取p节点的父节点：
private static <K,V> java.util.TreeMap.Entry<K,V> parentOf(java.util.TreeMap.Entry<K,V> p) {
    return (p == null ? null: p.parent);
}
//对节点进行着色，TreeMap使用了boolean类型来代表颜色（true为红色，false为黑色）
private static <K,V> void setColor(java.util.TreeMap.Entry<K,V> p, boolean c){
    if (p != null)
        p.color = c;
}
//获取左子节点：
private static <K,V> java.util.TreeMap.Entry<K,V> leftOf(java.util.TreeMap.Entry<K,V> p) {
    return (p == null) ? null: p.left;
}
//获取右子节点：
private static <K,V> java.util.TreeMap.Entry<K,V> rightOf(java.util.TreeMap.Entry<K,V> p) {
    return (p == null) ? null: p.right;
}
//左旋：
private void rotateLeft(java.util.TreeMap.Entry<K,V> p) {
    if (p != null) {
        java.util.TreeMap.Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}
//右旋：
private void rotateRight(java.util.TreeMap.Entry<K,V> p) {
    if (p != null) {
        java.util.TreeMap.Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

• TreeMap元素获取

TreeMap底层是红黑树结构，而红黑树本质是一颗二叉查找树，所以在获取节点方面，使用二分查找算法性能最高；

//通过key获取对应的value：
public V get(Object key) {
    //获取TreeMap中对应的节点：
    java.util.TreeMap.Entry<K,V> p = getEntry(key);
    //获取节点的值：
    return (p==null ? null : p.value);
}
//通过key获取Entry对象：
final java.util.TreeMap.Entry<K,V> getEntry(Object key) {
    //TreeMap自定义比较器不为空，使用自定义比较器对象来获取节点：
    if (comparator != null)
        //获取节点：
        return getEntryUsingComparator(key);
    //如果key为null，则抛出异常，TreeMap中不允许存在为null的key：
    if (key == null)
        throw new NullPointerException();
    //将传入的key转换成Comparable类型，传入的key必须实现Comparable接口
    Comparable<? super K> k = (Comparable<? super K>) key;
    //获取根节点：
    java.util.TreeMap.Entry<K,V> p = root;
    // 使用二分查找方式，首先判断传入的key与根节点的key哪个大：
    while (p != null) {
        //传入的key与p节点的key进行大小比较：
        int cmp = k.compareTo(p.key);
        //传入的key小于p节点的key,则从根的左子树中搜索：
        if (cmp < 0)
            //左边
            p = p.left;
        else if (cmp > 0)
            //传入的key大于p节点的key,则从根的右边子树中搜索：
            //右边
            p = p.right;
        else
            //传入的key等于p节点的key,则直接返回当前节点：
            return p;
    }
    //以上循环没有找对对应的节点，则返回null：
    return null;
}
//使用自定义比较器进行元素比较，获取对节点：
final java.util.TreeMap.Entry<K,V> getEntryUsingComparator(Object key) {
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        java.util.TreeMap.Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

• TreeMap元素删除

暂忽略；

《分布式服务架构：原理、设计与实战》是一本不可多得的理论与实践相结合的架构书籍，京东购买请扫下面二维码。