【数据结构与算法】第七篇：集合，映射

一.集合

1、集合的特点

◼ 集合的特点
不存放重复的元素
对于集合它的主要用途是常用于去重。
集合我们主要记住它不存放重复元素的特点，根据此特点又细化了出许多具体的功能：
1.✓ 存放新增 IP，统计新增 IP 量
2.✓ 存放词汇，统计词汇量

2、集合的接口设计

对于集合接口我们主要是维护它的遍历方法以及访问器。
除此以外在实现集合各个方法是一定要维护它的不重复性

public interface Set<E> {
	int size();	//元素数量
	boolean isEmpty(); // 是否为空
	void claer(); // 清空集合
	boolean contains(E element); // 是否包含element元素
	void add(E element); // 添加element元素
	void remove(E element); // 删除element元素
	void traversal(Visitor<E> visitor); // 通过访问器遍历
	
	public static abstract class Visitor<E>{ // 访问器
		boolean stop;
		public abstract boolean visit(E element);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.链表实现集合（listSet）

package set;

import list.LinkedList;
import list.List;

public class listSet<E>implements Set<E>{
    private final List<E> list=new LinkedList<>();
    public int size(){
        return list.size();
    }
    public boolean isEmpty(){

        return list.isEmpty();
    }
    public void clear(){
        list.clear();
    }
    public boolean contains(E element){
        return list.contains(element);
    }
    //这里就不能写List.add(element)因为集合不能有重复的元素
    //这样写就默认重复的元素可有加进去了
   public  void add(E element){
        if(list.contains(element)){
            return;
        }
        list.add(element);
       /**
        *int index=list.indexOf(element);
        *        if(index!=List.ELEMENT_NOT_FOUND){
        *            list.set(index,element);
        *        }else {
        *            list.add(element);
        *        }
        */

   }
   public void remove(E element){
        if(list.indexOf(element)!=List.ELEMENT_NOT_FOUND) {
            list.remove(list.indexOf(element));
        }
    }

    public void traversal(Visitor<E> visitor) {
        if(visitor==null)
        {
            return;
        }
        int n=list.size();
        for (int i = 0; i <n ; i++) {
            if(visitor.visit(list.get(i))){
                return;
            }
        }
    }
}

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

4.红黑树实现集合（TreeSet）

用红黑树实现集合有一个局限性，红黑树中的元素必须具有可比较性，所以最好传入一个比较器comparator

package set;

import tree.BinaryTree;
import tree.RBTree;

import java.util.Comparator;
@SuppressWarnings("unchecked")
public class TreeSet<E>implements Set<E> {
    private  RBTree<E> tree=new RBTree<>();

    public TreeSet()
    {
        this(null);
    }

    //由于红黑树具有局限性-->数据必须具有比较性。所以最好传入一个比较器
    public TreeSet(Comparator<E> comparator){
        tree=new RBTree<>(comparator);

    }
    @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) {
                //用现有Set理的visitor来控制限定条件
                return visitor.visit(element);
            }
        });
    }
}

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

二. 映射

1.映射的特点

映射（ Map） 在有些编程语言中也叫做字典（dictionary，比如 Python、Objective-C、Swift 等）。
既然是字典的功能,那么必然会有两个值。key和value通过key（线索）来找到value。

2.映射的接口设计

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);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.红黑树实现映射

package map;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

