TreeMap，TreeSet（红黑树，TreeMap的基本属性和结构、常见操作，TreeSet的基本属性和结构、常见操作，为什么使用红黑树/B+树）_treeset是什么树

1. 红黑树

java中的TreeMap，TreeSet都是基于红黑树进行实现。

① 红黑树——特殊的二叉查找树

• 红黑树(Red-Black Tree，简称R-B Tree)，它是一种特殊的二叉查找树。
• 红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于左孩子的键值，小于右孩子的键值。

② 红黑树的特征

红黑树有如下两个特征：

• 每个节点都有颜色，不是黑色就是红色；
• 在插入和删除的过程中，要遵循保持这些颜色的不同排列规则，即要遵循红-黑规则。

红-黑规则：

• 每个节点或者是黑色，或者是红色。
• 根节点是黑色。
• 每个叶子节点（null） 是黑色。注意： 这里叶子节点，是指为空的叶子节点！
• 如果一个节点是红色的，则它的子节点必须是黑色的。反之不一定，也就是从每个叶子到根的所有路径上不能有两个连续的红色节点。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点，即相同的黑色高度。

③ 红黑树的效率

• 红黑树的查找、插入和删除时间复杂度都为$O(log{2}^N)$，额外的开销是每个节点的存储空间都稍微增加了一点，因为一个存储红黑树节点的颜色变量。
• 插入和删除的时间要增加一个常数因子，因为要进行旋转，平均一次插入大约需要一次旋转，因此插入的时间复杂度还是$O(log{2}^N)$,但实际上比普通的二叉树是要慢的。

2. TreeMap

① TreeMap是有序的key-value集合

• TreeMap是一个有序的key-value集合，它是通过红黑树实现的。
• 映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator （比较器）进行排序，具体取决于使用的构造方法。

// 默认构造函数，TreeMap中的，节点顺序依赖于对key的自然排序
TreeMap()
// 指定Tree的比较器
TreeMap(Comparator<? super K> comparator)
1
2
3
4

• TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是$O(log{2}^n)$。

② 类图结构

public class TreeMap<K,V> extends AbstractMap<K,V> 
	implements NavigableMap<K,V>, Cloneable, java.io.Serializable
1
2

• Map 接口： 定义将键值映射到值的对象，Map规定不能包含重复的键值，每个键最多可以映射一个值,这个接口是用来替换Dictionary类。
• AbstractMap 类： 提供了一个Map骨架的实现,尽量减少了实现Map接口所需要的工作量
• SortedMap 接口： 定义按照key排序的Map结构，规定key-value是根据键key值的自然排序进行排序的，或者根据构造key-value时设定的比较器进行排序。
• NavigableMap 接口： 是SortedMap接口的子接口，在其基础上扩展了针对搜索目标返回最近匹配项的导航方法，例如返回小于（大于）某个key的节点集合，返回具有最大（最小）key的节点；如果不存在这样的键，则返回null
• Cloneable 接口： 意味着TreeMap可以被克隆： 通过显式的调用Object.clone()方法，合法的对该类实例进行字段复制。
  注意： 如果在没有实现Cloneable接口的实例上调用Obejct.clone()方法，会抛出CloneNotSupportException异常。
• Serializable 接口： 意味着TreeMap支持序列化，能够通过序列化传输
• TreeMap是非线程安全的，只适用于单线程环境下。

③ 基本属性和数据结构

//自定义比较器，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
private final Comparator<? super K> comparator;
// Entry节点，这个表示红黑树的根节点
private transient Entry<K,V> root;
// TreeMap中元素的个数
private transient int size = 0;
// TreeMap修改次数
private transient int modCount = 0;

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;//对于key值
    V value;//对于value值
    Entry<K,V> left;//指向左子树的引用
    Entry<K,V> right;//指向右子树的引用
    Entry<K,V> parent;//指向父节点的引用
    boolean color = BLACK;//节点的颜色默认是黑色，black为true
    ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

④ 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);
            // 如果key < 根节点，则在左子树查找插入位置
            if (cmp < 0)
                t = t.left;
            // 如果key > 根节点，则在右子树查找插入位置
            else if (cmp > 0)
                t = t.right;
            // 否则，重置根节点的值
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 如果没有指定比较器，则使用key进行自然排序
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        // 将key强制转换为Comparable<? super K>对象
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            // 如果key < 根节点，则在左子树查找插入位置
            if (cmp < 0)
                t = t.left;
            // 如果key > 根节点，则在右子树查找插入位置
            else if (cmp > 0)
                t = t.right;
            // 否则，重置根节点的值
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    // 如果key < 红黑树中最小节点parent，则新节点成为parent的左节点
    if (cmp < 0)
        parent.left = e;
    // 如果key > 红黑树中最小节点parent，则新节点成为parent的右节点
    else
        parent.right = e;
    // 节点插入完后，需要调整红黑树的高度和颜色
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

• 校验根节点： 校验根节点是否为空，若为空则根据传入的key-value的值创建一个新的节点，若根节点不为空则继续第二步。（size、modCount的变化，return null）
• 寻找插入位置： TreeMap内部是红黑树实现的，因此插入元素时，实际上是会去遍历左子树或者右子树。遍历左子树还是右子树，需要根据具体的比较原则决定。如果制定了比较器，则根据比较器进行比较，否则按key的自然排序进行比较。其中，如果cmp < 0， 则遍历其左子树，cmp > 0遍历其右子树，cmp =0则更改value；否则直到检索出合适的叶子节点为止。（size、modCount的变化，return null）

⑤ get方法

