【数据结构】Map和Set(1)

在这里插入图片描述
🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧【数据结构】常见的排序算法🎈🎈🎈🎈🎈

文章目录

  • 1.前言
    • 2.搜索树
    • 2.1概念
    • 2.2查询操作
    • 2.3插入操作
    • 2.4删除操作
    • 2.5性能分析

1.前言

Map与Set的底层有两种结构实现,一种是搜索树(TreeMap与TreeSet),还有一个就是哈希表(HashMaP与HashSet),接下来我们先了解搜索树这个底层结构。
在这里插入图片描述

2.搜索树

2.1概念

二叉搜索树又称二叉排序树,它或者是一棵空树,搜索二叉树具备这样性质:
1)根结点的左边的结点都比根结点小
2)根结点的右边的结点都比根结点大
3)通过中序遍历来遍历这个二叉搜索树是一个升序的数据集合
搜索二叉树:
在这里插入图片描述

2.2查询操作

2.2.1 基本思路:
1.将要查询的值先于根结点比较,与根结点不相等,则判断该元素与根结点的大小。
2.根结点 > 该元素 则该元素在根结点的左边
3.根结点 < 该元素 则该元素在根结点的右边
4.遇到null则遍历结束

2.2.2绘图分析
在这里插入图片描述
2.2.3代码实现

/**
     *寻找key元素
     * @param key
     * @return
     */
    public boolean search(int key) {
        TreeNode cur = root;
        while(cur != null) {
            //1.判断根结点
            if(cur.val == key) {
                return true;
            } else if(cur.val > key) {
                //2.根结点大于key
                cur = cur.left;
            } else {
                //3.根结点小于key
                    cur = cur.right;
                }
            }
        return false;
        }

2.3插入操作

2.3.1基本思路:
1)插入的元素要满足中序遍历之后是一个升序的集合
2)插入的元素只能在搜索二叉树的叶子结点 进行插入
3) 通过一个指针来遍历要插入的位置的同时再让一个指针标记插入位置的父节点

遍历的过程:
1)root == null 直接插入
2)root != null 判断与根结点的大小关系
root.val > val 插入root左边
root.val < val 插入root右边
2.2.2绘图分析
在这里插入图片描述
2.2.3代码实现

/**
     * 插入元素
      */
    public void insert(int val) {
        //1.root == null
        if(root == null) {
          root = new TreeNode(val);
            return;
        }
            //2.root != null
            TreeNode cur = root;
            TreeNode parent = null;
            while(cur != null) {
                if(cur.val < val) {
                    //1.根结点小于key
                    parent = cur;
                    cur = cur.right;
                } else {
                    //2.根结点大于key
                    parent = cur;
                    cur = cur.left;
                }
            }
            //说明cur为空,元素插入parent结点的其中两侧
            TreeNode node =  new TreeNode(val);
            if(parent.val < val) {
                parent.right = node;
            } else {
                parent.left = node;
            }
        }

2.4删除操作

删除操作是最复杂也是最难的一个操作,我们以cur指针来标记删除结点,parent指针标记删除结点的父结点,我们对删除操作分为三种情况:
1.cur.left == null
2.cur.right == null
3.cur.left != null && cur.right != null
我们先画一棵搜索二叉树,这里我们删20这个结点为例子:
在这里插入图片描述
1.cur.left == null
在这里插入图片描述
2.cur.right == null
在这里插入图片描述
3.cur.left != null && cur.right != null
在这里插入图片描述
代码实现:

 public boolean remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if(cur.val >val){
                parent = cur;
                cur = cur.left;
            } else {
                return removeNode(parent,cur);
            }
        }
        return false;
    }
    private boolean removeNode(TreeNode parent,TreeNode cur) {
        //1.cur.left == null
        if(cur.left == null) {
            if(cur == root) {
               cur.right = root;
            } else {
                if(cur == parent.right) {
                    parent.right = cur.right;
                }
                if(cur == parent.left) {
                    parent.left = cur.right;
                }
            }
        }
        //2.cur.right == null
        if(cur.right == null) {
            if(cur == root) {
                cur.left = root;
            } else {
                if(cur == parent.left) {
                    parent.left = cur.left;
                }
                if(cur == parent.right) {
                    parent.right = cur.left;
                }
            }
        }
        //3.cur.left !=null && cur.right != null
        TreeNode child = cur.right;
        TreeNode p = null;//p为child的父亲结点
        while(child.left != null) {
            p = child;
            child = child.left;
        }
        //找到最小值,将最小值赋值给cur
        cur.val = child.val;

        //最小值的父亲结点的左节点是否等于最小值结点
        if(p.left == child) {
            p.left = child.right;
        } else {
            p.right = child.right;
        }

        return true;
    }

