原来你是这样的TreeMap之红黑树
博客专区 > Mr_Qi 的博客 > 博客详情
原来你是这样的TreeMap之红黑树
Mr_Qi 发表于2天前
原来你是这样的TreeMap之红黑树
  • 发表于 2天前
  • 阅读 374
  • 收藏 25
  • 点赞 2
  • 评论 0

腾讯云实验室 1小时搭建人工智能应用,让技术更容易入门 免费体验 >>>   

上篇描述了HashMap的数据结构原来你是这样的HashMap

本篇就TreeMap的实现进行详述

相比较HashMap其多了SortedMap(NavigableMap 类似ceil floor返回最接近的元素)接口实现

顾名思义就是支持了排序

 

说到排序可能大家就能想到一堆排序算法:堆排序 二分法 冒泡排序 插入排序 快排等等

那么TreeMap采用了红黑树来作为排序(传统的平衡二叉树指的是高度上的平衡一般称之为AVL树,即任意节点的左子树和右子数的高度相差不超过1,红黑树的是平衡指的是黑高度【BH】的的平衡,即任意节点到叶子节点的简单路径中黑色节点数目均相同)

几个常见的构造函数如下

/**
 * Constructs a new, empty tree map, using the natural ordering of its
 * keys.  All keys inserted into the map must implement the {@link
 * Comparable} interface.  Furthermore, all such keys must be
 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
 * a {@code ClassCastException} for any keys {@code k1} and
 * {@code k2} in the map.  If the user attempts to put a key into the
 * map that violates this constraint (for example, the user attempts to
 * put a string key into a map whose keys are integers), the
 * {@code put(Object key, Object value)} call will throw a
 * {@code ClassCastException}.
 */
public TreeMap() {
    comparator = null;
}
 
/**
 * Constructs a new, empty tree map, ordered according to the given
 * comparator.  All keys inserted into the map must be <em>mutually
 * comparable</em> by the given comparator: {@code comparator.compare(k1,
 * k2)} must not throw a {@code ClassCastException} for any keys
 * {@code k1} and {@code k2} in the map.  If the user attempts to put
 * a key into the map that violates this constraint, the {@code put(Object
 * key, Object value)} call will throw a
 * {@code ClassCastException}.
 *
 * @param comparator the comparator that will be used to order this map.
 *        If {@code null}, the {@linkplain Comparable natural
 *        ordering} of the keys will be used.
 */
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}
 
/**
 * Constructs a new tree map containing the same mappings as the given
 * map, ordered according to the <em>natural ordering</em> of its keys.
 * All keys inserted into the new map must implement the {@link
 * Comparable} interface.  Furthermore, all such keys must be
 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
 * a {@code ClassCastException} for any keys {@code k1} and
 * {@code k2} in the map.  This method runs in n*log(n) time.
 *
 * @param  m the map whose mappings are to be placed in this map
 * @throws ClassCastException if the keys in m are not {@link Comparable},
 *         or are not mutually comparable
 * @throws NullPointerException if the specified map is null
 */
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

默认情况下comparator都是空,那么是如何进行排序的呢?

我们查看一下put方法

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
 
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            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<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

看到compare方法

/**
 * Compares two keys using the correct comparison method for this TreeMap.
 */
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

看来首先是使用comparator进行排序如果不存在则使用compareTo方法进行排序

那么必然如下问题:

  1. TreeMap可否使用key为null
  2. TreeMap的key是否Comparable之类
  3. 如果comparator发生了变化是否排序会受到影响需要resort?

问题1. 当comparator为空的时候放入空key必然会导致npe发生(和hashMap不一样,有时会用来存空key)

问题2:默认情况下如果放入了不支持排序的类型会导致强转类型失败

问题3:所以TreeMap将comparator设置为final那么该值必然只能设置一次

因此在通常场景下TreeMap的key还是需要校验是否为空(和HashMap不一样,当然是用comparator并且comparator支持null的话是OK的)

其实上述描述存在问题,事实上comparator方法不支持compare的参数为空 其详细约定如果为null要抛出npe

/**
 * Compares its two arguments for order.  Returns a negative integer,
 * zero, or a positive integer as the first argument is less than, equal
 * to, or greater than the second.<p>
 *
 * In the foregoing description, the notation
 * <tt>sgn(</tt><i>expression</i><tt>)</tt> designates the mathematical
 * <i>signum</i> function, which is defined to return one of <tt>-1</tt>,
 * <tt>0</tt>, or <tt>1</tt> according to whether the value of
 * <i>expression</i> is negative, zero or positive.<p>
 *
 * The implementor must ensure that <tt>sgn(compare(x, y)) ==
 * -sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>.  (This
 * implies that <tt>compare(x, y)</tt> must throw an exception if and only
 * if <tt>compare(y, x)</tt> throws an exception.)<p>
 *
 * The implementor must also ensure that the relation is transitive:
 * <tt>((compare(x, y)&gt;0) &amp;&amp; (compare(y, z)&gt;0))</tt> implies
 * <tt>compare(x, z)&gt;0</tt>.<p>
 *
 * Finally, the implementor must ensure that <tt>compare(x, y)==0</tt>
 * implies that <tt>sgn(compare(x, z))==sgn(compare(y, z))</tt> for all
 * <tt>z</tt>.<p>
 *
 * It is generally the case, but <i>not</i> strictly required that
 * <tt>(compare(x, y)==0) == (x.equals(y))</tt>.  Generally speaking,
 * any comparator that violates this condition should clearly indicate
 * this fact.  The recommended language is "Note: this comparator
 * imposes orderings that are inconsistent with equals."
 *
 * @param o1 the first object to be compared.
 * @param o2 the second object to be compared.
 * @return a negative integer, zero, or a positive integer as the
 *         first argument is less than, equal to, or greater than the
 *         second.
 * @throws NullPointerException if an argument is null and this
 *         comparator does not permit null arguments
 * @throws ClassCastException if the arguments' types prevent them from
 *         being compared by this comparator.
 */
