devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构八：二叉搜索树，Map，Set，哈希_map是不是二叉树

作者：weixin_40725706 | 2024-06-11 01:07:51

赞

踩

map是不是二叉树

前言：

 

目录

1.二叉搜索树

1.1：概念

 1.2：模拟实现二叉树的操作

 1.2.1:插入

1.2.2：查找 

 1.2.3：删除

2.概念和模型

2.1：概念

2.2：模型

3.Map

3.1：Map.Entry的说明,v>

3.2：Map的常用方法说明

4.Set的说明书

5.oj题练习

5.1.复制待随机指针的链表

5.2:前K个高频单词

6.哈希表

6.1：冲突

6.1.1：概念

6..2：冲突-避免-负载因子调节

6.2.3：冲突解决--闭散列

6.3.3：冲突解决-开散列/哈希桶

7.HashCode()和equals()的区别 

7.1：面试题：

这是数据结构的最后一篇，这篇会讲到Map和set还有哈希。学了这些，遇到莫些题，你会觉得很简单。

1.二叉搜索树

1.1：概念

二叉搜索树又称二叉排序树---二叉树节点的值都是唯一的，不重复的

1.若它的左子树不为空。则左子树的所有节点的值都小于根节点的值

2，若他的右子树不为空，则右子树的所有节点的值都大于根节点的值。

94604c7ea6f0466a991b885f5bf893b8.png

 1.2：模拟实现二叉树的操作

 1.2.1:插入

插入是在二叉树的叶子节点进行插入的

  1. public boolean insert(int key) {
  2.         TreeNode ret=new TreeNode(key);
  3.         //判断此树是不是空树
  4.         if(root==null){
  5.             root=ret;
  6.             return true;
  7.         }
  8.         TreeNode parent=null;
  9.         TreeNode cur=root;
  10.         while(cur!=null){
  11.             //判断它是不是大于此节点的值
  12.             if(cur.key<key) {//大于根节点，往右边插
  13.                 parent=cur;//记录父亲节点
  14.                 cur=cur.right;
  15.             }else if(cur.key>key) {//小于根节点的，往左边插
  16.                 parent =cur;
  17.                 cur=cur.left;
  18.             }
  19.         }//此时到了叶子节点
  20.         if(ret.key< parent.key){
  21.             parent.left=ret;
  22.         }else {
  23.             parent.right=ret;
  24.         }
  25.         return  true;
  26.     }

30301d4dfaf348dba69dc7f338d3a341.png     

1.2.2：查找 

若根节点不为空

如果根节点key==查找的key返回true

如果根节点key>查找的key，在左子树查找。

如果根节点key<查找的key，在右子树查找。

  1.   public TreeNode search(int key) {
  2.       //查找根节点是否为null
  3.         if(root==null){
  4.             return null;
  5.         }
  6.         TreeNode cur=root;
  7.         while(cur!=null){
  8.             if(cur.key>key){//比根节点小
  9.                 cur=cur.left;
  10.             }else if(cur.key<key){//比根节点大
  11.                 cur=cur.right;
  12.             }else{
  13.                 return cur;//找到
  14.             }
  15.         }
  16.         return null;
  17.     }

 1.2.3：删除

删除比较麻烦，要分为三大类。设待删除节点为cur .待删除的父亲节点为parent.

  1.   //删除节点
  2.     public  void removeChild(TreeNode cur,TreeNode parent){
  3.         //分三种情况
  4.         //1 cur.left==null
  5.         if(cur.left==null){
  6.             //判断是不是根节点
  7.             if(cur.equals(root)){
  8.                 root=root.right;
  9.             }
  10.             if(cur.equals(parent.left)){
  11.                 parent.left=cur.left;
  12.             }
  13.             if(cur.equals(parent.right)){
  14.                 parent.left=cur.right;
  15.             }
  16.         }else if(cur.right==null){ //2.cur.right==null
  17.            if(cur.equals(root)){
  18.                root=root.left;
  19.            }
  20.            if(cur.equals(parent.right)){
  21.                parent.right=cur.left;
  22.            }
  23.            if(cur.equals(parent.left)){
  24.                parent.left=cur.left;
  25.            }
  26.         }else{//3.cur.left!=null&&cur.right!=null
  27.             //用一个叫做替罪羊
  28.             //可以找左树的最右边，就是左边最大的，也小于根节点
  29.             //可以找右边的最左边，就是右边最小的，也大于根节点
  30.             TreeNode target=cur.left;//左树
  31.             TreeNode targetParent=cur;
  32.             while(target.right!=null){//左树的最右边
  33.                 targetParent=target;
  34.                 target=target.right;
  35.             }
  36.             cur.key=target.key;//将替罪羊的值赋值给cur
  37.             //将替罪羊删除
  38.             if(target.equals(targetParent.left)){
  39.                 targetParent.left=target.left;
  40.             }else{
  41.                 targetParent.right=target.right;
  42.             }
  43.         }
  44.     }
  45. }