2.5性能分析

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

关于Map与Set先分享到这,后面的内容更加精彩,请各位看官慢慢期待。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/578483.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【c++】探究C++中的list:精彩的接口与仿真实现解密

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;c笔记仓 朋友们大家好&#xff0c;本篇文章来到list有关部分&#xff0c;这一部分函数与前面的类似&#xff0c;我们简单讲解&#xff0c;重难点在模拟实现时的迭代器有关实现 目录 1.List介绍2.接…

【博特激光】激光焊接机在塑料领域的应用

激光焊接机在塑料领域的应用已经越来越广泛&#xff0c;这主要得益于其独特的优势和特性。激光焊接机利用激光束产生高能量、高温的条件&#xff0c;将塑料材料熔化并融合在一起&#xff0c;实现焊接的目的。 在塑料领域&#xff0c;激光焊接机主要用于各种塑料制品的焊接&…

【项目分享】用 Python 写一个桌面倒计日程序!

事情是这样的&#xff0c;我们班主任想委托我做一个程序&#xff0c;能显示还有几天考试。我立即理解了这个意思&#xff0c;接下了这个项目。 话不多说&#xff0c;来看看这个项目吧—— 项目简介 仓库地址&#xff1a;https://gitee.com/yaoqx/desktop-countdown-day 这是 …

C语言入门课程学习笔记-6

C语言入门课程学习笔记-6 第27课 - 字符数组与字符串&#xff08;上&#xff09;第28课 - 字符数组与字符串&#xff08;下&#xff09;第29课 - 数组专题练习&#xff08;上&#xff09;第30课 - 数组专题练习&#xff08;下&#xff09; 本文学习自狄泰软件学院 唐佐林老师的…

matplotlib 安装失败:Failed building wheel for matplotlib 解决方案

Python | Failed building wheel for matplotlib 朋友遇到 python 安装 matplotlib 时的问题&#xff0c;笔者帮忙远程调试(踩了不少坑)。网上的解决方案有很多无效&#xff0c;以此来记录以下个人解决方案。 在使用指令 pip install matplotlib出现如下报错&#xff1a; “…

移远通信再推系列高性能卫星、5G、GNSS及三合一组合天线

4月23日&#xff0c;全球领先的物联网整体解决方案供应商移远通信正式宣布&#xff0c;再次推出多款高性能天线产品&#xff0c;以进一步满足物联网市场对高品质天线产品的需求。 其中包括卫星天线YETN001L1A、三合一组合天线YEMA300QXA和YEMN302Q1A&#xff0c;外部5G天线YECN…

Unity对应的c#版本

本文主要是记录一下unity已经开始兼容c#的版本和.net版本&#xff0c;以便更好的利用c#的特性。 c#和.net对应情况 微软已经将.net开发到.net 9了&#xff0c;但是unity的迭代速度远没有c#迭代速度快&#xff0c;已知unity最新的LTS版本unity2023已经兼容了c#9 可以在unity手册…

生成数据能否帮助模型训练?

能否利用生成模型生成的假数据来辅助学习&#xff1f; 到底是可以左脚踩右脚&#xff08;bootsrap&#xff09;地实现 weak-to-strong 的不断提升&#xff0c;还是像鸡生蛋、蛋生鸡一样&#xff0c;只不过是徒劳无功&#xff1f; 论文题目&#xff1a; Do Generated Data Alw…

