红黑树

栏目: 数据库 · 发布时间: 5年前

内容简介:微信公众号:如有问题或建议,请在下方留言最近更新:2018-09-05

微信公众号:如有问题或建议,请在下方留言

最近更新:2018-09-05

二分查找树(BST)

1、定义:

二分查找树又称二叉查找树、二叉 排序 树,英文缩写为BST,即Binary Search Tree。该数据结构的出现,是为了提高查找的效率。之所以成为二分查找树,是因为其采用二分查找的算法。

2、特性:

  • 若左子树不为空,左子树上所有节点的值均小于根节点的值
  • 若右子树不为空,右子树上所有节点的值均大于根节点的值
  • 左右子树又分别是一棵二分查找树

3、示例:

下图是一个典型的二分查找树:

红黑树
图注:二分查找树

查找节点10:

  1. 查看根节点5,因为10>5,往右子树走
红黑树
图注:查看根节点5
  1. 查看节点8,因为10>8,往右子树走
红黑树
图注:查看节点8
  1. 查看节点15,因为10<15,往左子树走
红黑树
图注:查看节点15
  1. 查看节点12,因为10<12,往左子树走
红黑树
图注:查看节点12
  1. 查看节点10,正是我们要找的节点
红黑树
图注:查看节点10

4、思考:

虽然二叉查找树提高了查询的效率,但是依旧存在着缺陷,请看下面例子:

红黑树
图注:依次插入6、5、4、3、2

当依次插入6、5、4、3、2时,发现树成了线性形式,在此种情况下,查找效率大打折扣,因此就有了自平衡的二叉查找树,名为红黑树。

红黑树(RBT)

1、定义:

红黑树,是一个自平衡的二叉排序树,英文简称为RBT,即Red Black Tree。每个节点上增加了颜色属性,要么为红,要么为黑。

