[Collection与数据结构] Map与Set(一):二叉搜索树与Map,Set的使用

🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:🍕 Collection与数据结构 (91平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(94平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~

1. 搜索树

1.1 概念

二叉搜索树又称为二叉排序树,它可以是一颗空树,或者是具有以下性质的二叉树.

若他的右树不为空,则它的右子树上的所有结点都大于根结点.
若它的左树不为空,则它的左子树上的所有结点都小于根结点.
它的左子树和右子树也分别为二叉搜索树.

1.2 查找结点

如果根节点为空,返回false.如果根结点不为空:

如果根结点key == 查找key,返回true.
如果根结点key < 查找key,到其右子树中查找.
如果根结点key > 查找key,到其左子树中查找.

1.3 插入结点

如果为空树,直接令root = 所要插入的结点.之后返回true.
如果该树不是空树,按照搜索二叉树的性质确定查找逻辑.插入新结点.注意记录cur的父节点,否则无法插入.

1.4 删除结点(难点)

设待删除的结点是cur,带删除的结点的父节点是parent.

cur的左子树为空
- 要删除的节点是根结点,直接令root = root.right
- 要删除的结点是中间的结点, 单分支,parent.right = cur.right
- 要删除的结点是中间结点,<字型,parent.left = cur.right
cur的右子树为空
- 要删除的结点是根结点,直接令root = root.left
- 要删除的结点是中间结点,单分支,parent.left = cur.left
- 要删除的结点是中间结点,>字型,parent.right = cur.left
cur的左右子树都不为空
可以使用替换法进行删除,即它在右子树中寻找最小的结点,或者在左子树中寻找最大的结点,使用找到的结点替换要删除的结点,然后删除找到的最小(大)的结点,之后又分为两种情况(以右子树为例):
- 最小的结点与上下的结点组成<型.
- 最小的结点与上下结点形成单分支.
  [图解]

1.5 实现二叉搜索树

public class SearchBinaryTree {
    //搜索树的结点
    public static class Node{
       public int key;
       public Node left;
       public Node right;

        public Node(int key) {
            this.key = key;
        }
    }
    private Node root = null;

    /**
     * 查找元素
     * @param key 索要查找的元素
     * @return 返回Node的哈希值
     */
    public Node search(int key){
        Node cur = root;
        while (cur != null){
            if (cur.key == key){
                return cur;
            } else if (cur.key < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return null;//没找到,返回null
    }

    /**
     * 在二叉搜索树中插入指定的值
     * @param key 所要插入的值
     * @return 返回是否插入成功
     */
    public boolean insert(int key){
        Node node = new Node(key);
        Node cur = root;
        Node parent = null;
        if (root == null){
            root = node;
            return true;
        }
        while (cur != null){
            if (cur.key == key){
                return false;//二叉搜索树中不允许有两个相同的值,遇到相等返回false
            } else if (cur.key < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //退出循环后,判断结点应该插入在左侧还是右侧
        if (parent.key < key){
            parent.right = node;
        }else {
            parent.left = node;
        }
        return true;
    }

    /**
     * 删除指定值的结点
     * @param key 所要删除的值
     * @return 返回是否删除成功
     */
    public boolean remove(int key){
        Node cur = root;
        Node parent = null;
        if (root == null){
            return false;
        }
        while (cur != null){
            if (cur.key == key){
                removeNode(parent,cur);
                return true;
            } else if (cur.key < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        return false;//没找到,返回false
    }

    /**
     * 找到结点之后删除
     * @param parent 父结点
     * @param cur 当前要删除的结点
     */
    private void removeNode(Node parent,Node cur){
        if (cur.left == null){//cur的左结点为空
            if (cur == root){//当前要删除的结点是根结点
                root = root.right;
            } else if (parent.right == cur) {//删除的是单分支的中间节点
                parent.right = cur.right;
            }else {//删除的是<字型的中间结点
                parent.left = cur.right;
            }
        } else if (cur.right == null) {//cur的右结点为空
            if (cur == root){//当前要删除的结点是根结点
                root = root.left;
            } else if (parent.left == cur) {//删除的是单分支的中间节点
                parent.left = cur.left;
            }else {//删除的是>字型的中间结点
                parent.right = cur.left;
            }
        }else {//左右结点都不为空,使用替换删除法
            //在这个结点的右子树中寻找最小的值,用它进行替换,原因:这样右结点的值一定比替换之后的值大
            Node t = cur.right;
            Node tparent = cur;
            //寻找右子树的最小结点,一直向左子树遍历,因为只有左结点的值才比根结点小,
            while (t.left != null){//当没有左结点的时候停止遍历
                tparent = t;
                t = t.left;
            }
            cur.key = t.key;
            //删除替换掉的结点
            if (tparent.left == t){//<字型
                tparent.left = t.right;
            }else {//单分支型
                tparent.right = t.right;
            }
        }
    }
}

1.6 性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
在这里插入图片描述
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log₂N
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

1.7 和Java中Collection的关系

TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行讲解。

2. Map和Set

2.1 概念与场景

Map和Set是一种专门用来就那些搜索的容器或者数据结构,其搜索的效率与它们具体的例子有关.
以前常见的搜索方式有：
1. 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
2. 二分查找，时间复杂度为 ,但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：
1. 根据姓名查询考试成绩
2. 通讯录，即根据姓名查询联系方式
3. 不重复集合，即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是一种适合动态查找的集合容器。

2.2 两种模型

一般把搜索的数据称为关键字(key),和关键字对应的值称为值(value),将其称为key-value键值对,所以会有两种模型.

纯key模型,容器中只存了key一个值.
key-value模型,容器中存的是key-value的键值对.
Map中存储的是key-value键值对(有点类似于python中的字典),Set中只存储了key(有点类似于python中的集合).

2.3 Map的使用

2.3.1 关于Map的说明

Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复.

2.3.2 关于Map.Entry<K,V>的说明

Map.Entry<K,V>是Map内部实现的内部类,用来表示Map中Key于Value的映射关系(类似于python字典中的items),该内部类中主要提供了key和value的获取方式,以及value的设置.

方法	解释
K getKey()	返回 entry 中的 key
V getValue()	返回 entry 中的 value
V setValue(V value)	将键值对中的value替换为指定value

[注意]
在Map.Entry<K,V>类中没有提供key的设置方法,即该类中的key一旦确定就不可更改.

2.3.3 常用方法

方法	解释
V get(Object key)	返回 key 对应的 value，如果key不存在，返回null
V getOrDefault(Object key, V defaultValue)	返回 key 对应的 value，key 不存在，返回默认值
V put(K key, V value)	设置 key 对应的 value
V remove(Object key)	删除 key 对应的映射关系
Set`<K>` keySet()	返回所有 key 的不重复集合(Map中的key不可重复)
Collection`<V>` values()	返回所有 value 的可重复集合(Map中的value可重复)
Set<Map.Entry<K, V>> entrySet()	返回所有的 key-value 映射关系
boolean containsKey(Object key)	判断是否包含 key
boolean containsValue(Object value)	判断是否包含 value

[注意事项]

Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
Map中存放键值对的Key是唯一的，value是可以重复的
在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但是HashMap的key和value都可以为空。
Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
TreeMap的底层结构是红黑树,增删查改的时间复杂度是log₂N,HashMap的底层结构是哈希桶.时间复杂度是1,哈希桶直接可以根据索引找到位置,不需要遍历.
TreeMap和HashMap的线程都不安全.

使用实例:

import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Map<Integer,String> map = new TreeMap<>();
        map.put(1,"一");//添加元素
        map.put(2,"二");
        map.put(3,"三");
        map.put(4,"四");
        map.put(5,"五");
        System.out.println(map.size());//打印map大小
        System.out.println(map.get(5));//获取5对应的value
        System.out.println(map.getOrDefault(6,"不存在"));//6不存在,返回默认值
        map.remove(5);//删除5对应的键值对
        Set<Integer>set = map.keySet();//拿到map的key集合
        for(int x:set){
            System.out.print(x+" ");
        }
        for (String x:map.values()){
            System.out.println(x+" ");
        }
        Set<Map.Entry<Integer,String>> set1 = map.entrySet();
        for (Map.Entry<Integer,String> x:set1){//把一个不可迭代的对象转换为可迭代对象,经常用
            System.out.println("key:"+x.getKey()+" "+"value:"+x.getValue());
        }
        System.out.println(map.containsKey(1));
        System.out.println(map.containsKey(6));
        System.out.println(map.containsValue("一"));
        System.out.println(map.containsValue("六"));
    }
}

运行结果:
在这里插入图片描述

2.4 Set的使用

Set和Map最主要的区别有两点:

Set继承于Collection接口,而Map没有,所以Set可以遍历,Map不可以遍历.
Set中只存储key,而Map中存的是key-value的键值对.

2.4.1 常用方法

方法	解释
boolean add(E e)	添加元素，但重复元素不会被添加成功
void clear()	清空集合
boolean contains(Object o)	判断 o 是否在集合中
Iterator`<E>` iterator()	返回迭代器
boolean remove(Object o)	删除集合中的 o
int size()	返回set中元素的个数
boolean isEmpty()	检测set是否为空，空返回true，否则返回false
Object[] toArray()	将set中的元素转换为数组返回
boolean containsAll(Collection<?> c)	集合c中的元素是否在set中全部存在，是返回true，否则返回false
boolean addAll(Collection<? extends E> c)	将集合c中的元素添加到set中，可以达到去重的效果