史上最清晰的红黑树讲解(上)

本文以Java TreeMap为例,从源代码层面,结合详细的图解,剥茧抽丝地讲解红黑树(Red-Black tree)的插入,删除以及由此产生的调整过程。

总体介绍

Java TreeMap实现了SortedMap接口,也就是说会按照key的大小顺序对Map中的元素进行排序,key大小的评判可以通过其本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator)。

TreeMap底层通过红黑树(Red-Black tree)实现,也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。其具体算法实现参照了《算法导论》。

出于性能原因,TreeMap是非同步的(not synchronized),如果需要在多线程环境使用,需要程序员手动同步;或者通过如下方式将TreeMap包装成(wrapped)同步的:

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

红黑树是一种近似平衡的二叉查找树,它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。具体来说,红黑树是满足如下条件的二叉查找树(binary search tree):

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点必须是黑色
  3. 红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色)。
  4. 对于每个节点,从该点至null(树尾端)的任何路径,都含有相同个数的黑色节点。

在树的结构发生改变时(插入或者删除操作),往往会破坏上述条件3或条件4,需要通过调整使得查找树重新满足红黑树的条件。

预备知识

前文说到当查找树的结构发生改变时,红黑树的条件可能被破坏,需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类:一类是颜色调整,即改变某个节点的颜色;另一类是结构调整,集改变检索树的结构关系。结构调整过程包含两个基本操作:左旋(Rotate Left),右旋(RotateRight)

左旋

左旋的过程是将x的右子树绕x逆时针旋转,使得x的右子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

TreeMap中左旋代码如下:

//Rotate Left
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;
    }
}

右旋

右旋的过程是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

TreeMap中右旋代码如下:

//Rotate Right
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;
    }
}

方法剖析

get()

get(Object key)方法根据指定的key值返回对应的value,该方法调用了getEntry(Object key)得到相应的entry,然后返回entry.value。因此getEntry()是算法的核心。算法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找,直到找到满足k.compareTo(p.key) == 0entry

具体代码如下:

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
    ......
    if (key == null)//不允许key值为null
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然顺序
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)//向左找
            p = p.left;
        else if (cmp > 0)//向右找
            p = p.right;
        else
            return p;
    }
    return null;
}

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于getEntry()方法;如果没有找到则会在红黑树中插入新的entry,如果插入之后破坏了红黑树的约束,还需要进行调整(旋转,改变某些节点的颜色)。

public V put(K key, V value) {
    ......
    int cmp;
    Entry<K,V> parent;
    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);//创建并插入新的entry
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);//调整
    size++;
    return null;
}

上述代码的插入部分并不难理解:首先在红黑树上找到合适的位置,然后创建新的entry并插入(当然,新插入的节点一定是树的叶子)。难点是调整函数fixAfterInsertion(),前面已经说过,调整往往需要1.改变某些节点的颜色,2.对某些节点进行旋转。

调整函数fixAfterInsertion()的具体代码如下,其中用到了上文中提到的rotateLeft()rotateRight()函数。通过代码我们能够看到,情况2其实是落在情况3内的。情况4~情况6跟前三种情况是对称的,因此图解中并没有画出后三种情况,读者可以参考代码自行理解。

//红黑树调整函数fixAfterInsertion()
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) {//如果y为null,则视为BLACK
                setColor(parentOf(x), BLACK);              // 情况1
                setColor(y, BLACK);                        // 情况1
                setColor(parentOf(parentOf(x)), RED);      // 情况1
                x = parentOf(parentOf(x));                 // 情况1
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);                       // 情况2
                    rotateLeft(x);                         // 情况2
                }
                setColor(parentOf(x), BLACK);              // 情况3
                setColor(parentOf(parentOf(x)), RED);      // 情况3
                rotateRight(parentOf(parentOf(x)));        // 情况3
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);              // 情况4
                setColor(y, BLACK);                        // 情况4
                setColor(parentOf(parentOf(x)), RED);      // 情况4
                x = parentOf(parentOf(x));                 // 情况4
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);                       // 情况5
                    rotateRight(x);                        // 情况5
                }
                setColor(parentOf(x), BLACK);              // 情况6
                setColor(parentOf(parentOf(x)), RED);      // 情况6
                rotateLeft(parentOf(parentOf(x)));         // 情况6
            }
        }
    }
    root.color = BLACK;
}

remove()

remove(Object key)的作用是删除key值对应的entry,该方法首先通过上文中提到的getEntry(Object key)方法找到key值对应的entry,然后调用deleteEntry(Entry<K,V> entry)删除对应的entry。由于删除操作会改变红黑树的结构,有可能破坏红黑树的约束,因此有可能要进行调整。

有关remove()的具体讲解将放到下一篇博文当中,敬请期待!

  • 原文:www.cnblogs.com/CarpenterLee/p/5503882.html

原文发布于微信公众号 - Java团长(javatuanzhang)

原文发表时间:2018-04-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏聊聊技术

原 初学算法 - 求凸包的Garham's

47710
来自专栏菩提树下的杨过

数据结构C#版笔记--啥夫曼树(Huffman Tree)与啥夫曼编码(Huffman Encoding)

哈夫曼树Huffman tree 又称最优完全二叉树,切入正题之前,先看几个定义 1、路径 Path 简单点讲,路径就是从一个指定节点走到另一个指定节点所经过的...

2779
来自专栏ACM算法日常

PAT甲级 1053 Path of Equal Weight

Given a non-empty tree with root R, and with weight Wi assigned to each tree nod...

1395
来自专栏鸿的学习笔记

一些常见数据结构的实现

insert_left(get_right_child(tree), 'E')

431
来自专栏机器学习入门

LWC 53:694. Number of Distinct Islands

LWC 53:694. Number of Distinct Islands 传送门:694. Number of Distinct Islands Probl...

2557
来自专栏小怪聊职场

爬虫课程(四)|深度优先和广度优先算法

7874
来自专栏腾讯数据库技术

如何利用红黑树实现排名?

2333
来自专栏ACM算法日常

年会Party(树形动态规划)- HDU 1520

There is going to be a party to celebrate the 80-th Anniversary of the Ural Stat...

812
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

3437
来自专栏C语言及其他语言

【每日一题】问题 1255: 能量项链

在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有 N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的...

702

扫码关注云+社区

领取腾讯云代金券