2.概念和模型

2.1：概念

Map和Set是一种专门用来进行搜索的容器或者数据结构，其底层是一棵二叉搜索树。其搜索的效率与其具体的实际化子类有关。可能在查找时进行一些插入和删除的操作，即动态查找。

本节介绍的Map和Set是一种适合动态查找的集合容器。
 

2.2：模型

把搜索的数据称为关键字（Key)和关键字对应的称为值(Value),将其称为Key-Value的键值对

1.纯Key模型----快速查找莫个数据是否存在

2.Key-Value模型---统计文件中每个单词出现的次数。<单词，单词出现的次数>

3.Map

Map是一个接口类，没有继承Collection(Set和List都继承了），该类存储的是<K,V>结构的键值对，并且K一定是唯一的。

3.1：Map.Entry<K,V>的说明

Map.Entry<K, V>是Map内部实现的用来存放<Key,Value>键值对映射关系的内部类

方法解释
K getKey()返回entry中的Key
V getValue()

返回Key中的Value

 

 

 

 

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         TreeMap<String,Integer>map=new TreeMap<>();
  4.         map.put("hello",4);//h-104
  5.         map.put("world",1);//w-119
  6.         map.put("abc",7);//a-97
  7.         //返回所以的Key-Value的映射关系
  8.         Set< Map.Entry<String,Integer>>entrySet=map.entrySet();
  9.         for (Map.Entry<String,Integer>entry:entrySet) {
  10.             System.out.println("Key:"+entry.getKey()+" "+
  11.                              "Value"+entry.getValue());
  12.         }
  13.     }
  14. }

74ff0e42c2214654b460977901bab1ba.png

 从中，看出了什么吗？

Key的是安找升序排序的，故：Key一定要比较，不然会报错。

3.2：Map的常用方法说明

方法解释
V get(Object Key)返回Key对应的Value
V getOrDefault(Object key ,v defaultValue)返回key对应的Value,key不存在，返回默认值
V put(K key V value)设置key对应的Value//Key一定可以比较
V remove(Object key)删除Key对应的映射关系
Set<K> keySet()返回所有Key的不重复集合
Collection<V>values()返回所有Value的可重复集合
boolean containsKey(Object key)判断是否包含Key
boolean containsKey(Object value)判断是否包含value

 

 

 

 

 

 

 

 

 

 

注意：

1.Map是一个接口，不能直接实例化对象。

2.Map中存放键值对的Key是唯一的，Value是可以重复的。

3.Key不能为空，否则就会包空指针异常。

4.Map中键值对的Key不能直接修改（如果要修改，只能先删除，再进行重新插入！）

4.Set的说明书

Set继承Collection的接口类，Set中存储Key

方法解释
boolean add(E e)添加元素 重复元素不会添加
void clear ()清空集合
boolean contains(Object 0)判断o是否存在集合中
lterator<E> iterator()返回迭代器
boolean remove(Object o)删除集合中的o
int size()返回set中元素的个数
boolean isEmpty()检测set是否为空，空返回true 不空返回false
object [] toArray

将set中的元素转换为数组返

 

 

 

 

 

 

 

 

 

 

注意：

1.set中只存储了key，并且要求key一定要唯一。

2.Set的底层是使用map来实现的。

3.set最大的功能就是对集合中的元素去重

4.set中不能插入null的key。

5.oj题练习

5.1.复制待随机指针的链表

在笔试中出现过。可以注意下哟

138. 复制带随机指针的链表 - 力扣（LeetCode）

7ee7b138f2104331942682b363e65366.png

bf2c2eebf8ff48ba9b35f0c677bb5abb.png

6452c56968d44024a1d2bf19f639d8bf.png

  1. class Solution {
  2.     public Node copyRandomList(Node head) {
  3.         HashMap<Node,Node> map=new HashMap<>();
  4.         Node cur=head;//将链表都存到map中
  5.         while(cur!=null){
  6.             Node node=new Node(cur.val);//创建一个节点
  7.              map.put(cur,node);
  8.             cur=cur.next;
  9.         }
  10.         //第二次遍历链表
  11.         cur=head;
  12.         while(cur!=null){
  13.             map.get(cur).next=map.get(cur.next);
  14.             map.get(cur).random=map.get(cur.random);
  15.             cur=cur.next;
  16.         }
  17.     return map.get(head);
  18. }
  19. }

5.2:前K个高频单词

 692. 前K个高频单词 - 力扣（LeetCode）

 这道题我就说说思路就不画图了。

