数据结构-二叉搜索树
二叉搜索树:BST(Binary Search Tree)
二叉搜索树是二叉树,可以为空,如果不为空,满足以下性质:
- 非空左子树的所有键值小于其根节点的键值
- 非空右子树的所有键值大于其根节点的键值
- 左、右字数本身也都是二叉搜索树
二叉搜索树的特点:
- 二叉搜索树的特点就是相对较小的值总是保存在左节点上,相对较大的值总是保存在右节点上
- 查找效率非常高
二叉搜索树常见的操作:
- insert(key, value):向树中插入数据
- search(key):在树中查找
- remove(key):从树中移除
- update(key,value):修改节点数据
- inOrderTraverse:通过中序遍历方式遍历所有节点
- preOrderTraverse:通过先序遍历方式遍历所有节点
- postOrderTraverse:通过后序遍历方式遍历所有节点
- min:返回树中最小的键/值
- max:返回树中最大的键/值
class Node {constructor(key) {this._key = key;this._left = null;this._right = null;}
}
class BinarySearchTree {constructor() {this._root = null;}insert(key) {const insertNode = (node, newNode) => {if(newNode._key <= node._key) {if(node._left === null) {node._left = newNode;} else {insertNode(node._left, newNode);}} else {if(node._right === null) {node._right = newNode;} else {insertNode(node._right, newNode);}}}const newNode = new Node(key)if (this._root === null) {this._root = newNode} else {insertNode(this._root, newNode) }}preOrderTraverse(handler = (value) => {console.log(value)}) {const preOrderTraverseNode = (node) => {if (node === null) {return }handler(node._key)preOrderTraverseNode(node._left)preOrderTraverseNode(node._right)}preOrderTraverseNode(this._root)}midOrderTraverse(handler = (value) => {console.log(value)}) {const midOrderTraverseNode = (node) => {if (node === null) {return }midOrderTraverseNode(node._left)handler(node._key)midOrderTraverseNode(node._right)}midOrderTraverseNode(this._root)}postOrderTraverse(handler = (value) => {console.log(value)}) {const postOrderTraverseNode = (node) => {if (node === null) {return }postOrderTraverseNode(node._left)postOrderTraverseNode(node._right)handler(node._key)}postOrderTraverseNode(this._root)}min() {if (this._root === null) {return null}let node = this._rootwhile(true) {if (node._left === null) {return node._key}node = node._left}}max() {if (this._root === null) {return null}let node = this._rootwhile(true) {if (node._right === null) {return node._key}node = node._right}}search(key) {const searchNode = (node, key) => {if (node === null) {return false}if (node._key === key) {return true}if (key < node._key) {return searchNode(node._left, key)} else {return searchNode(node._right, key)}}return searchNode(this._root, key)}remove(key) {if (this._root === null) {return false}let current = this._rootlet parent = nulllet isLeftChild = truewhile (current._key !== key) {parent = currentif (key < current._key) {isLeftChild = truecurrent = current._left} else {isLeftChild = falsecurrent = current._right}if (current === null) {return false}}// 删除叶子节点if (current._left === null && current._right === null) {if (current === this._root) {this._root = null} else {if (isLeftChild) {parent._left = null} else {parent._right = null}}}// 删除有一个子节点else if (current._left === null ) {if (current === this._root) {this._root = current._right} else if (isLeftChild) {parent._left = current._right} else {parent._right = current._right}} else if (current._right === null) {if (current === this._root) {this._root = current._left} else if (isLeftChild) {parent._left = current._left} else {parent._right = current._left}} else {const getExChangeTargetNode = (current) => {let node = current._rightlet parentNode = currentlet isRightClick = truewhile(true) {if (node._left === null) {if (isRightClick) {parentNode._right = node._right} else {parentNode._left = node._right}return node}isRightClick = falseparentNode = nodenode = node._left}}const targetNode = getExChangeTargetNode(current);if (current !== this._root) {if (isLeftChild) {parent._left = targetNode} else {parent._right = targetNode}} else {this._root = targetNode}targetNode._right = current._righttargetNode._left = current._left}return true}}
相关文章:
数据结构-二叉搜索树
二叉搜索树:BST(Binary Search Tree) 二叉搜索树是二叉树,可以为空,如果不为空,满足以下性质: 非空左子树的所有键值小于其根节点的键值非空右子树的所有键值大于其根节点的键值左、右字数本身也都是二叉搜索树 二叉…...
JUnit:Java开发者不可或缺的单元测试框架
在软件开发过程中,测试是确保代码质量的关键环节。单元测试作为测试体系的基础,对提升代码质量、降低bug率、增强软件稳定性具有重要作用。JUnit 作为 Java 语言事实上的标准单元测试框架,已经成为 Java 开发者进行单元测试的首选工具。本文将…...
NG32单片机GPIO口配置方式
目录 一、引言 二、GPIO口基本结构 三、GPIO口配置方式 四、工作原理 五、总结 一、引言 NG32单片机是一款集成度高、功能强大的微控制器。其中,GPIO(General Purpose Input/Output)口作为单片机与外部设备通信的重要接口,具…...
SpringCloud-OpenFeign拓展-连接池、最佳使用方法、日志输出
目录 1 OpenFeign连接池 1.1 常见连接类型 1.2 连接池使用方法 1.2.1 引入依赖 1.2.2 开启连接池功能 1.2.3 配置完成,重启实例即可,底层将更改设置。 2 OpenFeign最佳使用方法 2.1 每个微服务都是单独的project,内部有三个独立模块 …...
跨链协议中Cosmos IBC、Polkadot/XCM、Celer Network的区别以及用途
跨链协议是实现不同区块链之间通信和价值转移的关键技术。Cosmos IBC、Polkadot/XCM 和 Celer Network 是三个在跨链领域内具有代表性的协议,它们各自有着独特的设计理念和应用场景。下面是这三个协议的详细对比: Cosmos IBC (Inter-Blockchain Communi…...
电子画册制作与传统画册相比,有哪些优势?
在当今数字化时代,电子画册作为一种新兴的媒体形式,其制作与传统画册相比具有显著的优势。以下是对这些优势的详细探讨。 首先,电子画册的制作过程通常更加便捷和经济。相较于传统画册需要经历的繁琐的印刷过程,电子画册的制作大多…...
postman如何导入证书
1、打开postman,点击Settings。 2、添加证书。 3、填写要访问平台的URL路径及端口、证书文件、证书密码。 4、添加完之后即可立即调用postman。...
RocketMQ教程(八):RocketMQ的集群搭建
传送门:RocketMQ教程汇总,让你从入门到精通 集群架构 RocketMQ 的各个组件都可以搭建成集群部署,Broker 还可以搭建成主从架构,下面介绍的主要是 Broker 集群。 数据复制策略 复制策略是Broker的Master与Slave间的数据同步方式。分为同步复制与异步复制: 同步复制 消…...
线上观看人次2万+!「飞天技术沙龙-CentOS 迁移替换专场」北京站圆满结束
5 月 29 日,阿里云联合龙蜥社区共同举办的「飞天技术沙龙-CentOS 迁移替换专场」于北京圆满结束,在线观看人次 2 万。本次活动现场汇聚了来自浪潮信息、Intel、龙芯、统信软件、红旗软件、电子五所等多家操作系统产业头部企业和机构,大家围绕…...
Docker基本架构概览-1
Docker基本架构概览 Docker架构 Docker采用客户端-服务器(C/S)架构,主要组件包括: Docker Client 用户与Docker交互的接口,发送命令到Docker守护进程。 Docker Daemon 运行在后台,接收并处理Docker客户端…...
OZON云仓靠谱吗,OZON云仓垫资提货模式
在电商飞速发展的今天,物流仓储成为了支撑整个电商生态的重要基石。OZON云仓作为市场上新兴的仓储物流服务提供商,凭借其先进的技术和灵活的服务模式,受到了不少电商卖家和消费者的关注。但随之而来的是一系列疑问:OZON云仓靠谱吗…...
数据集笔记:DGraph 大规模动态图数据集
dgraph-web (xinye.com) 1 数据集介绍 DGraph 是一个有向无权的动态图,包含超过 370 万个节点以及 430 万条动态边DGraph 中的节点表示金融借贷用户,有向边表示紧急联系人关系,每个节点包含脱敏后的属性特征,以及表示是否为金融…...
一些常用的git指令总结
1、git add 文件名 :该 命令可将该文件的修改添加到暂存区 比如:我刚刚修改了my_test.cpp文件,这时就可以使用git add my_test.cpp. 就将该修改添加到了暂存区。 2、git commit -m "......说明" 就是将当前的修改记录提交到本地…...
【HarmonyOS】遇见的问题汇总
一、当前编辑的页面,预览打不开 1、问题说明 当前编辑的页面,预览打不开,日志提示如下: Route information is not configured for the current page. To avoid possible redirection issues, configure route information for…...
C# NX二次开发-获取圆弧中心点和半径
使用UF函数可以获取圆弧边或圆弧线中心点和半径: 1.使用 UF_CURVE_ask_arc_data: theUf.Curve.AskArcData(edge.Tag, out UFCurve.Arc arc);theUf.Curve.CreateArc(ref arc, out Tag arc_tag);double[] matrix_values new double[9];double[] vec_product new double[3];theU…...
鸿蒙原生应用元服务开发-位置服务地理编码转化开发
(逆)地理编码转化开发 场景概述 使用坐标描述一个位置,非常准确,但是并不直观,面向用户表达并不友好。系统向开发者提供了以下两种转化能力。 地理编码转化:将地理描述转化为具体坐标。 逆地理编码转化能力…...
【ArcGISPro SDK】构建多面体要素
结果展示 每个面构建顺序 代码 using ArcGIS.Core.CIM; using ArcGIS.Core.Data; using ArcGIS.Core.Geometry; using ArcGIS.Desktop.Catalog; using ArcGIS.Desktop.Core; using ArcGIS.Desktop.Editing; using ArcGIS.Desktop.Extensions; using ArcGIS.Desktop.Framework;…...
leetcode够用之java语法
常用方法 Arrays.sort()排序 import java.util.Arrays;public class Main {public static void main(String[] args) {int[] numbers {9, 2, 5, 1, 7, 3};Arrays.sort(numbers);System.out.println(Arrays.toString(numbers)); // 输出: [1, 2, 3, 5, 7, 9]} }获取str中的第…...
pdf文件怎么改变大小?在线快速压缩pdf的方法
pdf作为一种常用的文件格式,使用这种文件类型的好处在于不仅拥有更好的兼容性,还可以设置密码来保证安全性,防止未授权用户查看内容,所以现在导出文件展示都会采用这种格式的来做内容展示。当遇到pdf文件过大问题时,想…...
inferCNV:scRNA-seq数据推断染色体拷贝数变化
inferCNV分析简介 inferCNV用于探索肿瘤单细胞RNA-Seq 数据,以确定体细胞大规模染色体拷贝数改变的证据,例如整个染色体或大片段染色体的增益或缺失。这是通过与一组参考“正常”细胞(这里的正常细胞可自行定义)进行比较…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
