Java~数据结构（七）~Map和Set的使用（TreeMap\TreeSet的使用、Map和Set的基础知识、二叉搜索树的常见操作及实现..）

文章目录

Map和Set概念及使用场景

Map和Set是Java中的集合，是一种数据结构，本质上也是用来存放数据的容器。
Map和Set最常见的使用场景就是搜索。以前常见的搜索有直接遍历或者二分查找，但这两种都是静态的查找，即都不会涉及到对数据进行插入和删除操作，但现实中有很多使用场景是需要进行插入和删除操作的，比如通讯录里面根据名字查找联系方式啊，或者根据名字查找考试成绩啊等等，这些都是在查找时可以动态的进行操作，这就是动态查找，

Map和Set就是适合动态查找的容器。

查找时的模型

我们查找时搜索的数据就是关键字（
key
），根据关键字搜索到的内容就是值（
value
）,也被成为KV键值对。

查找时，一般有以下两种模型：

纯key模型。比如有一个英文词典，快速查找一个单词是否在词典中。
纯key-value模型。比如统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数。
Map中存储的就是key-value键值对。而Set中只存储了key.

Map的使用

Map是一个接口类，该类没有继承自Collection，该类中存储的是<K，V>结构的键值对，并且k一定是唯一的，不能重复。
Map中有一个内部类
Map.Entry<k,v>
是专门用来存放<key,value>键值对映射关系的。
Map.Entry<k,v>
有啥用？怎么用？它的作用是获取到Map集合中所有的key或value,还可以设置value。用法如下：

Map的常用方法

在这里插入图片描述

Map是一个接口，不能实例化对象

，如果

要实例化对象只能实例化其实现类TreeMap或者HashMap
2.Map中的key是

唯一

且

不能为空

且

不能修改

，value可重复并且可以是空，如果非要修改key，只能先删除然后再重新插入。
3.Map中的key可以全部分离出来，存储到Set中来进行访问。(因为key不可重复
4.

Map中的value可以全部分离出来，存储到Collection的任何一个子集合中

。
TreeMap和HashMap的区别：

TreeMap的使用举例

import org.omg.PortableInterceptor.INACTIVE;

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

public class TestMap {
    public static void main(String[] args) {
        Map<Integer,Integer> m=new TreeMap<>();

        m.put(1,1);
        m.put(2,1);
        m.put(3,1);
        m.put(4,1);
        m.put(5,1);

       
         * put方法
         * put(key,value),向Map中插入k-v键值对,
         * 如果这个key之前不存在，会将k-v键值对插入到map中，返回null
         * 如果key存在，会刷新value值，用新值替换旧值。
         */

        System.out.println(m.put(6,1)); //null
        System.out.println(m.size());  //6
        System.out.println(m);

     
         * get方法
         * get(key): 返回key对应的value值
         * 如果key存在，会返回对应的value值
         * 如果不存在，会返回null
         */
        System.out.println(m.get(1)); //1
        System.out.println(m.get(7));//null

    
         * GetOrDefault():
         * 如果key存在，返回与key所对应的value,如果key不存在，返回一个默认值
         */
        System.out.println(m.getOrDefault(1,0));//如果1存在，返回与1对应的value值，否则返回0
        System.out.println(m.getOrDefault(2,0));
        System.out.println(m.size());

      
         * containKey(key):检测key是否包含在Map中  O(logN)
         * 找到返回true,没找到返回false
         */
        System.out.println(m.containsKey(1)); //true
        System.out.println(m.containsKey(8)); //false

     
         * containValue(key):检测value是否包含在Map中 O(N)
         * 为什么是O(N)?因为TreeMap是按照key来组织的，因此查找value就需要整体遍历
         * 找到返回true,没找到返回false
         */
        System.out.println(m.containsValue(1));
        System.out.println(m.containsValue(2));//false

       
         * 输出所有的key
         * keySet是将Map中的key放在Set中返回的
         */
        for(Integer s:m.keySet()){
            System.out.println(s+" ");
        }
        System.out.println();

  
         * 打印所有的键值对
         * entrtSet():将Map中的键值对放在Set中返回
         */
        for(Map.Entry<Integer, Integer> entry:m.entrySet()){
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
        System.out.println();
    }
}

Set的说明

Set没啥好说的，已经介绍过了。
Set和Map不同的地方主要有两个：Set是继承自Collection接口的类，Set中只存储了
KEY
.

Set的常见方法

在这里插入图片描述

Set是继承自Collection的一个接口类
Set的底层是Map，所以Set中key和Map中的key要求相同
Set的底层是使用Map来实现的，其使用的key与Object的一个默认对象作为一个键值对插入到Map中。
Set最大的功能是对集合中的元素去重。
实现Set接口最常用的子类是TreeSet和HashSet、LinkedListSet。LinkedListSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
TreeSet与HashSet的区别：

TreeSet使用举例

    public static void main(String[] args) {
        Set<String> s=new TreeSet<>();

        //add(key) 如果key不存在，则添加返回true，否则不存在返回false
        boolean isIn=s.add("apple");
        s.add("orange");
        s.add("peach");
        s.add("banan");
        System.out.println(s.size());
        System.out.println(s);

        isIn=s.add("apple");
        //add过程中，如果key是空，会抛出异常。
 

        //containsKey ： 如果key存在，返回true ,否则返回false
        System.out.println(s.contains("apple"));
        System.out.println(s.contains("watermelen"));

        //remove(key): key存在，删除成功并返回true
                  //  key不存在，删除失败返回false
   
        s.remove("apple");
        System.out.println(s);
        s.remove("watermelen");
        System.out.println(s);

        // s.remove(null) ---会抛出空指针异常

        Iterator<String> it=s.iterator();
        while(it.hasNext()){
            System.out.println(it.next()+" ");
        }
        System.out.println( " ");

    }

搜索树（查找树）

二叉搜索树称为二叉排序树，它是空树或者具有以下性质的树（二叉树）：
若左子树不为空，则左子树上所有节点的值都小于根节点
若右子树不为空，则右子树上所有节点的值都小于根节点
其左右子树也分别为二叉搜索树
查找操作

：若根节点不为空，如果根节点key==查找key，返回true。如果根节点key>查找key，则在其左子树寻找，如果根节点key小于查找key，则在其右子树寻找否则返回false
插入操作

：

1）如果是空树，即根==null,直接插入

2）如果不是空树，按照查找逻辑确定插入位置，插入新节点。比如如果想插入元素为10的新节点，搜索书序如下：
删除操作

：假设待删除节点为cur,其双亲节点为parent.

  1) 情况1：cur.left == null
           1.cur是root,则root = cur.right
           2.cur不是root,cur是parent.left,则 parent.left =cur.right;
           3.cur不是root,cur是parent.right,则parent.right =  cur.right
  2)情况2：cur.right == null
         1.cur是root,则 root = cur.left;
         2.cur不是root, cur是parent.left,则parent.left = cur.left
         3.cur不是root,cur是parent.right,则parent.right = cur.left
  3) 情况3：cur.left != null && cur.right !=null
         1.需要使用替换法进行删除，即在右子树中寻找中序遍历下的第一个节点，将这个值填补到被删除的节点中。