int compare(T o1, T o2);

理论上都不支持null key

 

让我们重新来走一遍TreeMap的put过程。

这是一个典型的二叉查找树的查找与插入过程。

  1. 如果当树本身不存在的情况下直接将本身放入根并返回空

    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
     
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }

     

   2.当树根存在直接按照排序查找到指定的节点(左孩子必然小于本身 右孩子必然大于本身 不支持相同大小,也就是当大小相同直接替换并返回old value)

   

int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
    do {
        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<>(key, value, parent);
if (cmp < 0)
    parent.left = e;
else
    parent.right = e;

  

3. 如果这是一根平衡二叉树那么由于数据的插入很可能导致失衡,那么可能需要一系列的旋转来完成二叉树的平衡(平衡的目的在于更好的查找速度)
大学里面可能都学过AVL树其实就是一种典型的平衡二叉树的实现(但是avl的旋转次数可能较多,导致整体统计性能不如红黑树)

在插入新的节点之后首先要做的就是重新平衡(旋转或者着色) 

fixAfterInsertion(e);
/** From CLR */
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        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;
    }
}
 
/** From CLR */
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        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;
    }
}
 
/** From CLR */
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)))) {
            Entry<K,V> y = rightOf(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 == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                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;
}

这边首先描述一下红黑树的定义

 

除了二叉树的基本要求外,红黑树必须满足以下几点性质。

  1. 节点必须是红色或者黑色。
  2. 根节点必须是黑色。
  3. 叶节点(NIL)是黑色的。(NIL节点无数据,是空节点)
  4. 红色节点必须有两个黑色儿子节点。
  5. 从任一节点出发到其每个叶子节点的路径,黑色节点的数量是相等的。

先查看一下节点的定义

/**
 * Node in the Tree.  Doubles as a means to pass key-value pairs back to
 * user (see Map.Entry).
 */
 
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left = null;
    Entry<K,V> right = null;
    Entry<K,V> parent;
    boolean color = BLACK;
 
    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
 
    /**
     * Returns the key.
     *
     * @return the key
     */
    public K getKey() {
        return key;
    }
 
    /**
     * Returns the value associated with the key.
     *
     * @return the value associated with the key
     */
    public V getValue() {
        return value;
    }
 
    /**
     * Replaces the value currently associated with the key with the given
     * value.
     *
     * @return the value associated with the key before this method was
     *         called
     */
    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;
    }
}

左旋操作

右旋操作

那么分几个场景来讨论插入:【默认孩子节点都是红色,设想如果颜色为黑色那么破坏了第五条特性,那么造成的旋转次数可能较多,实现相对困难】

  1. 当父亲节点是黑色,那么无需操作,直接插入新的红色孩子节点(不会破坏属性)
  2. 当父亲节点为红色(此时必然会破坏第4条特性)【以下操作均需要注意叔叔节点或者祖父节点均有可能不存在】===》当然此时祖父节点必然存在因为根节点必须为黑色
    以父亲为左孩子为例,其余镜像即可
    1. 当叔叔节点为红色,此时将父亲节点和叔叔节点涂成黑色,同时将祖父节点涂成红色,并将当前指针指向祖父节点
    2. 当叔叔节点为黑色,当前节点为父亲节点的右孩子 此时以父亲节点进行左旋 并将当前指针指向原父亲节点
    3. 当叔叔节点为黑色,当前节点为父亲节点左孩子 那么需要以父亲节点右旋 同时将父亲节点涂黑 原祖父节点涂红

考虑一下左旋或者右旋的情况,事实上为了高度尽可能的低(最好是完美平衡二叉树)那么当新加的节点是左孩子自然要进行右旋(这样高度相应降低)右孩子自然进行左旋【这也是常规思路】 其余分情况进行颜色变更

那么从代码分析

/** From CLR */
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)))) {
            //父亲节点为祖父节点的左孩子节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                //父亲节点和叔叔节点均为红色
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
                //对应情况A
            } else {
                 //父亲节点为红色和叔叔节点为黑色
                if (x == rightOf(parentOf(x))) {
                   //自身是父亲节点的右孩子 左旋父亲 指针并指向父亲节点
                    x = parentOf(x);
                    rotateLeft(x);
                    //对应情况B
                }
                //此时指针已经变成原父亲节点 逻辑走到情况C 所以此时的叔叔节点并未发生变化 因此叔叔节点仍然为黑色
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
                //父亲涂红色 祖父涂黑色 父亲右旋 对应情况C
            }
        } 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));
                //对应情况A
            } else {
                if (x == leftOf(parentOf(x))) {
            //自身是父亲节点的左孩子 右旋父亲 指针并指向父亲节点
                    x = parentOf(x);
                    rotateRight(x);
            //对应情况B
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
                //父亲涂黑色 祖父涂红色 父亲左旋 对应情况C
            }
        }
    }
    root.color = BLACK; //根节点必须为黑色
}

 

参考 http://www.cnblogs.com/hilow/p/3949188.html

http://blog.csdn.net/chenssy/article/details/26668941

http://www.cnblogs.com/daoluanxiaozi/p/3340382.html

https://zhuanlan.zhihu.com/p/24795143?refer=dreawer

http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html

共有 人打赏支持
粉丝 104
博文 135
码字总数 117114
×
Mr_Qi
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: