TreeSet 是 Java 中实现有序集合的一个类,它基于红黑树实现,可以保证集合中的元素按照自然顺序或自定义顺序排序。在本文中,我们将详细介绍 TreeSet 的实现原理,并结合源码和示例代码进行解释。

  1. TreeSet 的底层数据结构

TreeSet 的底层数据结构是红黑树,红黑树是一种自平衡二叉搜索树,它可以保证在插入、删除和查找元素时,时间复杂度为 O(log n)。红黑树的特点如下:

  • 每个节点要么是红色,要么是黑色。
  • 根节点是黑色。
  • 所有叶子节点都是黑色,并且是空节点(NIL节点)。
  • 如果一个节点是红色的,则它的子节点必须是黑色的。
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

TreeSet 中的红黑树实现了 SortedSet 接口,该接口扩展了 Set 接口,增加了对元素排序的支持。

  1. TreeSet 的构造方法

TreeSet 提供了多个构造方法,用于创建不同类型的有序集合。其中最常用的构造方法如下:

  • TreeSet():创建一个空的 TreeSet,按照元素的自然顺序排序。
  • TreeSet(Comparator comparator):创建一个空的 TreeSet,按照指定的 Comparator 排序。
  • TreeSet(SortedSet s):创建一个新的 TreeSet,包含指定 SortedSet 中的所有元素。
  • TreeSet(Collection c):创建一个新的 TreeSet,包含指定 Collection 中的所有元素,按照元素的自然顺序排序。
  1. TreeSet 的添加操作

TreeSet 提供了多种添加操作,如 add()、addAll() 等。这些操作的实现原理基本相同,都是通过将元素插入到红黑树中实现的。以 add() 操作为例,其代码如下:

 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
public boolean add(E e) {
    return add(e, null);
}

private boolean add(E e, Node<E> root) {
    if (root == null) {
        root = new Node<E>(e, null, null, null, BLACK);
        size = 1;
    } else {
        int cmp = compare(e, root.item);
        if (cmp < 0)
            root.left = add((E) e, root.left);
        else if (cmp > 0)
            root.right = add((E) e, root.right);
        else
            return false;

        if (root.color == RED && root.left != null && root.left.color == RED
            && root.right != null && root.right.color == RED)
            root.color = BLACK;

        if (root.parent != null && root.parent.color == RED && root.color == RED)
            root = balanceInsertion(root, root.parent);
    }

    return true;
}

可以看出,add() 操作通过 compare() 方法比较元素的大小,然后将元素插入到红黑树中。在插入过程中,需要维持红黑树的平衡,因此需要进行旋转和重新着色等操作。

  1. TreeSet 的删除操作

TreeSet 提供了多种删除操作,如 remove()、clear() 等。这些操作的实现原理基本相同,都是通过将元素从红黑树中移除实现的。以 remove() 操作为例,其代码如下:

 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
public boolean remove(Object o) {
    Node<E> p = getNode(o);
    if (p == null)
        return false;

    delete(p);
    return true;
}

private void delete(Node<E> p) {
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {
        Node<E> s = successor(p);
        p.item = s.item;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    Node<E> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(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;
        }
    }
}

可以看出,remove() 操作通过 getNode() 方法查找元素所在的节点,然后通过 delete() 方法将节点从红黑树中移除。在移除过程中,需要维持红黑树的平衡,因此需要进行旋转和重新着色等操作。

  1. TreeSet 的遍历操作

TreeSet 提供了多种遍历操作,如 iterator()、descendingIterator() 等。这些操作的实现原理基本相同,都是通过遍历红黑树实现的。以 iterator() 操作为例,其代码如下:

 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
public Iterator<E> iterator() {
    return new AscendingIterator();
}

private class AscendingIterator implements Iterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private Node<E> expectedModCount;

    AscendingIterator() {
        expectedModCount = modCount;
        if (size != 0) {
            next = getFirst();
        }
    }

    public boolean hasNext() {
        return next != null;
    }

    public E next() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (next == null)
            throw new NoSuchElementException();
        lastReturned = next;
        next = successor(next);
        return lastReturned.item;
    }

    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        TreeSet.this.remove(lastReturned.item);
        expectedModCount = modCount;
        lastReturned = null;
    }
}

可以看出,iterator() 操作通过 AscendingIterator 内部类实现,该内部类实现了 Iterator 接口,并提供了 hasNext()、next() 和 remove() 等方法。在遍历过程中,需要维持红黑树的平衡,因此需要进行旋转和重新着色等操作。

  1. 示例代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import java.util.TreeSet;

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(3);
        treeSet.add(1);
        treeSet.add(2);
        System.out.println(treeSet);  // [1, 2, 3]

        treeSet.remove(1);
        System.out.println(treeSet);  // [2, 3]

        for (Integer integer : treeSet) {
            System.out.println(integer);  // 2, 3
        }
    }
}

总之,TreeSet 是 Java 中实现有序集合的一个类,它基于红黑树实现,可以保证集合中的元素按照自然顺序或自定义顺序排序。TreeSet 提供了多种添加、删除和遍历操作,并且在维持红黑树的平衡时,需要进行旋转和重新着色等操作。在使用 TreeSet 时,需要根据具体的应用场景进行选择和优化。