封面画师：ツチヤ封面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 性能对比

从时间复杂度分析，使用双向链表实现的集合中：

是否包含某个元素，最坏时间复杂度为 O(n)
添加元素至集合，时间复杂度为 O(n)
从集合中删除元素，时间复杂度为 O(n)

而使用红黑树实现集合的三种功能的时间复杂度都为 O(logn)

除此之外，我们可以添加大量的数据进集合中，比较这两种方式的性能。比如，统计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);
    }
    
    ......
}

如果我现在有一个需求：“实现添加没有可比较性元素至集合，而性能还能达到红黑树那样高性能”，这样的需求能实现吗？

答案是肯定的，可以使用哈希表，但本文暂不介绍。

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<>();
    
    // 省略实现的方法
    ......
}

上述方式虽然可以实现，但是使用嵌套不是很“优雅”🍷 ，因此需要换一种方式。我们可以直接将TreeMap就看成一个红黑树的类，只不过这是个特殊的红黑树，不仅拥有红黑树的特点，还满足了映射的要求。

因此，我们可以将红黑树中涉及的节点类Node和BRNode的部分代码拷贝到这个类中。最终结果如下：

public class TreeMap<K, V> implements Map<K, V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    
    // 省略实现的方法
    ......
    
    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;
        }
    });
}

PS：根据阅读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是否相等。这个方法是像下面这样的：

1
2
3

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，则直接使用equal()方法判断 v1 是否与 v2 相等，相等返回 true ，不相等返回 false。

根据上述这段代码，我们可以回想起在实现动态数组或链表时，有一个名为indexOf()的方法，这个方法用于判断某个元素在当前数组或链表中的位置。

在动态数组和链表中，我们允许元素为null，可以向其中插入null。由于这个原因，我们在实现indexOf()时，需要判断传递的值是否null，如果不判断直接使用equal()进行比较，会出现空指针异常。

动态数组中的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);
}