1.我们用HashMap 来存放单词。key是单词。value 是单词出现的次数

2.Top-k问题。将前K个单词按照频率来建立小堆。

3.K后面的单词，依次和堆顶元素相比较，单词出现频率大于堆顶的。该单词入堆。堆顶元素出堆。如果频率出现相同。比堆顶单词首字母大。该单词入堆，堆顶元素出堆。按照单词大小建立大堆。

4.用列表保存堆中元素,之后逆转。

  1. class Solution {
  2.     public List<String> topKFrequent(String[] words, int k) {
  3.             HashMap<String, Integer> map = new HashMap<>();
  4.         //保存字符串数组到map
  5.         for (String x : words) {
  6.             if (map.containsKey(x)) {
  7.                 int val = map.get(x);
  8.                 map.put(x, val + 1);
  9.             } else {
  10.                 map.put(x, 1);
  11.             }
  12.         }
  13.         //Top-K问题
  14.         PriorityQueue<Map.Entry<String, Integer>> q1 =
  15.                 new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
  16.                     @Override
  17.                     public int compare(Map.Entry<String, Integer> o1,
  18.                                        Map.Entry<String, Integer> o2) {
  19.                         if (o1.getValue().compareTo(o2.getValue()) == 0) {
  20.                             //频率相同,按照单词首字母大小建立大堆
  21.                             return o2.getKey().compareTo(o1.getKey());
  22.                         }//频率不同，按照频率大小建立小堆
  23.                         return o1.getValue().compareTo(o2.getValue());
  24.                     }
  25.                 });
  26.         //遍历map当中的entry
  27.         for (Map.Entry<String, Integer> entry : map.entrySet()) {
  28.             //把前k个元素建成小堆
  29.             if (q1.size() < k) {
  30.                 q1.offer(entry);
  31.             } else {//后k个元素，逐渐和堆顶元素进行比较
  32.                 Map.Entry<String, Integer> s1 = q1.peek();
  33.                 //频率大
  34.                 if (entry.getValue().compareTo(s1.getValue()) > 0) {
  35.                     //比堆顶元素大
  36.                     //将堆顶元素出堆
  37.                     q1.poll();
  38.                     //再将这个元素入堆
  39.                     q1.offer(entry);
  40.                 }//和堆顶元素频率相等
  41.                 else {
  42.                     if (entry.getValue().compareTo(s1.getValue()) == 0) {
  43.                         //比较单词首字母的大小
  44.                         if (s1.getKey().compareTo(entry.getKey()) > 0) {
  45.                             //比堆顶元素的首字母大，堆顶元素出堆，
  46.                             q1.poll();
  47.                             q1.offer(entry);
  48.                         }
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.         //将堆的元素赋值给List
  54.         List<String> list = new ArrayList<>();
  55.         for (int i = 0; i < k; i++) {
  56.             Map.Entry<String, Integer> m1 = q1.poll();
  57.             list.add(m1.getKey());
  58.         }
  59.         Collections.reverse(list);
  60.         return list;
  61.     }
  62. }

6.哈希表

使元素存储位置与它的关键码之间能够建立一一映射的关系。

6.1：冲突

6.1.1：概念

不同关键字通过相同哈希计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞。

冲突的发生使必然的，我们只能尽量降低冲突。

6..2：冲突-避免-负载因子调节

载荷因子：填入表中的元素个数/散列表的长度（严格限制在0.7-0.8）之间

6.2.3：冲突解决--闭散列

闭散列：也叫开放定址法。可以将key存放到冲突位置中的‘下一个'空位置中。

1.线性探测：

从发送冲突的位置开始，依次向后探测，直至找到下一个空位置。---冲突数据堆积在一起

2.二次探测：

找下一个空位置的方法：Hi=(Ho+i^2)%m

Hi:要插入的位置

Ho:hash(key)=key%capacity--长度。计算出来的位置

i:第几次冲突。m:长度。

6.3.3：冲突解决-开散列/哈希桶

b3985830d70643e986b1000be07e1d86.png

7.HashCode()和equals()的区别 

hashCode（） 方法的作用是获取哈希码。返回的是一个整数，作用是：确定对象在哈希表的索引下标。

equals()判断两个对象是否相等。

1.两个对象的hashcode一样，equals一定一样？

不一定

2.两个对象的equals一样，hashcode一定一样？

一定

7.1：面试题：

重写equals()方法就可以比较两个对象是否相等，为什么还要重写hashcode()方法？

HashSet和HashMap在判断两个元素是否相等时，会先判断hashCode是否相等，如果

hashCode相等，才会用equals()方法比较是否相等。

总结：以上就是我总结的Map和Set，如果有错，请各位铁子留言改正，若感觉不错，一键三连。

 

 

 

 

 

 

 

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/701092
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号