public V get(Object key) {
    //获取元素，若为空则返回null否则返回其值
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
    //构造器不为空则调用以下方法
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    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;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

• get(Object key)方法调用了getEntry(Object key)方法，判断getEntry(Object key)方法的返回值是否为null。如果为null，则表明没有与key对应的节点；get(Object key)方法也返回null。否则，get(Object key)方法返回p.value。
• getEntry方法主要流程如下：

1. 比较器校验： 判断是否指定比较器，若指定则调用getEntryUsingComparator，若没有则进行第二步
2. 空值校验： key若为空直接抛出NullPointerException，从这点可以看出TreeMap是不允许Key-value为空的
3. 遍历返回： 遍历整个红黑树若找到对应的值则返回，否则返回null值

⑥ remove(Object key)方法

public V remove(Object key) {
    // 获取key对应的节点
    Entry<K,V> p = getEntry(key);
    // 节点不存在
    if (p == null)
        return null;
 
    V oldValue = p.value;
    // 删除节点
    deleteEntry(p);
    return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
   modCount++;      //修改次数 +1
    size--;          //元素个数 -1

    /*
     * 被删除节点的左子树和右子树都不为空，那么就用 p节点的中序后继节点代替 p 节点
     * successor(P)方法为寻找P的替代节点。规则是右分支最左边，或者 左分支最右边的节点
     * ---------------------（1）
     */
    if (p.left != null && p.right != null) {  
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }

    //replacement为替代节点，如果P的左子树存在那么就用左子树替代，否则用右子树替代
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    /*
     * 删除节点，分为上面提到的三种情况
     * -----------------------（2）
     */
    //如果替代节点不为空
    if (replacement != null) {
        replacement.parent = p.parent;
        /*
         *replacement来替代P节点
         */
        //若P没有父节点，则跟节点直接变成replacement
        if (p.parent == null)
            root = replacement;
        //如果P为左节点，则用replacement来替代为左节点
        else if (p == p.parent.left)
            p.parent.left  = replacement;
      //如果P为右节点，则用replacement来替代为右节点
        else
            p.parent.right = replacement;

        //同时将P节点从这棵树中剔除掉
        p.left = p.right = p.parent = null;

        /*
         * 若P为红色直接删除，红黑树保持平衡
         * 但是若P为黑色，则需要调整红黑树使其保持平衡
         */
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) {     //p没有父节点，表示为P根节点，直接删除即可
        root = null;
    } else {      //P节点不存在子节点，直接删除即可
        if (p.color == BLACK)         //如果P节点的颜色为黑色，对红黑树进行调整
            fixAfterDeletion(p);

        //删除P节点
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

• remove(Object key)方法通过getEntry(Object key)方法获取对应节点，若节点为null，则返回null；节点非null，则调用deleteEntry(Entry<K,V>)方法删除对应的节点，并返回oldValue。
• deleteEntry(Entry<K,V>)方法首先更新modCount和size的值，然后根据分情况讨论，删除对应节点。删除节点后，调用fixAfterDeletion(p)方法，进行红黑树的结构调整。

参考链接：
JAVA学习-TreeMap详解
Java提高篇（二七）-----TreeMap
Java集合之TreeMap详解

3. TreeSet

① TreeSet是有序集合

• TreeSet是一个有序集合，是基于TreeMap实现的。即TreeSet是通过红黑树实现的。
• TreeSet中的元素支持2种排序方式：自然排序或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。

// 默认构造函数。使用该构造函数，TreeSet中的元素按照自然排序进行排列。
TreeSet()
// 指定TreeSet的比较器
TreeSet(Comparator<? super E> comparator)
1
2
3
4

• TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。

② 类图结构

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
1
2

• TreeSet 继承于AbstractSet，所以它是一个Set集合，具有Set的属性和方法。
• TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
• TreeSet 实现了Cloneable接口，意味着它能被克隆。
• TreeSet 实现了java.io.Serializable接口，意味着它支持序列化。
• TreeSet是sortedSet的唯一实现类

SortedSet subSet(Object  fromElement,Object toElement) ：返回这个Set的子集合，范围从fromElement（包含）到toElement（不包含）
SortedSet headSet(Object toElement):返回这个Set的子集合，范围小于到toElement的子集合 
SortedSet tailSet(Object fromElement):返回这个Set的子集合，范围大于或等于到fromElement的子集合 
1
2
3

• TreeSet不是线程安全的。

③ 成员变量

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // 用于保存TreeMap的对象，会在构造函数当中赋值TreeMap对象
    private transient NavigableMap<E,Object> m;

    // TreeMap当中所有的value都是保存的PRESENT对象
    private static final Object PRESENT = new Object();
}
1
2
3
4
5
6
7
8
9

④ add()方法

• TreeSet常用的操作其实都是针对TreeMap进行的操作，基本上都是TreeMap对外提供的api。

//添加元素，调用m.put方法实现
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
1
2
3
4

⑤ contains()方法

//查找是否包含元素，调用m.containsKey(o)方法实现
public boolean contains(Object o) {
    return m.containsKey(o);
}
1
2
3
4

⑥ remove()方法

//删除方法，调用m.remove()方法实现
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}
1
2
3
4

⑦ 遍历方法

• Iterator顺序遍历

for(Iterator iter = set.iterator(); iter.hasNext(); ) { 
    iter.next();
}   
1
2
3

4. 问题汇总

1. 为什么使用红黑树，而不是普通的二叉查找树

• 红黑树是一种自平衡的二叉查找树，这样就可以保证快速检索指定节点。
• 由于它是自平衡的，插入、删除需要增加一个常数因子，用于实现树的自平衡。因此，插入和删除的时间复杂度比普通的二叉查找树慢，不是真正的$O(log{2}^N)$。

2. 为什么数据库却使用B+树？

• B+是多分支的平衡树，多分支和自平衡两个特性都有利于快速检索指定节点。
• 尤其是多分支，使得查找效率提升明显，更适合数据库中数据量大的情况。比如，分支数为10，记录数10000000，$log10^{10000000}=7$，只需访问7次便可以查找到指定数据。
  $$查找次数=log分支{数}^{记录数}$$
  参考链接：
  Java基础知识之容器（六：TreeSet详解）
  Java 集合系列17之 TreeSet详细介绍(源码解析)和使用示例
  Java集合 — TreeSet底层实现和原理（源码解析）
  java源码-TreeSet