//红黑树实现映射
//因为现在是两个泛型，红黑树每个节点都存储这两个数据
//如果还是继承以前的节点是不现实的--->所以这里我们需要自己构建一个红黑树
@SuppressWarnings("unchecked")
public class TreeMap <k,v>implements Map<k,v>{
    private static final boolean RED=true;
    private static final boolean BLACK=false;
    int size;
    Node<k,v> root;
   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;
    }

    private void checkIsNull(k key){
    if(key==null)
    {
        throw new UnsupportedOperationException("key不合法");
    }
    }
    @Override
    public v put(k key, v value) {
        checkIsNull(key);
        // 添加第一个节点
        if (root == null) {
            //一开始的写法是new Node<>(element,null);对应值和父节点

            root = createNode(key,value, null);
            size++;

            // 新添加节点之后的处理（巧妙之处---写在父类的add中追加判断调整）
            //如果主函数创建的是单纯的二叉搜索树则方法体是空不做处理，如果是AvL是则
            //遵循重写规则进行恢复
            afterPut(root);
            //这里的返回是返回它之前的节点，根节点之前没有节点
            return null;
        }

        // 添加的不是第一个节点
        // 找到父节点
        Node<k,v> parent = root;
        Node<k,v> node = root;
        int cmp = 0;
        do {
            cmp = compare(key ,node.key);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // 相等，这里注意如果要是相等key,value都赋值给这个节点，返回老value
                //相等就覆盖
                node.key = key;
                v oldValue=node.value;//node被覆盖之前的的value;
                node.value=value;
                return oldValue;
            }
        } while (node != null);

        // 看看插入到父节点的哪个位置
        //到这里就是已经红黑树之前没有这个数据，这完全是新添加的节点，而且添加的位置就是node的位置
        Node<k,v> newNode = createNode(key,value, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;

        // 新添加节点之后的处理
        afterPut(newNode);

        return null;
    }
    private Node<k,v> createNode(k key,v value,Node<k,v> parent){
        return new Node<>(key,value,parent);
    }
    private void afterPut(Node<k,v> node)
    {
        Node<k,v> parent=node.parent;
        //这个代码块包括两种情况--->（1）第一次添加节点（2）叔父节点是红色的情况下，上溢到了根节点
        if(parent==null){
            black(node);
            root=node;
            return;
        }
        if(isBlack(parent))
        {
            //排除本身就满足条件的哪四种情况,不需要额外处理
            return;
        }
        Node<k,v> uncle=parent.sibling();
        Node<k,v> grand=parent.parent;
        //叔父节点是红色-->发生上溢
        if(isRed(uncle)){
            //上溢分裂的情况
            black(parent);
            black(uncle);
            //把祖父节点当成一个新添加的节点加到上面-->解决上溢
            afterPut(red(grand));
            return;
        }
        //叔父节点不是红节点
        if(parent.isLeftChild())
        {
            //由于染色顺序并不影响所以可以把统一的染色顺序放在前面red(grand)
            //LL RR 单旋
            if(node.isLeftChild()){//LL
                black(parent);
                red(grand);
            }else {//LR
                black(node);
                red(grand);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else{
            if(node.isRightChild())//RR
            {
                black(parent);
                red(grand);
            }else{//RL
                black(node);
                red(grand);
                rotateRight(parent);
            }
            rotateLeft(grand);
        }
    }
    private int compare(k e1,k e2){
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<k>)e1).compareTo(e2);
    }

    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);
    }

    protected 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节点
            root = parent;
        }

        // 更新child的parent
        if (child != null) {
            child.parent = grand;
        }

        // 更新grand的parent
        grand.parent = parent;
    }

    private Node<k,v> color(Node<k,v> node,boolean color){
        //代码习惯：染色的同时返回被染色的节点便于对其进行一些操作
        if(node==null)
        {
            return null;
        }
        node.color=color;
        return node;
    }
    public Node<k,v> red(Node<k,v> node)
    {
        return color(node,RED);
    }
    public Node<k,v> black(Node<k,v> node)
    {
        return color(node,BLACK);
    }

    //判断颜色
    private boolean iscolor(Node<k,v> node)
    {
        return node==null?BLACK:node.color;

    }
    public boolean isRed(Node<k,v> node)
    {
        return iscolor(node)==RED;

    }
    public boolean isBlack(Node<k,v> node){
        return iscolor(node)==BLACK;
    }


    @Override
    public v get(k key) {
        Node<k,v> node=node(key);
        return node!=null?node.value:null;
    }
    //给定key值删除
    @Override
    public v remove(k key) {
        return remove(node(key));
    }
    //给定节点删除
    private v remove(Node<k,v> node) {
        if (node == null) return null;
        size--;

        v old=node.value;
        if (node.hasTwoChildren()) { // 度为2的节点
            // 找到后继节点
            Node<k,v> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值
            node.key = s.key;
            node.value=s.value;
            // 删除后继节点
            node = s;
        }

        // 删除node节点（node的度必然是1或者0）
        Node<k,v> replacement = node.left != null ? node.left : node.right;

        if (replacement != null) { // node是度为1的节点
            replacement.parent=node.parent;
            if(node.parent==null){//node是度为一的根节点
                root=replacement;
            }else if(node==node.parent.left){
                node.parent.left=replacement;
            }else{
                node.parent.right=replacement;
            }
            afterRemove(node,replacement);

            //除了这个if代码块就都是叶子节点了
        } else if (node.parent == null) { // node是叶子节点并且是根节点
            root=null;
            afterRemove(node, null);
        } else { // node是叶子节点，但不是根节点
            if (node == node.parent.left) {
                node.parent.left=null;
            } else { // node == node.parent.right
                node.parent.right=null;
            }
            //细节：这里不管删除操作如何进行--都没由对node，parent进行销毁,parent仍然存在
            // 删除节点之后的处理
            afterRemove(node, null);
        }
        return old;
    }

    private Node<k,v> node(k element) {
        Node<k,v> node = root;
        while (node != null) {
            int cmp = compare(element, node.key);
            if (cmp == 0) return node;
            if (cmp > 0) {
                node = node.right;
            } else { // cmp < 0
                node = node.left;
            }
        }
        return null;
    }
    private void afterRemove(Node<k,v> node,Node<k,v> replacement){
        //b树类比红黑树一定是删除的最后一层。如果要删除的是红色，由于黑色是主体，
        // 所以要删除的节点一定度为0的红色叶子节点，不会影响原本红黑树的规则，所以不用调整，直接结束函数
        if(isRed(node)){
            return;
        }
        /**
         * 一定要清楚afterRemove的作用是删除之后的调整，不是主体删除方法。
         * 作用：对于不符合红黑树性质的操作及时进行调整
         *
         * 问：对于删除度为2的黑色节点，是不是可是囊括
         * 答：可以：因为删除度为2的黑色节点，找到前驱后，还是删除红色节点不用处理，染黑替代节点并不影响，因为已经删除
         *
         * 为什么黑色节点的替代不能为黑色节点
         * 因为b树的删除都是在最后一层进行操作，如果黑色节点子节点依然是一个黑色节点，由于黑色才是主体
         * 不会融入到一个节点中，所以只会向下增高一层，不符合删除在最后一层操作。，
         */
        if(isRed(replacement)){
            //染黑：避免出现连续两个红色节点
            black(replacement);
            return;
        }
        /**
         * 处理最后一种情况-->删除度为0的黑色叶子节点的调整方法
         *
         * 删除度为0的黑色叶子节点的调整方法肯定会造成下溢
         * 补救:(1)看看兄弟节点能不能借
         * a:兄弟节点能借的条件：1.兄弟节点是黑色 2.兄弟节点至少拥有一个红色子节点
         * ----------------------------------------
         * 能借后做出的操作：
         * 进行旋转操作
         * 旋转之后的中心节点继承 parent 的颜色
         * 旋转之后的左右节点染为 BLACK（因为此时红色子节点已经旋上去了）
         *
         * 旋转有三种情况：LL LR LL
         *
         * 🤩🤩特殊情况1：
         * 如果被删除的是黑色，它的父节点也是黑色，删除后黑色父节点也会向下合并，造成父节点继续下溢
         *只需将这个父节点当成一个新的被删除的黑色节点递归调用afterRemove方法，重复利用代码
         *
         * 🤩🤩特殊情况2：
         * 🚩🚩🚩如果兄弟节点是红色，对于b树的性质，【黑色节点与其红色节点组成一个b树节点】
         * 可知：红色节点一定在父节点中-->红色的节点的子节点一定是黑的，可以借侄子的【想办法将侄子变成兄弟】
         * 强制将侄子变成兄弟再次套用兄弟节点是黑色是的代码
         *-----------------------------------------------
         */

        Node<k,v> parent=node.parent;
        if(parent==null)
        {
            return;
        }
        //这么写有问题：node已经被删除--->指向node的线已经断了
        //Node sibling =node.sibling();
        /**
         *  需要间接求出兄弟节点
         *  只需知道被删除的节点先前是在parent的左边还是右边，进而知道sibling是parent.left还是parent.right
         */

        /**
         *    为什么以此作为判定标准：
         *         因为在二叉搜索树的删除中，删除黑色叶子节点,已经将一边置为null
         *         if (node == node.parent.left) {
         *             node.parent.left=null;
         *         } else { // node == node.parent.right
         *             node.parent.right=null;
         *         }
         */
        //有特殊情况
        boolean left=parent.left==null||node.isLeftChild();
        Node<k,v> sibling=left?parent.right:parent.left;
        if(left){//node是在左子树，兄弟节点在右边
            if(isRed(sibling)){
                black(parent);
                red(sibling);
                rotateLeft(parent);
                //更新兄弟
                sibling=parent.right;
            }

            //兄弟节点是黑色-->判断是否有红色子节点

            //没有一个红色子节点--->父节点向下合并

            /**
             * 为什么以父节点是不是黑的为判定条件
             * 因为如果父节点是红色，那它肯定不是主体，向下合并后，parent本身并没有下溢
             * 如果父节点是黑色，那他向下合并后，自身也会下溢
             *
             */
            if(isBlack(sibling.left)&&isBlack(sibling.right)){
                boolean parentBlack=isBlack(parent);
                black(parent);
                red(sibling);
                //这种情况父节点向下合并，父节点的位置也会下溢
                if(parentBlack){
                    //三黑局面没有替代节点
                    afterRemove(parent,null);
                }

            }else {//至少有一个红色子节点
                //判断是LL LR.....
                //三种情况:LL LR (LL或LR)
                //可以先统一进行左旋转然后在统一进行右旋转
                //如何区分LR左子节点是黑的
                if(isBlack(sibling.left)) {//LR情况

                    rotateLeft(sibling);
                    //左旋转后兄弟节点已经发生了变化
                    sibling = parent.left;
                }
                //LL 情况
                //现在的sibling已经更新过是图中的78
                color(sibling,iscolor(parent));
                black(parent);
                black(sibling.left);
                rotateRight(parent);
            }

        }else {//node是在右子树，兄弟节点在左边
            //🤩🤩特殊情况2：
            if(isRed(sibling)){
                black(parent);
                red(sibling);
                rotateRight(parent);
                //更新兄弟
                sibling=parent.left;
            }

            //兄弟节点是黑色-->判断是否有红色子节点

            //没有一个红色子节点--->父节点向下合并

            /**
             * 为什么以父节点是不是黑的为判定条件
             * 因为如果父节点是红色，那它肯定不是主体，向下合并后，parent本身并没有下溢
             * 如果父节点是黑色，那他向下合并后，自身也会下溢
             *
             */
            if(isBlack(sibling.left)&&isBlack(sibling.right)){
                boolean parentBlack=isBlack(parent);
                black(parent);
                red(sibling);
                //这种情况父节点向下合并，父节点的位置也会下溢
                if(parentBlack){
                    //三黑局面没有替代节点
                    afterRemove(parent,null);
                }

            }else {//至少有一个红色子节点
                //判断是LL LR.....
                //三种情况:LL LR (LL或LR)
                //可以先统一进行左旋转然后在统一进行右旋转
                //如何区分LR左子节点是黑的
                if(isBlack(sibling.left)) {//LR情况

                    rotateLeft(sibling);
                    //左旋转后兄弟节点已经发生了变化
                    sibling = parent.left;
                }
                //LL 情况
                //现在的sibling已经更新过是图中的78
                color(sibling,iscolor(parent));
                black(parent);
                black(sibling.left);
                rotateRight(parent);
            }

        }
    }
    protected Node<k,v> predecessor(Node<k,v> node) {
        if (node == null) return null;

        // 前驱节点在左子树当中（left.right.right.right....）
        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;
    }

    protected Node<k,v> successor(Node<k,v> node) {
        if (node == null) return null;

        // 前驱节点在左子树当中（right.left.left.left....）
        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;
        }

        return node.parent;
    }

    @Override
    public boolean containsKey(k key) {
        return node(key)!=null;
    }

    private boolean Equals(v v1,v v2){

        return v1==null?v2==null:v1.equals(v2);
    }
    @Override
    public boolean containsValue(v value) {
        if(root==null)
        {
            return false;
        }
        Queue<Node<k,v>> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty())
        {
            Node<k,v> node=queue.poll();
            boolean com=Equals(value,node.value);
            if(com)
            {
                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 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 isLeftChild() {
            return parent != null && parent.left ==this;
        }

        public boolean isRightChild() {

            return parent != null && parent.right == this;
        }

        public boolean hasToChildren() {
            return left != null && right != null;
        }

        public Node<k, v> sibling() {
            if (isLeftChild()) {
                return right;
            }
            if (isRightChild()) {
                return left;
            }
            return null;
    }

    public boolean hasTwoChildren(){
            return left!=null&&right!=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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615

三.用映射实现集合（HashMap实现HashSet）

上面我们提到，映射有两个关键的存储数据key value.映射由 红黑树来实现，在红黑树中如果添加的是相同元素会实现覆盖操作，所以用红黑树实现的映射默认没有重复元素，所以我们不难看出如果我们把红黑树中的value 去掉不就符合集合的所有要求了吗,所以我们完全可以用映射来实现集合。

package bite;

import map.Map;
import map.TreeMap;

import java.util.Objects;

//用映射实现集合
//映射去掉value正好符合集合的要求
public class TreeSet<E> implements Set<E>{
    Map<E, Objects> 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, Objects>() {
            @Override
            public boolean visit(E key, Objects value) {
                visitor.visit(key);
                return false;
            }
        });

    }
}

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

详细代码请见：映射 集合