所有操作代码实现如下：

public class BinarySearchTree {
  package binarysearchtree;

class BinarySearchTree {

    public static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node (int val) {
            this.val = val;
        }
    }


    public Node root;
    //查找操作
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if(cur.val == key) {
                return cur;
            }else if(cur.val < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return null;
    }

    //插入操作
    public boolean insert(int key) {
        Node node = new Node(key);
        if(root == null) {
            root = node;
            return true;
        }

        Node cur = root;
        Node parent = null;

        while(cur != null) {
            if(cur.val == key) {
                return false;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //parent
        if(parent.val > key) {
            parent.left = node;
        }else {
            parent.right = node;
        }

        return true;
    }
 
      //删除操作
    public void remove(Node parent,Node cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            Node targetParent =  cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }
    //删除
    public void removeKey(int key) {
        if(root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                remove(parent,cur);
                return;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }




}
public class TestDemo {


    public static void inorder(BinarySearchTree.Node root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    public static void preorder(BinarySearchTree.Node root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preorder(root.left);
        preorder(root.right);
    }
   
    ///进行使用  写的那些二叉树方法是否有用
    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(13);
        binarySearchTree.insert(1);
        binarySearchTree.insert(21);
        binarySearchTree.insert(14);
        binarySearchTree.insert(5);
        binarySearchTree.insert(6);

        inorder(binarySearchTree.root);
        System.out.println();

        preorder(binarySearchTree.root);
        System.out.println();

        System.out.println(binarySearchTree.search(1).val);

        binarySearchTree.removeKey(13);

        inorder(binarySearchTree.root);
        System.out.println();
        preorder(binarySearchTree.root);
        System.out.println();
    }
}

原文链接：https://blog.csdn.net/Merciful_Lion/article/details/127197844

文章目录

Map和Set概念及使用场景

查找时的模型

Map的使用

Map的常用方法

TreeMap的使用举例

Set的说明

Set的常见方法

TreeSet使用举例

搜索树（查找树）

你可能也喜欢