集成学习算法学习笔记

一、集成学习的基本思想 三个臭皮匠顶一个诸葛亮 集成学习会考虑多个评估器的建模结果&#xff0c;汇总后得到一个综合的结果&#xff0c;以此来获取比单个模型更好的回归或分类表现。 很多独立的机器学习算法&#xff1a;决策树、神经网络、支持向量机 集成学习构建了一组基…

如何在iPhone/iPad上恢复已删除的微信消息?

“我从我的iPhone上删除了一些微信消息。我想知道我是否可以从我的iPhone上恢复已删除的微信消息。我尝试了一些方法&#xff0c;但没有一个可以恢复我丢失的消息&#xff0c;只能恢复我的短信。谁可以给我有什么建议吗&#xff1f;” ——蒂娜 如何在iPhone或iPad上恢复已删除…

3122.使矩阵满足条件的最少操作次数

周赛第三题,知道要用动态规划,但是不知道怎么回到子问题 显然根据题意我们需要让每一列都相同,但是相邻列不能选择同一种数字,观察到数据nums[i]介于0-9,我们就以此为突破口. 首先我们用count[n][10], count[i][j]记录第i1列值为j的元素个数,转移方程如下: dfs(i,pre) max(dfs…

根据标签最大层面ROI提取原始图像区域

今天要实现的任务是提取肿瘤的感兴趣区域。 有两个文件&#xff0c;一个是nii的原始图像文件&#xff0c;一个是nii的标签文件。 我们要实现的是&#xff1a;在标签文件上选出最大层面&#xff0c;然后把最大层面的ROI映射到原始图像区域&#xff0c;在原始图像上提裁剪出ROI…

6.模板初阶

目录 1.泛型编程 2. 函数模板 2.1 函数模板概念 2.2函数模板格式 2.3 模板的实现 2.4函数模板的原理 2.5 函数模板的实例化 3.类模板 1.泛型编程 我们如何实现一个 交换函数呢&#xff1f; 使用函数重载虽然可以实现&#xff0c;但是有一下几个不好的地方&#xff1a; …

(学习日记)2024.04.26:UCOSIII第五十节:User文件夹函数概览(uC-CPU文件夹)

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…

docker容器技术篇:集群管理实战mesos+zookeeper+marathon(二)

docker集群管理实战mesoszookeepermarathon&#xff08;二&#xff09; 一 实验环境 操作系统&#xff1a;centos7.9 二 基础环境配置以及安装mesos 安装过程请点击下面的链接查看&#xff1a; 容器集群管理实战mesoszookeepermarathon&#xff08;一&#xff09; 三 安装…

WPF 资源基础

动态资源/静态资源 UI代码 <Window x:Class"WpfApp1.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/ex…

leetcode_37.解数独

37. 解数独 题目描述&#xff1a;编写一个程序&#xff0c;通过填充空格来解决数独问题。 数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08;请参考…

我教你如何可翻页电子画册

​电子画册是一种创新的方式&#xff0c;可以将传统的纸质画册转化为数字化的形式&#xff0c;并且具备翻页的功能。它不仅可以提供更好的阅读体验&#xff0c;还可以方便地分享给他人。 1.选择制作工具&#xff1a; 有许多在线平台和软件可以帮助你制作电子画册&#xff0c;比…

海康大华摄像头rtsp在网页中播放

一.项目说明 摄像头视频推流实现 支持rtsp&#xff1b;rtmp; 摄像头在浏览器中播放实现 内包含资源和对于的部署方案 资料中有详细部署资料和对于的api接口&#xff0c;支持二次开发。 二.项目实现效果 三.下载地址 下载地址&#xff1a;http://www.gxcode.top/code

【春 联---turtle海龟画图】

春联 又称"春贴"、"门对"、"对联"&#xff0c;是过年时所贴的红色喜庆元素"年红"中一个种类。它以对仗工整、简洁箱巧的文字描绘美好形象&#xff0c;抒发美好愿 望&#xff0c;是中国特有的文学形式&#xff0c;是华人们过年 的重要习…