二叉搜索树(Binary Search Tree)
1.二叉搜索树概念
二叉搜索树又称二叉排序树、二叉查找树,它或者是一棵空树,或者是具有以下性质的二叉树:
1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左右子树也分别为二叉搜索树
二叉搜索树一般不支持key值冗余(不允许有重复的key值)
二叉搜索树的性质使搜索时非常方便高效,最多搜索高度次O(log N)(二叉树退化为O(N),需要二叉搜索树平衡,使用AVL树或红黑树)
二叉搜索树的中序遍历能对key进行排序
二叉搜索树的应用:
K模型:K模型只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值
例如查找某个key值存不存在?
KV模型:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对
key值不能冗余,但value值可以相同
例如key值为单词,value为对应单词的英文
2.二叉搜索树操作(K模型为例)

2.1 二叉搜索树的查找
1. 从根节点开始查找,查找的key比cur(当前节点)的key大,则cur向右查找;查找的key比cur的key小,则cur向左查找,直到找到key值相同或查找的key值不存在。
2. 最多查找高度次,cur走到空,就说明查找的key不存在。
Node* find(const T& data)
{Node* cur = _root;while (cur){//找到返回if (data == cur->_data)return cur;//大于cur,向右找else if (data > cur->_data)cur = cur->_right;//小于cur,向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;
}
2.2 二叉搜索树的插入
1. 树为空树时,则直接新增节点,并作为该对象的根节点(_root)。
2. 树不为空树时,按二叉树的性质查找位置并插入

bool insert(const T& data)
{//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data > parent->_data)parent->_right = cur;elseparent->_left = cur;return true;
}
2.3 二叉搜索树的删除
查找元素是否在二叉搜索树中,如果不存在,则返回,否则要删除的节点分四种情况:
1. 要删除的节点无孩子节点 -- 直接删除该节点
2. 要删除的节点只有左孩子节点 -- 让左孩子节点替代该节点位置,并删除该节点
3. 要删除的节点只有右孩子节点 -- 让右孩子节点替代该节点位置,并删除该节点
4. 要删除的节点有左右孩子节点 -- 由二叉树性质,查找删除节点的右子树key值最小节点,让最小节点的key覆盖掉删除节点的key,最小节点一定是只有一个右孩子节点或没有孩子节点的情况,按1或2删除最小节点。(最小节点不可能存在左孩子,不然就不是最小节点了,更不可能有两个孩子)
bool erase(const T& data)
{//空树,删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}
}
2.4 二叉搜索树代码(K模型和KV模型)
KV模型与K模型类似,只是KV模型的data类型是pair类型,first是key,second是value。
K模型:
namespace myBSTree_K
{template <class T>struct BSTNode{BSTNode(const T& data = T()):_left(nullptr), _right(nullptr), _data(data){}BSTNode<T>* _left;BSTNode<T>* _right;T _data;};template <class T>class BSTree{typedef BSTNode<T> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree& tree){_root = _Copy(tree._root);}//析构函数无法传参,只能调用子函数进行递归销毁~BSTree(){//后序遍历销毁_destory(_root);_root = nullptr;}Node* find(const T& data){Node* cur = _root;while (cur){//找到返回if (data == cur->_data)return cur;//大于cur,向右找else if (data > cur->_data)cur = cur->_right;//小于cur,向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;}bool insert(const T& data){//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data > parent->_data)parent->_right = cur;elseparent->_left = cur;return true;}bool erase(const T& data){//空树,删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}}void InOrder(){_InOrder(_root);}private:void _destory(Node* root){if (root == nullptr){return;}_destory(root->_left);_destory(root->_right);delete root;root = nullptr;}Node* _Copy(const Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_data);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;}//中序遍历void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data << ' ';_InOrder(root->_right);}//成员变量Node* _root;};
}
KV模型:
namespace myBSTree_KV
{template <class K, class V>struct BSTNode{BSTNode(const pair<K,V>& data = pair<K,V>()):_left(nullptr), _right(nullptr), _data(data){}BSTNode<K,V>* _left;BSTNode<K,V>* _right;pair<K,V> _data;};template <class K, class V>class BSTree{typedef BSTNode<K,V> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree& tree){_root = _Copy(tree._root);}//析构函数无法传参,只能调用子函数进行递归销毁~BSTree(){//后序遍历销毁_destory(_root);_root = nullptr;}Node* find(const K& key){Node* cur = _root;while (cur){//找到返回if (key == cur->_data.first)return cur;//大于cur,向右找else if (key > cur->_data.first)cur = cur->_right;//小于cur,向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;}bool insert(const pair<K, V>& data){//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data.first > cur->_data.first){parent = cur;cur = cur->_right;}else if (data.first < cur->_data.first){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data.first > parent->_data.first)parent->_right = cur;elseparent->_left = cur;return true;}bool erase(const K& key){//空树,删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (key> cur->_data.first){parent = cur;cur = cur->_right;}else if (key < cur->_data.first){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}}//改--如果key相同,改value,如果key不存在,不改bool update(const pair<K, V>& data){Node* cur = find(data.first);if (cur == nullptr)return false;else{cur->_data.second = data.second;return true;}}void InOrder(){_InOrder(_root);}private:void _destory(Node* root){if (root == nullptr){return;}_destory(root->_left);_destory(root->_right);delete root;root = nullptr;}Node* _Copy(const Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_data);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;}//中序遍历void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data.first << ':' << root->_data.second << endl;_InOrder(root->_right);}//成员变量Node* _root;};
}
3. 二叉搜索树的性能分析
插入和删除操作都必须先查找,查找效率代表二叉搜索树的各个操作的性能
对有n个节点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是节点在二
叉搜索树的深度的函数,即结点越深,则比较次数越多,但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:log2N
最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为:N/2
二叉搜索树退化,使二叉搜索树性能丢失,需要使二叉搜索树平衡,可以使用AVL树和红黑树。
相关文章:
二叉搜索树(Binary Search Tree)
1.二叉搜索树概念 二叉搜索树又称二叉排序树、二叉查找树,它或者是一棵空树,或者是具有以下性质的二叉树: 1. 非空左子树的所有键值小于其根节点的键值 2. 非空右子树的所有键值大于其根节点的键值 3. 左右子树也分别为二叉搜索树 二叉搜索树一般不支持…...
Yii2框架的初始化及执行流程
当 Yii2 框架执行 index.php 入口脚本后,内部执行逻辑和顺序可以概括如下: 1、加载相关配置文件和关键组件: 加载 Composer 自动加载器: require DIR . ‘/…/vendor/autoload.php’; 加载 Yii 框架文件: require D…...
2024.1-2024.2pycharm无法打开terminal命令行
2024版的idea或pycharm打开terminal时会发生如下问题: Cannot open Windows PowerShell Failed to start [C:\Windows\System32\WindowsPowerShell\v1.0\powershell.exe,或 Cannot open Command Prompt Failed to start [C:\Windows\system32\cmd.exe] 需要点击标…...
50ETF期权移仓是什么?50ETF期权移仓要注意什么?
今天带你了解50ETF期权移仓是什么?50ETF期权移仓要注意什么?当前火热的期权交易市场,“移仓”同样是一门非常重要的技术。上证50ETF期权投资的过程中,我们可以进行一定的移仓操作的,如果移仓操作得好,可以很…...
软件工程概述(上)
1、软件的概念、特点和分类 要了解软件工程,首先让我们重新认识一下软件。如今可以说是一个软件定义一切的时代,虽然人工智能发展的如火如荼,但究其本质,核心还是软件。那么,如何给软件下一个定义呢?软件又…...
阿里云ubuntu系统安装mysql8.0
一、安装mysql8.0 1.已安装其他版本的mysql,需要删除 若没有不需要此操作 1 #卸载MySQL5.7版本 2 apt remove -y mysql-client5.7* mysql-community-server5.7* 4 # 卸载5.7的仓库信息 5 dpkg-l | grep mysql | awk iprint $2} | xargs dpkg -P2.更新仓库 apt u…...
自己搭建远程桌面服务器-RustDesk 极简版
linux搭建RustDesk保姆间教程_rustdesk linux-CSDN博客https://blog.csdn.net/yzs2022/article/details/135136491 背景 在某公司工作,向日葵等远程办公软件均已屏蔽,无法使用(也没有明文规定不允许使用远程控制软件),…...
数字资产是什么?怎么产生?怎么增长?
数字资产是什么? 数字资产是指企业或个人拥有或控制的,以电子数据形式存在的,在日常活动中持有以备出售或处于生产过程中的非货币性资产。它涵盖了广泛的范围,包括但不限于数字货币、数字证券、数字艺术品、虚拟土地等。这些资产…...
Centos7升级gitlab(17)
在 CentOS 7 中将 GitLab 从版本 17.1.1 升级到 17.2.2,涉及以下步骤。请务必在升级前备份数据,以防止升级过程中出现问题导致数据丢失。 升级步骤 1. 备份 GitLab 数据 在升级之前,确保已经备份了 GitLab 的数据,包括数据库、…...
Zookeeper详解以及常见的高可用关联组件
一、ZooKeeper 详解 Apache ZooKeeper 是一个开源的分布式协调服务,用于分布式应用程序之间的协调和管理。ZooKeeper 提供了一个高效、可靠的服务来帮助管理分布式系统中的共享配置信息、命名、同步和组服务等。 二、主要特性 1. 高可用性 ZooKeeper 集群通过选…...
Docker Containerd初体验
Docker Containerd概述 Containerd是一个开源的容器运行时,它提供了一种标准化的方式来管理容器的生命周期。该项目最初是由Docker开发团队创建的,并在后来成为了一个独立的项目,被纳入了Cloud Native Computing Foundation(C…...
开始使用 AWS SAM CLI
了解如何使用 AWS SAM CLI 在本地调试 lambda 函数 欢迎来到雲闪世界。我们将学习 AWS SAM CLI 的概念。SAM 是无服务器 应用程序 模型的缩写,是 Amazon Web Services 提供的一个框架,可以利用它在本地机器上构建应用程序并将其直接部署到 AWS Lambdas。…...
RK3588 RTL8125BG调试
RTL8125B是一款PCIE转RJ45的网卡控制器芯片,在底层调试时只需配置PCIE即可 diff --git a/arch/arm64/boot/dts/rockchip/rk3588-nvr-demo.dtsi b/arch/arm64/boot/dts/rockchip/rk3588-nvr-demo.dtsi index 798359eaf061..d8a7a43cdfa0 100755 --- a/arch/arm64/bo…...
Python自省(机制与函数)
Python 自省(Introspection)是一种强大的特性,它允许程序在运行时检查对象的类型、属性以及它们如何相互关联。这种能力让 Python 非常适合于快速开发、调试以及编写需要高度动态交互的代码。Python 的自省机制主要通过内置的函数和类型来实现…...
【JavaEE】JVM 内存区域划分,以及 Java 垃圾回收机制引用计数器,可达性分析等
目录 1. JVM执行流程 2. JVM运行时数据区 2.1 堆 2.2 Java虚拟机栈(线程私有) 2.3本地方法栈(线程私有) 2.4 程序计数器 2.5 元数据区 3. JVM的类加载机制 1) 加载 2) 验证 3) 准备 4) 解析 5) 初始化 双亲委派模型 4. java垃圾回收 4.1 死亡对象判断方法 a) …...
Web开发:C# MVC + Session机制实现授权免登录demo
token基础demo 【需求】 Home/Index 登录界面,校验成功后可以登录到Main/Index ,用户登录3分钟内关闭网站,再次访问Home/Index时可以免密登录Main/Index 【配置文件-Program.cs】 var builder WebApplication.CreateBuilder(args);// Add services t…...
【Qt】QWidget的font属性
QWidget的font属性 API说明 font() 获取当前 widget 的字体信息. 返回 QFont 对象. setFont(const QFont& font) 设置当前 widget 的字体信息. 关于Qfont 属性说明 family 字体家族. ⽐如 "楷体", "宋体", "微软雅⿊" 等. pointSiz…...
每天一个数据分析题(四百八十五)- 统计推断
假设检验中,关于p值说法正确的是? A. p值是在原假设成立时,样本观察结果发生的概率。 B. p值是接受原假设的概率 C. p值是相对样本统计量而言的 D. 用p值做决策比用域值做决策更准确 数据分析认证考试介绍:点击进入 题目来源…...
基于STM32的农业病虫害检测检测系统:OpenCV、MQTT、Flask框架、MySQL(代码示例)
一、项目概述 随着全球农业现代化的不断推进,智能农业监测系统应运而生。此项目旨在通过实时监测土壤湿度、温度等环境数据,结合作物生长状态的分析,提高农业生产效率和作物质量。通过引入STM32单片机、OpenCV图像处理技术和后端数据分析系统…...
算法日记day 39(动归之打家劫舍)
一、打家劫舍1 题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
