数据结构之Map/Set讲解+硬核源码剖析(一)

简介: 数据结构之Map/Set讲解+硬核源码剖析(一)

💕"活着是为了活着本身而活着"💕

作者:Mylvzi

文章主要内容:数据结构之Map/Set讲解+硬核源码剖析

一.搜索树

1.概念

 二叉搜索树又叫二叉排序树,他或者是一颗空树,或者是具有以下性质的树

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

简单来说,二叉搜索树上存储结点的值满足以下条件:

                                      left < root < right

 注意:二叉搜索树中不能存在两个相同的值

2.二叉搜索树的操作及其实现

前提准备

static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    private TreeNode root = null;

1.查询操作(search)

 根据二叉搜索树的性质很容易实现查询的操作

代码实现:

// search
    public boolean search(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            }else {
                return true;
            }
        }
        return false;
    }

2.插入操作(insert)

 让cur走到合适的位置,再去判断parent.val 与 val的关系,进行插入

画图分析:

代码实现:

// insert
    public boolean insert(int val) {
        TreeNode newNode = new TreeNode(val);
        // 空树直接插入
        if (root == null) {
            root = newNode;
            return true;
        }
        // 保留cur的根节点
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            parent = cur;
            if(cur.val < val) {
                cur = cur.right;
            } else if(cur.val > val){
                cur = cur.left;
            }else {
                // 二叉搜索树中不能存在两个相同的数字
                return false;
            }
        }
        // 此时cur就是要插入的位置
        if(parent.val < val) {
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        return true;
    }

3.删除操作(remove)

 如果你要删除的cur的结点只有一个子节点,此时删除十分容易

但是如果你想要删除的结点有两个子节点,处理稍微麻烦,因为在你删除cur结点之后,还要保证剩下的结点也满足二叉搜索树的性质,这里采用“替罪羊”法解决删除拥有两个子节点的结点

思路分析:

我现在想要删除90这个结点,但是删除之后谁来替代这个结点呢?

根据二叉搜索树的性质,90看作根节点,则他一定比左树的所有结点的值大,比右树所有结点的值小

我们需要找一个合理的结点去替换90,替换之后仍要满足二叉搜索树的性质,这个合理的结点可以通过两个方法实现

  1. 找左树的最大值
  2. 找右树的最小值

现在以找右树的最小值为例演示

代码实现

public void remove(int val) {
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            parent = cur;
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            }else {
                removeNode(parent,cur);
                return;
            }
        }
    }
    private void removeNode(TreeNode parent, TreeNode cur) {
        // 注意此时cur就是我要删除的数据
        // 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) {
         // cur的右树为空
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {// 都不等于Null
            // 找右树的最小值
            // 使用替罪羊法
/*            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            // 找右树的最小值  直到某个结点的left为null  则此节点就是右树最左边的结点  也就是右树的最小值
            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;
            }*/
            // 求左树的最大值
            TreeNode tp = cur;
            TreeNode t = cur.left;
            while (t.right != null) {
                tp = t;
                t = t.right;
            }
            // 此时t就是左树的最大值
            cur.val = t.val;
            // 重写链接
            if (t == tp.left) {
                tp.left = t.left;
            }else {
                tp.right = t.left;
            }
        }
    }

3.性能分析

 对于二叉搜索树来说,进行插入/删除操作都要先进行查询,所以二叉搜索树的性能取决于查询的效率  最好情况是二叉树是一颗完全二叉树  最坏情况则是二叉树是一颗单分支的二叉树

 问题:如果是单分支的情况,二叉搜索树的效率会变得很低,如何解决这种问题呢?

4.和 java 类集的关系

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

二.搜索

1.概念和场景

 Map和Set是一种专门用来进行“搜索”的数据结构/容器,其搜索效率取决于其具体实现的子类

我们之前其实也学过搜索

1.直接遍历  最粗暴的搜索方法  时间复杂度0(N)

2.二分查找  需要序列是有序的  时间复杂度O(logN)

上述查找适合静态的查找,即在查找的过程中不会进行插入和删除的操作,但是现实中的很多查找都需要动态的进行插入和删除,比如:

1.根据学号查成绩

2.根据通讯录名字查找电话号

3.根据身高找女朋友(bushi)

......

在查找的过程中可能会出现插入和删除的操作,Map和Set就是用于动态的插入和删除的搜索容器

2.搜索的模型

 搜索的方式其实有两种,一种是直接在一大堆数据中寻找,另一种是根据对应关系进行查找(比如你需要先找到通讯录的名字,才能根据通讯录的名字找到你要寻找的手机号),我们一般把搜索的数据称为关键字Key,key对应的称为值Value,将其称之为Key-value的键值对

1. 纯 key 模型(找有没有)

  • 在词典中找单词

2. Key-Value 模型(找对应关系)

  • 梁山好汉的江湖绰号:每个好汉都有自己的江湖绰号
  • 学号对应着你的名字

而Map中存储的是Key-Value 模型,Set中存储的是纯 key 模型

三.Map的使用

先放一张Java中和数据结构有关的类的图

1.概念

 Map是一个接口类,不能直接实例化对象,如果要使用,需要根据实现他的类来实例化具体的对象,比如TreeMap(底层是红黑树)和HashMap(底层是哈希表)

2.常用方法

1.put

在Map中添加key与value的映射关系

// 根据实现Map的类TreeMap来实例化一个对象
        Map<String,Integer> map = new TreeMap<>();
        // Put方法
        // 设置  单词--出现的次数  这样的一个key与value的映射
        map.put("apple",14);
        map.put("bank",15);
        map.put("cat",17);
 注意:

1.我们知道,TreeMap的底层是一颗红黑树,存储的时候是使用结点来存储元素的,它实际上存储的是Key-Value的映射关系,实际上Map中存在一个内部类Map.Entry,用于表示映射关系

2.既然TreeMap是一种红黑树,那他在存入数据的时候必然要排序,排序的根据是Key

2.get方法

 存在两个get方法  但都是为了返回key对应的value值

System.out.println(map.get("apple"));// 输出14
        System.out.println(map.get("bank"));// 输出15
        System.out.println(map.get("cat"));// 输出17
        // get时进行判断 如果Map中含有传入的key就返回其value  没有则返回其默认值(解某些题很有用)
        System.out.println(map.getOrDefault("apple", 100));// 输出14  因为Map中含有apple
        System.out.println(map.getOrDefault("Dog", 100));// 输出100  因为Map中不含有Dog

数据结构之Map/Set讲解+硬核源码剖析(二)+https://developer.aliyun.com/article/1413571

目录
相关文章
|
7天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
68 9
|
18天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
62 2
|
18天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
49 2
|
28天前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
63 0
|
28天前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
49 0
|
6天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
45 16
|
6天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
34 8
|
8天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
35 4
|
10天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
33 3
|
16天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
24 1

热门文章

最新文章