JDK源码研究TreeMap（红黑树）上篇

十三月的

浏览: 165015 次
性别:
来自: 长沙

最近访客更多访客>>

robotmen

malongkong

天堂路

leozam

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

数据结构理解
JAVA基础

红黑树 TreeMap 数据结构 JDK

TreeMap

目的：

通过对JDK源码的分析，进一步了解红黑树。

1:TreeMap介绍

2:红黑树介绍

3:红黑树插入及TreeMap插入实现

4:红黑树删除及TreeMap删除实现

1：TreeMap介绍

TreeMap和HashMap同样继承于Map接口，前者是在基于红黑树，后者是基于散列。

红黑树，是一种平衡的二叉搜索树。但是它并非是严格的平衡树，而是追求局部的平衡，从而保证树的高度在lgn和2lgn之间。

所谓平衡，实际是为了解决二叉搜索树的两种极端情况即所有结点的值本来是有序，则在建立二叉搜索树的时候，该树实际变成了一个链表，它的时间复杂度是o(n)。当通过旋转操作使之称为平衡二叉树后，树的高度是lgn，则其搜索的时间复杂度是o(lgn)。

2：红黑树介绍

红黑树：红黑树首先是一个二叉搜索树.树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值。

除此之外，红黑树还有如下性质：

1：每个结点都有颜色，不是红色就是黑色

2：根节点必须是黑色

3：所有的叶子结点都是空结点（null），颜色是黑色

4：红色结点的父结点必须是黑色

5：从任意一个结点到其子树中的叶子结点的路径中包含相同数目的黑色节点。

3：红黑树插入及TreeMap插入实现

红黑树在插入新的结点的时候，规定新结点的颜色是红色。和普通二叉搜索树一样，首先找到插入的位置，之后红黑树需要维持自己的5个性质，因此需要进行修正。

当插入结点N的父节点是黑色结点的时候，显然根本不需要任何修正，上述5个性质仍旧成立。所以只需要考虑插入结点N的父节点同样是红色的情况,一共有6种情况，实际上是3种情况，因为有3种情况是对称的。

情况1：N是其父节点的左孩子，N的父节点是红色，父节点的兄弟结点是红色。

情况2：N是其父节点的左孩子，N的父节点是红色，父节点的兄弟结点是黑色。但父节点是爷爷结点的右孩子。

情况3：N是其父节点的左孩子，N的父节点是红色，父节点的兄弟结点是黑色。父节点是爷爷结点的左孩子。

情况4、5和6只是把N换成是其父节点的右孩子。

可以看出情况1并不关心N、父节点和爷爷结点的关系。但是情况2和3是关心的。

下面给出情况1、2和3的调整办法：

情况1，调整N的父节点和N的父节点的兄弟结点（称叔叔结点）的颜色为黑色，爷爷结点的颜色为红色，并设爷爷结点为新的N。这样N相当于向上调整了两层。之后再根据N所处位置判断是哪种情况继续调整。

（G代表爷爷结点Grandfather,P代表父节点Father，N代表新结点New）

情况2：

此时，违规的结点变成了P结点，相当于新的N，实际上这就转化为了情况3.

情况3：

下面以一个具体的例子介绍：

当前该红黑树满足其5个性质，现在我们需要插入一个新得结点15.

可以看出上述满足情况1.于是我们进行了调整，之后变成了右边的情形。此时违规的是结点10.

结点10违规，检查之后发现属于情况2.此时需要右旋转。一旦实行右旋转就转化为了情况3，情况3也意味着结束。

当然，以上这些结点可能只是整个树的一部分，但是整个过程就是这样。

代码实现：

  //结点Entry结构  
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
 //put方法
  public V put(K key, V value) {
       //根节点
        Entry<K,V> t = root;
        //如果根节点为空
        if (t == null) {
            root = new Entry<K,V>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
       //以下是查找插入的位置X
        int cmp;
        Entry<K,V> parent;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {//如果用户设定比较器
            do {
               //记录最终位置X的父节点
                parent = t;
                cmp = cpr.compare(key, t.key);
               //根据比较选择
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);//直到叶子结点
        }
        else {//如果用户没有设定比较器
            if (key == null)
                throw new NullPointerException();
            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);
        }
        //初始化需要插入的结点
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
        //设定父节点和新插入结点的关系
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //修复
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

实际上面除了修复函数外，和普通的二叉搜索树并无多大差别，关键在于维护红黑树的性质

 private void fixAfterInsertion(Entry<K,V> x) {
        //新结点默认为红色
        x.color = RED;
       //如果父节点为红色
        while (x != null && x != root && x.parent.color == RED) {
            //如果父节点是爷爷结点的左结点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
               //叔叔结点y
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
               //如果叔叔结点是红色 （情况1）
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                   //x重新赋值
                    x = parentOf(parentOf(x));
                } else {//叔叔结点是黑色的
                    //x是父节点的右结点 （情况2）
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        //左旋
                        rotateLeft(x);
                    }
                    //此处已经转化为（情况3）
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {//如果父节点是爷爷结点的右结点  （对称）
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    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;
    }

实际上插入和插入后的修复相对比较简单，删除会比较复杂些，上篇完。