「数据结构」二叉搜索树1:实现BST
🎇个人主页:Ice_Sugar_7
🎇所属专栏:Java数据结构
🎇欢迎点赞收藏加关注哦!
实现BST
- 🍉二叉搜索树的性质
- 🍉实现二叉搜索树
- 🍌插入
- 🍌查找
- 🍌删除
- 🍉性能分析
🍉二叉搜索树的性质
二叉搜索树又称二叉排序树,它可以是一棵空树,也可以是有以下性质的二叉树
- 若左子树不为空,则左子树上所有节点的值都小于根节点的值
- 若右子树不为空,则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
因为左节点 < 根节点 < 右节点,所以二叉搜索树中序遍历
结果是升序序列
🍉实现二叉搜索树
🍌插入
插入成功返回true,插入失败返回false
(注意:如果树中已经有关键字key,那我们就不能再插入了)
//插入一个关键字keypublic boolean insert(int key) {TreeNode node = new TreeNode(key);if(root == null) {root = node;return true;}TreeNode cur = root;TreeNode parent = null; //保存cur的双亲节点while(cur != null) { //cur若为空,说明找到插入位置了if(cur.key < key) {parent = cur;cur = cur.right;} else if(cur.key > key) {parent = cur;cur = cur.left;} else { //树中已经有key,不能插入return false;}}//比较key和双亲节点的key,确定key要插在parent的左边还是右边if(key > parent.key)parent.right = node;if(key < parent.key)parent.left = node;return true;}
🍌查找
根据二叉搜索树的特点,key比当前节点的值小,就往左子树找;反之则往右子树找
//查找key是否存在public TreeNode search(int key) {if(root == null)return null;TreeNode cur = root;while(cur != null) {if(cur.key < key) {cur = cur.right;} else if(cur.key > key) {cur = cur.left;} else {return cur;}}return null; //到这里说明找不到,返回null}
🍌删除
这个操作比较麻烦,因为它需要处理多种情况。大方向上分为三种情况讨论:
假设根节点为root,待删除节点是cur,它的双亲节点为parent
-
cur的左节点为空
①cur就是根节点(此时parent不存在),只需让root = root.right
②cur不是根节点,是parent的左节点
③cur不是根节点,是parent的右节点
②和③的分析如下图:
-
cur的右节点为空
这个和1的分析思路是一样的,就不多赘述了 -
cur的左右节点都不为空
使用替换法
进行删除:
就是从cur的左子树中找到最右侧的节点(这个节点是左子树中关键字最大的)max,或者从右子树中找到最左侧节点(关键字最小)min,用它的值替换掉cur的值,然后再把max或min删掉
其实就是转化为1和2的问题,因为max和min的左节点和右节点肯定有一个为空
来看下代码实现:
//删除key的值public boolean remove(int key) {if(root == null)return false;TreeNode cur = root;TreeNode parent = null;while(cur != null) {if(cur.key < key) {parent = cur;cur = cur.right;} else if(cur.key > key) {parent = cur;cur = cur.left;} else { //找到cur了,准备把它删了if(cur.left == null) {if(cur == root) {root = root.right;return true;} else {if(cur == parent.left)parent.left = cur.right;if(cur == parent.right)parent.right = cur.right;}} else if(cur.right == null) {if(cur == root) {root = root.left;return true;} else {if(cur == parent.left)parent.left = cur.left;if(cur == parent.right)parent.right = cur.left;}} else { //左右都不为空TreeNode target = cur.right; //让target去右子树找到最左边的节点TreeNode targetParent = cur;while(target.left != null) {targetParent = target;target = target.left;}//将tmp的关键字赋给curcur.key = target.key;//删除tmp节点if(targetParent.left == target) {targetParent.left = cur.right;} else {targetParent.right = cur.right;}}return true;}}return false;}
🍉性能分析
插入和删除等操作都必须先查找,所以查找的效率代表二叉搜索树中各个操作的性能
每次查找都要比较key和当前节点的值。
那么在最好的情况下,二叉搜索树是完全二叉树,平均比较次数是logN
而在最坏的情况下,此时二叉搜索树退化为单支树,平均比较次数就是N / 2
相关文章:
「数据结构」二叉搜索树1:实现BST
🎇个人主页:Ice_Sugar_7 🎇所属专栏:Java数据结构 🎇欢迎点赞收藏加关注哦! 实现BST 🍉二叉搜索树的性质🍉实现二叉搜索树🍌插入🍌查找🍌删除 &am…...
可达鸭二月月赛——基础赛第六场(周五)题解,这次四个题的题解都在这一篇文章内,满满干货,含有位运算的详细用法介绍。
姓名 王胤皓 T1 题解 T1 题面 T1 思路 样例输入就是骗人的,其实直接输出就可以了,输出 Hello 2024,注意,中间有一个空格! T1 代码 #include<bits/stdc.h> using namespace std; #define ll long long int …...
ELFK日志采 - QuickStart
文章目录 架构选型ELKEFLK ElasticsearchES集群搭建常用命令 Filebeat功能介绍安装步骤Filebeat配置详解filebeat常用命令 Logstash功能介绍安装步骤Input插件Filter插件Grok Filter 插件Mutate Filter 插件常见的插件配置选项:Mutate Filter配置案例: O…...
微信小程序的图片色彩分析,窃取网络图片的主色调
1、安装 Mini App Color Thief 包 包括下载包,简单使用都有,之前写了,这里就不写了 网址:微信小程序的图片色彩分析,窃取主色调,调色板-CSDN博客 2、 问题和解决方案 问题:由于我们的窃取图片的…...
Leetcode 121 买卖股票的最佳时机
题意理解: 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交…...
SQL语言复习-----1
1,前言 SQL是计算机的一门基础语言,无论在开发还是数据库管理上都是非常重要,最近总结归纳了一下相关知识,记录如下。 2,归纳 SQL是结构化查询语言。 关系数据库有三级模式结构。 基本表和视图一样都是关系。 举例…...
爬虫2—用爬虫爬取壁纸(想爬多少张爬多少张)
先看效果图: 我这个是爬了三页的壁纸60张。 上代码了。 import requests import re import os from bs4 import BeautifulSoupcount0 img_path "./壁纸图片/"#指定保存地址 if not os.path.exists(img_path):os.mkdir(img_path) headers{ "User-Ag…...
学习Android的第九天
目录 Android Button 按钮 基本的按钮 StateListDrawable 范例 使用颜色值绘制圆角按钮 自制水波纹效果 Android ImageButton 图片按钮 ImageButton 不同状态下的 ImageButton Android RadioButton 单选按钮 RadioButton 获得选中的值 Android Button 按钮 在 And…...
课时21:内置变量_脚本相关
2.4.1 脚本相关 学习目标 这一节,我们从 基础知识、简单实践、小结 三个方面来学习 基础知识 脚本相关的变量解析 序号变量名解析1$0获取当前执行的shell脚本文件名2$n获取当前执行的shell脚本的第n个参数值,n1…9,当n为0时表示脚本的文…...
ubuntu22.04@laptop OpenCV Get Started: 006_annotating_images
ubuntu22.04laptop OpenCV Get Started: 006_annotating_images 1. 源由2. line/circle/rectangle/ellipse/text 应用Demo3 image_annotation3.1 C应用Demo3.2 Python应用Demo3.3 重点过程分析3.3.1 划线3.3.2 画圆3.3.3 矩形3.3.4 椭圆3.3.5 文字 4. 总结5. 参考资料 1. 源由 …...
【制作100个unity游戏之23】实现类似七日杀、森林一样的生存游戏10(附项目源码)
本节最终效果演示 文章目录 本节最终效果演示系列目录前言快捷栏绘制UI代码控制快捷列表信息 源码完结 系列目录 前言 欢迎来到【制作100个Unity游戏】系列!本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第23篇中,我们将探索如何制作…...
uniapp vue3怎么调用uni-popup组件的this.$refs.message.open() ?
vue2代码 <!-- 提示信息弹窗 --><uni-popup ref"message" type"message"><uni-popup-message :type"msgType" :message"messageText" :duration"2000"></uni-popup-message></uni-popup>typ…...
【深度学习:语义分割】语义分割简介
【深度学习:语义分割】语义分割简介 什么是图像分割?了解语义分割数据采集语义分割的深度学习实现全卷积网络上采样跳跃连接U-NetDeepLab多尺度物体检测金字塔场景解析网络(PSPNet) 语义分割的应用医学影像自动驾驶汽车农业图片处…...
前端开发_AJAX基本使用
AJAX概念 AJAX是异步的JavaScript和XML(Asynchronous JavaScript And XML)。 简单点说,就是使用XMLHttpRequest对象与服务器通信。 它可以使用JSON,XML,HTML和text文本等格式发送和接收数据。 AJAX最吸引人的就是它的“异步"特性&am…...
OnlyOffice-8.0版本深度测评
OnlyOffice 是一套全面的开源办公协作软件,不断演进的 OnlyOffice 8.0 版本为用户带来了一系列引人瞩目的新特性和功能改进。OnlyOffice 8.0 版本在功能丰富性、安全性和用户友好性上都有显著提升,为用户提供了更为强大、便捷和安全的文档处理和协作环境…...
【Go】一、Go语言基本语法与常用方法容器
GO基础 Go语言是由Google于2006年开源的静态语言 1972:(C语言) — 1983(C)—1991(python)—1995(java、PHP、js)—2005(amd双核技术 web端新技术飞速发展&…...
杨中科 ASP.NETCORE 高级14 SignalR
1、什么是websocket、SignalR 服务器向客户端发送数据 1、需求:Web聊天;站内沟通。 2、传统HTTP:只能客户端主动发送请求 3、传统方案:长轮询(Long Polling)。缺点是?(1.客户端发送请求后&…...
哪家洗地机比较好用?性能好的洗地机推荐
在众多功能中,我坚信洗地机的核心依旧是卓越的清洁能力以及易于维护的便捷性,其他的附加功能可以看作是锦上添花,那么如何找到性能好的洗地机呢?我们一起看看哪些洗地机既能确保卫生效果还能使用便利。 洗地机工作原理࿱…...
学习与非学习
学习与非学习是人类和动物行为表现中的两种基本形式,它们在认知过程和行为适应上有着根本的区别。理解这两者之间的差异对于把握认知发展、心理学以及教育学等领域的核心概念至关重要。 学习 学习是一个获取新知识、技能、态度或价值观的过程,它导致行为…...
牛客网SQL进阶127: 月总刷题数和日均刷题数
官网链接: 月总刷题数和日均刷题数_牛客题霸_牛客网现有一张题目练习记录表practice_record,示例内容如下:。题目来自【牛客题霸】https://www.nowcoder.com/practice/f6b4770f453d4163acc419e3d19e6746?tpId240 0 问题描述 基于练习记录表…...
19:Web开发模式与MVC设计模式-Java Web
目录 19.1 Java Web开发模式19.2 MVC设计模式详解19.3 MVC与其他Java Web开发模式的区别总结19.4 应用场景总结 在Java Web应用程序开发领域,有效的架构模式和设计模式对提高代码可维护性、模块化以及团队协作至关重要。本文将探讨Java Web开发中的常见模式——模型…...
Z字形变换
问题: 将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下: P A H N A P L S I I G Y I R 之后,你…...
飞书上传图片
飞书上传图片 1. 概述1.1 访问凭证2. 上传图片获取image_key1. 概述 飞书开发文档上传图片: https://open.feishu.cn/document/server-docs/im-v1/image/create 上传图片接口,支持上传 JPEG、PNG、WEBP、GIF、TIFF、BMP、ICO格式图片。 在请求头上需要获取token(访问凭证) …...
Java微服务学习Day1
文章目录 认识微服务服务拆分及远程调用服务拆分服务远程调用提供者与消费者 Eureka注册中心介绍构建EurekaServer注册user-serviceorder-service完成服务拉取 Ribbon负载均衡介绍原理策略饥饿加载 Nacos注册中心介绍配置分级存储负载均衡环境隔离nacos注册中心原理 认识微服务…...
STM32标准库驱动W25Q64模块读写字库数据+OLED0.96显示例程
STM32标准库驱动W25Q64 模块读写字库数据OLED0.96显示例程 🎬原创作者对W25Q64保存汉字字库演示: W25Q64保存汉字字库 🎞测试字体显示效果: 📑功能实现说明 利用W25Q64保存汉字字库,OLED显示汉字的时候&…...
【java】简单的Java语言控制台程序
一、用于文本文件处理的Java语言控制台程序示例 以下是一份简单的Java语言控制台程序示例,用于文本文件的处理。本例中我们将会创建一个程序,它会读取一个文本文件,显示其内容,并且对内容进行计数,然后将结果输出到控…...
【服务器数据恢复】HP EVA虚拟化磁盘阵列数据恢复原理方案
EVA存储结构&原理: EVA是虚拟化存储,在工作过程中,EVA存储中的数据会不断地迁移,再加上运行在EVA上的应用都比较繁重,磁盘负载高,很容易出现故障。EVA是通过大量磁盘的冗余空间和故障后rss冗余磁盘动态…...
08-OpenFeign-结合Sentinel,实现熔断降级
当我们在对服务远程调用时,会因为服务的请求超时、抛出异常等情况,导致调用失败。 如果短时间内,产生大量请求异常。引发上游的调用方请求积压,最终会引起整个调用链雪崩。 为此我们需要对核心的调用过程进行监控,当…...
15.实现数组的扁平化
实现方式1(递归) 普通的递归思路很容易理解,就是通过循环递归的方式,一项一项地去遍历,如果每一项还是一个数组,那么就继续往下遍历,利用递归程序的方法,来实现数组的每一项的连接: let arr […...
对话模型Demo解读(使用代码解读原理)
文章目录 前言一、数据加工二、模型搭建三、模型训练1、构建模型2、优化器与损失函数定义3、模型训练 四、模型推理五、所有Demo源码 前言 对话模型是一种人工智能技术,旨在使计算机能够像人类一样进行对话和交流。这种模型通常基于深度学习和自然语言处理技术&…...
Android 自定义BaseFragment
直接上代码: BaseFragment代码: package com.example.custom.fragment;import android.content.Context; import android.os.Bundle; import android.view.LayoutInflater; import android.view.View; import android.view.ViewGroup; import androidx…...
[C#] 如何对列表,字典等进行排序?
对列表进行排序 下面是一个基于C#的列表排序的案例: using System; using System.Collections.Generic;class Program {static void Main(string[] args){// 创建一个列表List<int> numbers new List<int>() { 5, 2, 8, 1, 10 };// 使用Sort方法对列…...
Mac 下载安装Java、maven并配置环境变量
下载Java8 下载地址:https://www.oracle.com/java/technologies/downloads/ 根据操作系统选择版本 没有oracle账号需要注册、激活登录 mac直接选择.dmg文件进行下载,下载后安装。 默认安装路径:/Library/Java/JavaVirtualMachines/jdk-1…...
【多模态】27、Vary | 通过扩充图像词汇来提升多模态模型在细粒度感知任务(OCR等)上的效果
文章目录 一、背景二、方法2.1 生成 new vision vocabulary2.1.1 new vocabulary network2.1.2 Data engine in the generating phrase2.1.3 输入的格式 2.2 扩大 vision vocabulary2.2.1 Vary-base 的结构2.2.2 Data engine2.2.3 对话格式 三、效果3.1 数据集3.2 图像细粒度感…...
|Python新手小白低级教程|第二十章:函数(2)【包括石头剪刀布判断程序(模拟版)】
文章目录 前言一、复习一、函数实战之——if语句特殊系统1.判断等第分数(函数名为mark(参数num))2.石头剪刀布判断程序 二、练习总结 前言 Hello,大家好,我是你们的BoBo仔,感谢你们来阅读我的文…...
vue3 之 商城项目—home
home—整体结构搭建 根据上面五个模块建目录图如下: home/index.vue <script setup> import HomeCategory from ./components/HomeCategory.vue import HomeBanner from ./components/HomeBanner.vue import HomeNew from ./components/HomeNew.vue import…...
git flow与分支管理
git flow与分支管理 一、git flow是什么二、分支管理1、主分支Master2、开发分支Develop3、临时性分支功能分支预发布分支修补bug分支 三、分支管理最佳实践1、分支名义规划2、环境与分支3、分支图 四、git flow缺点 一、git flow是什么 Git 作为一个源码管理系统,…...
【Linux】学习-进程信号
进程信号 信号入门 生活角度的信号 你在网上买了很多件商品,再等待不同商品快递的到来。但即便快递没有到来,你也知道快递来临时,你该怎么处理快递。也就是你能“识别快递”,也就是你意识里是知道如果这时候快递员送来了你的包裹,你知道该如何处理这些包裹当快递员到了你…...
webgis后端安卓系统部署攻略
目录 前言 一、将后端项目编译ARM64 二、安卓手机安装termux 1.更换为国内源 2.安装ssh远程访问 3.安装文件远程访问 三、安装postgis数据库 1.安装数据库 2.数据库配置 3.数据导入 四、后端项目部署 五、自启动设置 总结 前言 因为之前一直做的H5APP开发…...
【数据分享】1929-2023年全球站点的逐日平均风速数据(Shp\Excel\免费获取)
气象数据是在各项研究中都经常使用的数据,气象指标包括气温、风速、降水、能见度等指标,说到气象数据,最详细的气象数据是具体到气象监测站点的数据! 有关气象指标的监测站点数据,之前我们分享过1929-2023年全球气象站…...
【多模态大模型】视觉大模型SAM:如何使模型能够处理任意图像的分割任务?
SAM:如何使模型能够处理任意图像的分割任务? 核心思想起始问题: 如何使模型能够处理任意图像的分割任务?5why分析5so分析 总结子问题1: 如何编码输入图像以适应分割任务?子问题2: 如何处理各种形式的分割提示?子问题3:…...
Shell之sed
sed是什么 Linux sed 命令是利用脚本来处理文本文件。 可依照脚本的指令来处理、编辑文本文件。主要用来自动编辑一个或多个文件、简化对文件的反复操作、编写转换程序等。 sed命令详解 语法 sed [-hnV][-e <script>][-f<script文件>][文本文件] sed [-nefr] [动作…...
AJAX——认识URL
1 什么是URL? 统一资源定位符(英语:Uniform Resource Locator,缩写:URL,或称统一资源定位器、定位地址、URL地址)俗称网页地址,简称网址,是因特网上标准的资源的地址&…...
《Docker极简教程》--Docker环境的搭建--在Linux上搭建Docker环境
更新系统:首先确保所有的包管理器都是最新的。对于基于Debian的系统(如Ubuntu),可以使用以下命令:sudo apt-get update sudo apt-get upgrade安装必要的依赖项:安装一些必要的工具,比如ca-certi…...
开源微服务平台框架的特点是什么?
借助什么平台的力量,可以让企业实现高效率的流程化办公?低代码技术平台是近些年来较为流行的平台产品,可以帮助很多行业进入流程化办公新时代,做好数据管理工作,从而提升企业市场竞争力。流辰信息专业研发低代码技术平…...
C#系列-C#操作UDP发送接收数据(10)
在C#中,发送UDP数据并接收响应通常涉及创建两个UdpClient实例:一个用于发送数据,另一个用于接收响应。以下是发送UDP数据并接收响应的示例代码: 首先,我们需要定义一个方法来发送UDP数据,并等待接收服务器…...
突破编程_C++_面试(基础知识(10))
面试题29:什么是嵌套类,它有什么作用 嵌套类指的是在一个类的内部定义的另一个类。嵌套类可以作为外部类的一个成员,但它与其声明类型紧密关联,不应被用作通用类型。嵌套类可以访问外部类的所有成员,包括私有成员&…...
初步探索Pyglet库:打造轻量级多媒体与游戏开发利器
目录 pyglet库 功能特点 安装和导入 安装 导入 基本代码框架 导入模块 创建窗口 创建控件 定义事件 运行应用 程序界面 运行结果 完整代码 标签控件 常用事件 窗口事件 鼠标事件 键盘事件 文本事件 其它场景 网页标签 音乐播放 图片显示 祝大家新…...
【npm】安装全局包,使用时提示:不是内部或外部命令,也不是可运行的程序或批处理文件
问题 如图,明明安装Vue是全局包,但是使用时却提示: 解决办法 使用以下命令任意一种命令查看全局包的配置路径 npm root -g 然后将此路径(不包括node_modules)添加到环境变量中去,这里注意,原…...
Go 语言 for 的用法
For statements 本文简单翻译了 Go 语言中 for 的三种用法,可快速学习 Go 语言 for 的使用方法,希望本文能为你解开一些关于 for 的疑惑。详细内容可见文档 For statements。 For statements with single condition 在最简单的形式中,只要…...