封面画师：ツチヤ 封面ID：82630820
本文参考视频：小马哥教育(SEEMYGO) 2019 年 恋上数据结构与算法（第一季）
源码仓库：mofan212/data-structure-and-algorithm (github.com)
辅助学习网址：数据结构和算法动态可视化
1. 集合
1.1 简介
集合（Set），特点是 不存放重复的元素。根据这个特性，集合可用于以下场景：
- 存放新增 IP，统计新增 IP 量
- 存放词汇，统计词汇量
集合接口：
public interface Set<E> {
int size();
boolean isEmpty();
void clear();
boolean contains(E element);
void add(E element);
void remove(E element);
void traversal(Visitor<E> visitor);
public static abstract class Visitor<E> {
boolean stop;
// 记得设置成公共的方法
public abstract boolean visit(E element);
}
}思考：集合的内部实现能否直接利用学过的数据结构？
答案是可以的。可以使用 动态数组 、 链表 和 红黑树 来实现。
1.2 ListSet
编写接口 Set，其中包含集合的一些方法：
public interface Set<E> {
int size();
boolean isEmpty();
void clear();
boolean contains(E element);
void add(E element);
void remove(E element);
/**
* 遍历接口
* 集合内元素是无序、互斥的
* 动态数组、链表有索引，可以直接循环遍历
* 集合没有，只能提供接口
*/
void traversal(Visitor<E> visitor);
public static abstract class Visitor<E> {
boolean stop;
public abstract boolean visit(E element);
}
}使用链表实现集合，编写 ListSet，链表使用以前编写的双向链表（也可以使用 JDK 的双向链表）：
// 使用链表实现集合
public class ListSet<E> implements Set<E> {
private List<E> list = new LinkedList<>();
@Override
public int size() {
return list.size();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void clear() {
list.clear();
}
@Override
public boolean contains(E element) {
return list.contains(element);
}
@Override
public void add(E element) {
// if (list.contains(element)) return;
int index = list.indexOf(element);
if (index != List.ELEMENT_NOT_FOUND) {
// 存在相同元素时，新元素覆盖旧元素
list.set(index, element);
} else {
// 不存在相同元素时，直接添加
list.add(element);
}
}
@Override
public void remove(E element) {
int index = list.indexOf(element);
if (index != List.ELEMENT_NOT_FOUND) {
list.remove(index);
}
}
@Override
public void traversal(Visitor<E> visitor) {
if (visitor == null) return;
int size = list.size();
for (int i = 0; i < size; i++) {
if (visitor.visit(list.get(i))) return;
}
}
}编写测试代码进行测试：
public static void main(String[] args) {
Set<Integer> listSet = new ListSet<>();
listSet.add(10);
listSet.add(11);
listSet.add(11);
listSet.add(12);
listSet.add(10);
listSet.traversal(new Set.Visitor<Integer>() {
@Override
public boolean visit(Integer element) {
System.out.println(element);
return false;
}
});
}预测输出： 10 11 12
1.3 TreeSet
使用上述的集合接口 Set，然后使用二叉树来实现集合。编写 TreeSet，二叉树使用以前学习的红黑树，需要将以前的代码拷贝到当前 Project 或 Module 中。
如果使用以前红黑树的代码，需要修改一个地方。给表示二叉树的类 BinaryTree 中的抽象接口 Visitor 的抽象方法 visit(E element) 添加一个访问修饰符 public。最初这个抽象方法的访问修饰符是缺省的，如今表示红黑树的类和表示集合的类处于不同的包中，因此需要添加一个 public，否则无法访问。
public static abstract class Visitor<E> {
// 遍历终止标志 true：终止 false：全遍历
boolean stop;
// 如果返回true，表示停止遍历
public abstract boolean visit(E element);
}编写 TreeSet 的代码：
public class TreeSet<E> implements Set<E> {
private RBTree<E> tree = new RBTree<>();
@Override
public int size() {
return tree.size();
}
@Override
public boolean isEmpty() {
return tree.isEmpty();
}
@Override
public void clear() {
tree.clear();
}
@Override
public boolean contains(E element) {
return tree.contains(element);
}
@Override
public void add(E element) {
// 使用红黑树时，默认去重
tree.add(element);
}
@Override
public void remove(E element) {
tree.remove(element);
}
@Override
public void traversal(Visitor<E> visitor) {
tree.inorder(new BinaryTree.Visitor<E>() {
@Override
public boolean visit(E element) {
return visitor.visit(element);
}
});
}
}测试代码：
public static void main(String[] args) {
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(12);
treeSet.add(10);
treeSet.add(7);
treeSet.add(11);
treeSet.add(10);
treeSet.add(11);
treeSet.add(9);
treeSet.traversal(new Set.Visitor<Integer>() {
@Override
public boolean visit(Integer element) {
System.out.println(element);
return false;
}
});
}1.4 性能对比
从时间复杂度分析，使用双向链表实现的集合中：
- 是否包含某个元素，最坏时间复杂度为
- 添加元素至集合， 时间复杂度为
- 从集合中删除元素， 时间复杂度为
而使用红黑树实现集合的三种功能的时间复杂度都为
除此之外，我们可以添加大量的数据进集合中，比较这两种方式的性能。比如，统计 JDK 源码中有多少个不一样的单词，然后比较两种实现方式所消耗的时间，最后可以得出：
红黑树实现的集合性能远大于链表实现的集合性能 。
1.5 局限性
使用红黑树实现的集合虽然流弊，但是它有一个局限性。😲
红黑树是二叉搜索树的一种，因此红黑树的节点除了满足自身特定的要求外，默认满足二叉搜索树的特点。二叉搜索树有一个很重要的特点： 节点具有可比较性 。向使用红黑树实现的集合中添加元素时，这些元素必须具备可比较性，否则无法添加，而对于使用链表实现的集合就没有这样的限制。
由于这个特点，继续完善 TreeSet，添加两个构造方法，就像编写二叉搜索树的代码一样，让具有可比较性的元素才能添加至红黑树实现的集合中：
public class TreeSet<E> implements Set<E> {
private RBTree<E> tree;
public TreeSet() {
this(null);
}
public TreeSet(Comparator<E> comparator) {
tree = new RBTree<>(comparator);
}
// --snip--
}如果有一个需求：「实现添加没有可比较性元素至集合，而性能还能达到红黑树那样高性能」，这样的需求能实现吗？
答案是肯定的，可以使用 哈希表，但本文暂不介绍。
2. 映射
2.1 简介
映射（Map），在有些编程语言中也被叫做字典（dictionary），比如 Python、 Objective-C、Swift 等。
那什么是映射呢？所谓映射、字典，就是可以通过一个键（Key）找到唯一的值（value）。键不能重复，一个键对应一个值；值可以重复，一个值可以被多个键指向。
映射接口：
public interface Map<K, V> {
int size();
boolean isEmpty();
void clear();
V put(K key, V value);
V get(K key);
V remove(K key);
boolean containsKey(K key);
boolean containsValue(V value);
void traversal(Visitor<K, V> visitor);
public static abstract class Visitor<K, V> {
boolean stop;
// 记得设置成公共的方法
public abstract boolean visit(K key, V value);
}
}思考：映射的内部实现能否直接利用学过的数据结构？
答案是可以的。类似 Set，Map 可以直接利用之前学习的 链表、BST（AVL 树、红黑树）等数据结构来实现。
前面设计集合时，已经知道红黑树的性能远好于链表，因此映射的底层也选用红黑树。
2.2 节点设计
如果使用红黑树实现映射，那么红黑树的一个节点需要存储两个值：一个表示键，一个表示值。
前面编写的红黑树中一个节点只能存储一个值，同时范型也只有一个 RBTree<E>，而这里需要两个范型。只写 K 不行，只写 V 也不行，可以额外定义一个类，这个类有两个范型 KV<K, V>，在这个类中定义映射的范型，最后在红黑树的范型中嵌套这个类：
public class TreeMap<K, V> implements Map<K, V> {
private static class KV<K, V> {
K key;
V value;
}
private RBTree<KV<K, V>> rbTree = new RBTree<>();
// 省略实现的方法
// --snip--
}上述方式虽然可以实现，但是使用嵌套不是很「优雅」🍷，因此需要换一种方式。直接将 TreeMap 看成一个红黑树的类，只不过这是个特殊的红黑树，不仅拥有红黑树的特点，还满足了映射的要求。
可以将红黑树中涉及的节点类 Node 和 BRNode 的部分代码拷贝到这个类中。最终结果如下：
public class TreeMap<K, V> implements Map<K, V> {
private static final boolean RED = false;
private static final boolean BLACK = true;
// 省略实现的方法
// --snip--
private static class Node<K, V> {
K key;
V value;
boolean color = RED;
Node<K, V> left; // 左节点
Node<K, V> right; // 右节点
Node<K, V> parent; // 父节点
public Node(K key, V value, Node<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public boolean isLeaf() {
return left == null && right == null;
}
public boolean hasTwoChildren() {
return left != null && right != null;
}
// 判断当前节点是否是其父节点的左子节点
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
// 判断当前节点是否是其父节点的右子节点
public boolean isRightChild() {
return parent != null && this == parent.right;
}
// 获取兄弟节点
public Node<K, V> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
}
}2.3 接口实现
既然将 TreeMap<K, V> 看成一棵红黑树，那么就要在这个类中实现红黑树的功能。利用以前编写的红黑树的代码进行改造，改造的主要内容如下：
- 修改节点范型为
<K, V> - 注意现在一个节点中存放了两个值，分别是 key 和 value
- 修改个别方法的访问修饰符，比如：
protected改为private
理一下需要哪些方法：
- 首先红黑树是 BST，节点需要有可比性，规定 key 拥有可比较性，而 value 没有，甚至可以是空。因此首先需要一个比较方法
compare()，与之对应的还需要添加一个成员变量comparator - 在接口设计中，需要实现根据 key 获取 value 和判断某个 key 是否存在的接口，这两个接口可以使用一个方法
node()，这个方法可以根据 key 来获取节点 - 还需要实现判断某个 value 是否存在，由于由于 value 不具备可比较性，同时允许为
null。因此，只能遍历红黑树节点，一个一个找。故将层序遍历的代码拷贝到containsValue()中，还需要编写一个方法valEquals()用于判断传递的值和红黑树中节点的 value 是否相等 - 然后是实现遍历映射的接口，为了让遍历结果有意义，选择中序遍历这棵红黑树
- 最后就是红黑树的重头戏，添加、删除节点。在这之前，需要将红黑树中编写的 辅助方法 复制到当前类
- 添加、删除红黑树中的节点需要进行旋转的操作，因此还需要将 左、右旋转 的代码复制到当前类
- 删除红黑树节点时，真正删除的其实是红黑树的叶子节点，因为需要将删除节点的前驱或后继节点的值覆盖删除节点，因此还需要将 获取前驱、后继节点 的代码复制到当前类
- 准备工作已经完善！然后复制添加节点的代码到
put()中，并复制添加节点后的处理方法到afterPut()中 - 对删除方法进行重载，编写
remove(Node<K, V> node)方法。复制删除节点的代码到该方法中，并复制删除节点后的处理方法到afterRemove()中
⚠️ 警告！以下涉及大量代码，请注意折叠！ ⚠️
⚠️ 已删除部分代码注释，可前往 数据结构之红黑树 一文查看。 ⚠️
完整代码
public class TreeMap<K, V> implements Map<K, V> {
private static final boolean RED = false;
private static final boolean BLACK = true;
private int size; // 节点个数
private Node<K, V> root; // 根节点
private Comparator<K> comparator;
public TreeMap() {
this(null);
}
public TreeMap(Comparator<K> comparator) {
this.comparator = comparator;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
root = null;
size = 0;
}
@Override
public V put(K key, V value) { // 使用Key进行比较
keyNotNullCheck(key);
// 添加第一个节点 （根节点）
if (root == null) {
root = new Node<>(key, value, null);
size++;
// 添加节点后的处理 传入参数类型为Node
afterPut(root);
return null;
}
// 添加的不是第一个节点
// 找到插入节点的父节点
Node<K, V> parent = root;
Node<K, V> node = root;
int cmp = 0;
while (node != null) {
cmp = compare(key, node.key);
parent = node; // 保存父节点
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
node.key = key; // 相等时覆盖
V oldValue = node.value;
node.value = value;
return oldValue;
}
}
// 看看插入到父节点的哪个位置
Node<K, V> newNode = new Node<>(key, value, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// 添加节点后的处理 传入参数类型为Node
afterPut(newNode);
return null;
}
@Override
public V get(K key) {
Node<K, V> node = node(key);
return node != null ? node.value : null;
}
@Override
public V remove(K key) {
return remove(node(key));
}
@Override
public boolean containsKey(K key) {
return node(key) != null;
}
@Override
public boolean containsValue(V value) {
/** 由于 value 不具备可比较性，同时允许为 null
* 因此，只能遍历红黑树节点，一个一个找
* 在这里使用层序遍历
* */
if (root == null) {
return false;
}
Queue<Node<K, V>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<K, V> node = queue.poll();
if (valEquals(value, node.value)) return true;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return false;
}
@Override
public void traversal(Visitor<K, V> visitor) {
if (visitor == null) return;
traversal(root, visitor);
}
// 使用中序遍历
private void traversal(Node<K, V> node, Visitor<K, V> visitor) {
if (node == null || visitor.stop) return;
traversal(node.left, visitor);
if (visitor.stop) return;
visitor.visit(node.key, node.value);
traversal(node.right, visitor);
}
private boolean valEquals(V v1, V v2) {
return v1 == null ? v2 == null : v1.equals(v2);
}
private V remove(Node<K, V> node) {
if (node == null) return null;
size--;
V oldValue = node.value;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<K, V> s = successor(node);
// 用后继节点的值覆盖被删除节点的值
node.key = s.key;
node.value = s.value;
// 变量node指向其后继节点，等待后续删除
node = s;
}
// 删除node节点（node的度必然为1或0）
Node<K, V> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node度为1
// 更改parent
replacement.parent = node.parent;
// 更改node的parent的left、right的指向
if (node.parent == null) { // node度为1，且为根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
afterRemove(replacement);
} else if (node.parent == null) { // node度为0，是叶子节点，并且是根节点
root = null;
// 被删除的节点
// 删除根节点后其实可以不用进行操作，即： afterRemove可以省略
// afterRemove(node);
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else {
node.parent.right = null;
}
// 被删除的节点
afterRemove(node);
}
return oldValue;
}
private void afterRemove(Node<K, V> node) {
if (isRed(node)) {
black(node);
return;
}
// 获取被删除节点的父节点
Node<K, V> parent = node.parent;
// 被删除节点是根节点
if (parent == null) return;
boolean left = parent.left == null || node.isLeftChild();
Node<K, V> sibling = left ? parent.right : parent.left;
if (left) { // 被删除节点在左边，兄弟节点在右边
if (isRed(sibling)) { // 被删除节点兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
// 更换兄弟
sibling = parent.right;
}
// 此时兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点一个红色子节点都没，父节点向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
// 父节点为黑色时，下溢，进行递归
afterRemove(parent);
}
} else { // 兄弟节点至少有一个红色子节点，向兄弟节点借元素
// 兄弟节点左子节点是黑色，先对兄弟进行旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
// 旋转后，重置兄弟节点位置
sibling = parent.right;
}
// 先染色兄弟节点，再染色父节点：兄弟节点跟随父节点染色
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else { // 被删除节点在右边，兄弟节点在左边
if (isRed(sibling)) { // 被删除节点兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}
// 此时兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点一个红色子节点都没，父节点向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟节点至少有一个红色子节点，向兄弟节点借元素
// 兄弟节点左子节点是黑色，先对兄弟进行旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
private Node<K, V> predecessor(Node<K, V> node) {
if (node == null) return null;
// 前驱节点在左子树中
Node<K, V> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 从“祖宗节点”中寻找前驱节点
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// node.parent == null || node == node.parent.right
return node.parent;
}
private Node<K, V> successor(Node<K, V> node) {
if (node == null) return null;
// 后继节点在右子树中
Node<K, V> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从“祖宗节点”中寻找后继节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
// node.parent == null || node == node.parent.left
return node.parent;
}
// 根据元素找寻节点
private Node<K, V> node(K key) {
Node<K, V> node = root;
while (node != null) {
int cmp = compare(key, node.key);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else { // cmp < 0
node = node.left;
}
}
return null;
}
private void afterPut(Node<K, V> node) {
Node<K, V> parent = node.parent;
// 添加节点是根节点时 或 上溢到根节点
if (parent == null) {
black(node);
return;
}
// 如果添加节点的父节点是黑色，直接返回
if (isBlack(parent)) return;
// 获取叔父节点
Node<K, V> uncle = parent.sibling();
// 获取祖父节点
Node<K, V> grand = red(parent.parent);
if (isRed(uncle)) { // 叔父节点是红色时[B树节点上溢]
black(parent);
black(uncle);
// 把祖父节点当作新添加的节点
afterPut(grand);
return;
}
// 叔父节点不是红色时
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
black(parent);
} else { // LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
if (node.isLeftChild()) { // RL
black(node);
rotateRight(parent);
} else { // RR
black(parent);
}
rotateLeft(grand);
}
}
// 左旋转
private void rotateLeft(Node<K, V> grand) {
Node<K, V> parent = grand.right;
Node<K, V> child = parent.left;
// 旋转
grand.right = child;
parent.left = grand;
// 旋转后
afterRotate(grand, parent, child);
}
// 右旋转
private void rotateRight(Node<K, V> grand) {
Node<K, V> parent = grand.left;
Node<K, V> child = parent.right;
// 旋转
grand.left = child;
parent.right = grand;
// 旋转后
afterRotate(grand, parent, child);
}
private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
// 让 parent 成为根节点
parent.parent = grand.parent;
if (grand.isLeftChild()) {
grand.parent.left = parent;
} else if (grand.isRightChild()) {
grand.parent.right = parent;
} else { // 没有父节点， grand是根节点
root = parent;
}
// 更新其他节点的父节点
if (child != null) {
child.parent = grand;
}
grand.parent = parent;
}
/****辅助方法****/
// 节点染色
private Node<K, V> color(Node<K, V> node, boolean color) {
if (node == null) return node;
node.color = color;
return node;
}
// 节点染成红色
private Node<K, V> red(Node<K, V> node) {
return color(node, RED);
}
// 节点染成黑色
private Node<K, V> black(Node<K, V> node) {
return color(node, BLACK);
}
// 查看某一节点的颜色
private boolean colorOf(Node<K, V> node) {
return node == null ? BLACK : node.color;
}
// 判断节点颜色是否是黑色
private boolean isBlack(Node<K, V> node) {
return colorOf(node) == BLACK;
}
// 判断节点颜色是否是红色
private boolean isRed(Node<K, V> node) {
return colorOf(node) == RED;
}
private int compare(K k1, K k2) {
if (comparator != null) {
return comparator.compare(k1, k2);
}
// 未创建比较器时，强制节点拥有比较性
return ((Comparable<K>) k1).compareTo(k2);
}
// Key 空值检查
private void keyNotNullCheck(K key) {
if (key == null) {
throw new IllegalArgumentException("element must not be null");
}
}
private static class Node<K, V> {
K key;
V value;
boolean color = RED;
Node<K, V> left; // 左节点
Node<K, V> right; // 右节点
Node<K, V> parent; // 父节点
public Node(K key, V value, Node<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public boolean isLeaf() {
return left == null && right == null;
}
public boolean hasTwoChildren() {
return left != null && right != null;
}
// 判断当前节点是否是其父节点的左子节点
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
// 判断当前节点是否是其父节点的右子节点
public boolean isRightChild() {
return parent != null && this == parent.right;
}
// 获取兄弟节点
public Node<K, V> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
}
}测试代码：
static void test1() {
Map<String, Integer> map = new TreeMap<>();
map.put("c", 2);
map.put("a", 5);
map.put("b", 6);
map.put("a", 8);
// 遍历出来结果是从小到大的
map.traversal(new Map.Visitor<String, Integer>() {
@Override
public boolean visit(String key, Integer value) {
System.out.println(key + "_" + value);
return false;
}
});
}根据阅读 JDK 源码得到的启发，删除红黑树的根节点时，其实可以不用进行任何操作，直接将根节点设置为 null 即可。同时，将 remove() 方法中删除根节点时调用的 afterRemove() 方法删除。但是不能够删除 afterRemove() 方法中判断节点的父节点为空时进行的操作，因为这个判断不仅在删除节点是根节点时要执行，下溢到根节点时也要执行。
根据上述操作，向红黑树中添加第一个节点（根节点）时，只需要将该节点染黑即可，不需要进行其他操作。即： 删除 put() 方法中添加根节点后调用的 afterPut() 方法，并在其前添加 black(root);。注意不能够删除 afterPut() 方法中判断节点的父节点为空时进行的操作，因为这个判断不仅在添加节点是根节点时要执行，上溢到根节点时也要执行。
2.4 Map 与 Set
在设计的红黑树中，如果添加了重复元素，默认新元素会覆盖旧元素，即： 默认去重。
前面的映射 Map 是用红黑树实现的，同时是将 Map 中的 Key 作为比较标准，即： Key 是唯一的。
在 Map 中，Key 和 Value 是一一对应的，如果只看 Key，那么 Key 是唯一的。这似乎与集合 Set 有些关系。
是的！ 集合 Map 只看 Key 或去掉 Value（Map 的所有 Key 组合在一起），就可以看成集合 Set。因此， Set 可以间接利用 Map 来做内部实现。
具体实现
拷贝一份集合 Set 的接口到当前目录中，然后编写 TreeSet 类。
/**
* @author 默烦
* @date 2020/7/21
*/
public class TreeSet<E> implements Set<E> {
Map<E, Object> map = new TreeMap<>();
@Override
public int size() {
return map.size();
}
@Override
public boolean isEmpty() {
return map.isEmpty();
}
@Override
public void clear() {
map.clear();
}
@Override
public boolean contains(E element) {
return map.containsKey(element);
}
@Override
public void add(E element) {
map.put(element, null);
}
@Override
public void remove(E element) {
map.remove(element);
}
@Override
public void traversal(Visitor<E> visitor) {
map.traversal(new Map.Visitor<E, Object>() {
@Override
public boolean visit(E key, Object value) {
return visitor.visit(key);
}
});
}
}测试方法：
static void test2() {
Set<String> set = new TreeSet<>();
set.add("a");
set.add("c");
set.add("b");
set.add("c");
set.add("c");
set.traversal(new Set.Visitor<String>() {
@Override
public boolean visit(String element) {
System.out.println(element);
return false;
}
});
}2.5 代码启发
在编写实现 TreeMap 的方法时，其中有一个接口是判断当前 Map 中是否存在某个 value，由于在设计时 value 不具备比较性，且 value 可以为空。因此在实现这个接口时，需要编写一个方法 valEquals()，用于判断传入的值与当前 Map 的 value 是否相等。这个方法是像下面这样的：
private boolean valEquals(V v1, V v2) {
return v1 == null ? v2 == null : v1.equals(v2);
}说明一下上述代码的含义： 先判断 v1 是否为 null，如果 v1 为 null，再判断 v2 是否为 null，v2 为 null 时，返回 true，不为 null 时，返回 false；如果最初判断 v1 不为 null，则直接使用 equals() 方法判断 v1 是否与 v2 相等，相等返回 true，不相等返回 false。
根据上述这段代码，可以回想起在 实现动态数组或链表 时，有一个名为 indexOf() 的方法，这个方法用于判断某个元素在当前数组或链表中的位置。
在动态数组和链表中允许元素为 null，可以向其中插入 null。在实现 indexOf() 时，需要判断传递的值是否 null，如果不判断直接使用 equals() 进行比较，会出现空指针异常。
动态数组中的 indexOf() 方法如下：
public int indexOf(E element) {
// 处理空值
if (element == null) { // 1
for (int i = 0; i < size; i++) {
if (elements[i] == null) return i;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) return i; // n
}
} // 一共 n + 1 次判断
return ELEMENT_NOT_FOUND;
}根据 valEquals() 方法的启发，可以将 indexOf() 方法改成成以下代码：
public int indexOf(E element) {
for (int i = 0; i < size; i++) {
// 一共 2n 次判断
if (valEquals(element, elements[i])) return i; // 2n
}
return ELEMENT_NOT_FOUND;
}
private boolean valEquals(Object v1, Object v2) {
// 判断两次
return v1 == null ? v2 == null : v1.equals(v2);
}这样改写可以减少了代码量，但是会存在另外一个问题： 判断的次数。
注意：这两种方式的时间复杂度是一样的。
对于第一种方式： 如果传递的值为 null 只需要判断一次；如果不为 null，最坏情况下需要判断 次。总共需要判断 次。
对于第二种方式： 无论传递的值是否为 null，都需要判断 次。总共需要判断 次。
虽然第二种减少代码量，但是效率相对于第一种是要低一点的。因此，在 JDK 源码中，动态数组也是采用的第一种方式进行比较。
同样的还有在 TreeMap 中的添加节点时执行的代码，由于使用的是红黑树实现的，添加节点时一定会进行比较，然后满足二叉搜索树的性质时才成功添加。
下面是自行实现的比较方法：
下面是 JDK 源码的比较方式：
经过比较，可以很简单地发现：JDK 源码的判断次数比自行实现的判断次数少，也说明了 JDK 源码的效率更高。
果然还是 JDK 流弊！
3. 额外补充
3.1 NavigableSet
NavigableSet 是 Java 集合框架中 SortedSet 接口的子接口，扩展了 SortedSet 的功能，提供了更强大的导航方法，允许开发者基于元素的排序规则快速查找、遍历或获取子集。
public interface NavigableSet<E> extends SortedSet<E> {
// --snip--
}在 JDK 中，TreeSet 是 NavigableSet 最常用的实现类，基于红黑树实现，保证元素有序且操作时间复杂度为 。
在日常刷题中，某些场景下可能需要用到 TreeSet，并且会使用到 NavigableSet 中的一些方法，因此在此简单介绍下。
除此之外，TreeSet 对应了 TreeMap，NavigableSet 也对应的 NavigableMap，两个接口中的方法很类似，关于 NavigableMap 就不再赘述。
查找与目标元素最接近的方法
| 方法 | 描述 |
|---|---|
E lower(E e) | 返回严格小于 e 的最大元素，没有返回 null |
E floor(E e) | 返回小于或等于 e 的最大元素，没有返回 null |
E ceiling(E e) | 返回大于或等于 e 的最小元素，没有返回 null |
E higher(E e) | 返回严格大于 e 的最小元素，没有返回 null |
NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(2, 4, 6, 8));
set.lower(5); // 返回 4（严格小于5的最大元素）
set.floor(5); // 返回 4（小于等于5的最大元素）
set.ceiling(5); // 返回 6（大于等于5的最小元素）
set.higher(5); // 返回 6（严格大于5的最小元素）获取并移除元素
| 方法 | 描述 |
|---|---|
E pollFirst() | 移除并返回第一个元素，集合为空时返回 null |
E pollLast() | 移除并返回最后一个元素，集合为空时返回 null |
继承
SortedSet的方法
| 方法 | 描述 |
|---|---|
E first() | 返回第一个元素（集合为空抛出异常） |
E last() | 返回最后一个元素（集合为空抛出异常） |
