TreeSet 是 Java 中实现有序集合的一个类，它基于红黑树实现，可以保证集合中的元素按照自然顺序或自定义顺序排序。在本文中，我们将详细介绍 TreeSet 的实现原理，并结合源码和示例代码进行解释。
- TreeSet 的底层数据结构
TreeSet 的底层数据结构是红黑树，红黑树是一种自平衡二叉搜索树，它可以保证在插入、删除和查找元素时，时间复杂度为 O(log n)。红黑树的特点如下：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点都是黑色，并且是空节点（NIL节点）。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
TreeSet 中的红黑树实现了 SortedSet 接口，该接口扩展了 Set 接口，增加了对元素排序的支持。
- TreeSet 的构造方法
TreeSet 提供了多个构造方法，用于创建不同类型的有序集合。其中最常用的构造方法如下：
- TreeSet()：创建一个空的 TreeSet，按照元素的自然顺序排序。
- TreeSet(Comparator comparator)：创建一个空的 TreeSet，按照指定的 Comparator 排序。
- TreeSet(SortedSet s)：创建一个新的 TreeSet，包含指定 SortedSet 中的所有元素。
- TreeSet(Collection c)：创建一个新的 TreeSet，包含指定 Collection 中的所有元素，按照元素的自然顺序排序。
- 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() 方法比较元素的大小，然后将元素插入到红黑树中。在插入过程中，需要维持红黑树的平衡，因此需要进行旋转和重新着色等操作。
- 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() 方法将节点从红黑树中移除。在移除过程中，需要维持红黑树的平衡，因此需要进行旋转和重新着色等操作。
- 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
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 时，需要根据具体的应用场景进行选择和优化。