2、特性:

  • 每个节点要么为红色,要么为黑色
  • 根节点为黑色
  • 每个叶子节点(NIL)是黑色 [ 注意: 这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
  • 不允许连续两个红色节点
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点

3、示例:

下图是一个典型的红黑树:

红黑树
图注:红黑树

4、思考:

针对于BST中提到的缺陷,依次插入6、5、4、3、2,红黑树是如何处理的呢?此处不做解答,请继续往下看。

红黑树实践-TreeMap

1、TreeMap.Entry:

首先我们来看下TreeMap中存储键值对的类-TreeMap.Entry,该类定义了红黑树的数据结构。查看其成员变量,除了存储key、value外,还存储了左节点、右节点、父节点、颜色(默认为黑色)。

 1 static final class Entry<K,V> implements Map.Entry<K,V> {
 2    K key;
 3    V value;
 4    Entry<K,V> left;
 5    Entry<K,V> right;
 6    Entry<K,V> parent;
 7    boolean color = BLACK;
 8
 9    /**
10     * Make a new cell with given key, value, and parent, and with
11     * {@code null} child links, and BLACK color.
12     */
13    Entry(K key, V value, Entry<K,V> parent) {
14        this.key = key;
15        this.value = value;
16        this.parent = parent;
17    }
18
19    /**
20     * Returns the key.
21     *
22     * @return the key
23     */
24    public K getKey() {
25        return key;
26    }
27
28    /**
29     * Returns the value associated with the key.
30     *
31     * @return the value associated with the key
32     */
33    public V getValue() {
34        return value;
35    }
36
37    /**
38     * Replaces the value currently associated with the key with the given
39     * value.
40     *
41     * @return the value associated with the key before this method was
42     *         called
43     */
44    public V setValue(V value) {
45        V oldValue = this.value;
46        this.value = value;
47        return oldValue;
48    }
49
50    public boolean equals(Object o) {
51        if (!(o instanceof Map.Entry))
52            return false;
53        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
54
55        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
56    }
57
58    public int hashCode() {
59        int keyHash = (key==null ? 0 : key.hashCode());
60        int valueHash = (value==null ? 0 : value.hashCode());
61        return keyHash ^ valueHash;
62    }
63
64    public String toString() {
65        return key + "=" + value;
66    }
67}
复制代码

2、添加元素代码实现:

 1public V put(K key, V value) {
 2    //找到合适的位置插入Entry元素
 3    Entry<K,V> t = root;
 4    if (t == null) {
 5        compare(key, key); // type (and possibly null) check
 6
 7        root = new Entry<>(key, value, null);
 8        size = 1;
 9        modCount++;
10        return null;
11    }
12    int cmp;
13    Entry<K,V> parent;
14    // split comparator and comparable paths
15    Comparator<? super K> cpr = comparator;
16    if (cpr != null) {
17        do {
18            parent = t;
19            cmp = cpr.compare(key, t.key);
20            if (cmp < 0)
21                t = t.left;
22            else if (cmp > 0)
23                t = t.right;
24            else
25                return t.setValue(value);
26        } while (t != null);
27    }
28    else {
29        if (key == null)
30            throw new NullPointerException();
31        @SuppressWarnings("unchecked")
32            Comparable<? super K> k = (Comparable<? super K>) key;
33        do {
34            parent = t;
35            cmp = k.compareTo(t.key);
36            if (cmp < 0)
37                t = t.left;
38            else if (cmp > 0)
39                t = t.right;
40            else
41                return t.setValue(value);
42        } while (t != null);
43    }
44    Entry<K,V> e = new Entry<>(key, value, parent);
45    if (cmp < 0)
46        parent.left = e;
47    else
48        parent.right = e;
49    //进行插入后的平衡调整
50    fixAfterInsertion(e);
51    size++;
52    modCount++;
53    return null;
54}
复制代码

因为插入后可能带来红黑树的不平衡,所以需要进行平衡调整,方法无非两种:

  • 变色
  • 旋转(左旋或者右旋)
 1private void fixAfterInsertion(Entry<K,V> x) {
 2    //默认插入元素颜色为红色
 3    x.color = RED;
 4
 5    //只要x不为根且父亲节点为红色就继续调整
 6    while (x != null && x != root && x.parent.color == RED) {
 7        //父节点为爷爷节点的左节点
 8        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
 9            //获取右叔节点
10            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
11            //右叔节点为红色(此时父节点也为红色)
12            if (colorOf(y) == RED) {
13                //变色
14                //父节点改为黑色
15                setColor(parentOf(x), BLACK);
16                //右叔节点改为黑色
17                setColor(y, BLACK);
18                //爷爷节点改成红色
19                setColor(parentOf(parentOf(x)), RED);
20                //爷爷节点所在的子树已平衡,所以让x指向爷爷节点,继续往上调整
21                x = parentOf(parentOf(x));
22            } else {
23                //父亲节点在爷爷节点的左边,而x在父亲节点的右边,则需要调整到同一侧
24                if (x == rightOf(parentOf(x))) {
25                    //x指向父节点
26                    x = parentOf(x);
27                    //以x进行左旋
28                    rotateLeft(x);
29                }
30                //变色
31                //父节点改为黑色
32                setColor(parentOf(x), BLACK);
33                //右叔节点改为黑色-本身已经为黑色
34                //爷爷节点改为红色
35                setColor(parentOf(parentOf(x)), RED);
36                //右叔为黑,变色后左边黑色多与右边,故以爷爷节点为中心右旋
37                rotateRight(parentOf(parentOf(x)));
38            }
39        } else {//父节点为爷爷节点的右节点
40            //获取左叔节点
41            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
42            //左叔节点为红色(此时父节点也为红色)
43            if (colorOf(y) == RED) {
44                //变色
45                //父节点改为黑色
46                setColor(parentOf(x), BLACK);
47                //左叔节点改为黑色
48                setColor(y, BLACK);
49                //爷爷节点改为红色
50                setColor(parentOf(parentOf(x)), RED);
51                //爷爷节点所在的子树已平衡,所以让x指向爷爷节点,继续往上调整
52                x = parentOf(parentOf(x));
53            } else {
54                //父亲节点在爷爷节点的右边,而x在父亲节点的左边,则需要调整到同一侧
55                if (x == leftOf(parentOf(x))) {
56                    //x指向父节点
57                    x = parentOf(x);
58                    //以x进行右旋
59                    rotateRight(x);
60                }
61                //变色
62                //父节点改为黑色
63                setColor(parentOf(x), BLACK);
64                //左叔节点改为黑色-本身已经为黑色
65                //爷爷节点改为红色
66                setColor(parentOf(parentOf(x)), RED);
67                //左叔为黑,变色后右边黑色多与左边,故以爷爷节点为中心左旋
68                rotateLeft(parentOf(parentOf(x)));
69            }
70        }
71    }
72    //根节点设置为黑色
73    root.color = BLACK;
74}
复制代码

3、添加元素流程图:

红黑树
图注:插入元素调整流程

4、添加元素精简流程图:

红黑树
图注:插入元素调整流程

通过上述流程图可以看出,红黑树的调整是采用局部平衡的方式,从下往上依次处理,最终达到整棵树的平衡。

5、实践:

依次插入2、3、4、5、7、8、16、15、14、10、12,画出红黑树插入过程。

红黑树
图注:插入过程

上述例子,涵盖了元素插入中遇到的所有情况。相信通过学习优化后的流程图,对于红黑树的元素插入问题,大家的思路是足够清晰的。

总结

本文主要是通过二分查找树的缺陷,引出了红黑树的说明。通过分析TreeMap插入元素的源码,整理出红黑树调整的流程图,最后通过示例来加深对于红黑树的理解。

此时,再回到BST中的缺陷问题,红黑树是如何进行解决的,想必大家都已经有了答案。

文章的最后,感谢大家的支持,如有疑问,欢迎大家留言,一起讨论和学习。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员的自我修养

程序员的自我修养

陈逸鹤 / 清华大学出版社 / 2017-5 / 49.00

程序员作为一个职业、也作为一个群体,正逐渐从幕后走向前台,并以他们自己的能力加速改变着世界,也改变着人们生活的方方面面。然而,对于程序员,特别是年轻程序员们来说,如何理解自己的职业与发展,如何看待自己的工作与生活,这些问题往往比那些摆在面前的技术难题更让他们难以解答。 这本书从一个成熟程序员、一名IT管理者的角度,以杂记的形式为大家分享关于国内程序员职业生涯、个人发展、编程中的实践与认知乃至......一起来看看 《程序员的自我修养》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

html转js在线工具
html转js在线工具

html转js在线工具