初级数据结构——二叉搜索树
目录
- 前言
- 一、定义
- 二、基本操作
- 三、时间复杂度分析
- 四、变体
- 五、动态图解
- 六、代码模版
- 七、经典例题
- [1.——700. 二叉搜索树中的搜索](https://leetcode.cn/problems/search-in-a-binary-search-tree/)
- 代码题解
- [2.——938. 二叉搜索树的范围和](https://leetcode.cn/problems/range-sum-of-bst/)
- 代码题解
- [3.——98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/)
- 代码题解
- 八、总结
- 结语
前言
这一期我们一起来学习二叉搜索树。二叉搜索树(Binary Search Tree, BST)是一种重要的数据结构,在计算机科学中广泛应用于查找、插入和删除操作。以下是对二叉搜索树的基本分析,包括其定义、性质、操作的时间复杂度以及一些变体。
一、定义
二叉搜索树是一种二叉树,其中每个节点包含一个键值,且满足以下性质:
左子树性质:左子树中所有节点的键值都小于根节点的键值。
右子树性质:右子树中所有节点的键值都大于根节点的键值。
递归性质:左子树和右子树本身也是二叉搜索树。
二、基本操作
1.查找(Search)
算法:从根节点开始,如果目标键值小于当前节点的键值,则递归地在左子树中查找;如果目标键值大于当前节点的键值,则递归地在右子树中查找;如果找到目标键值,则返回该节点。
时间复杂度:在最坏情况下(树退化为链表),时间复杂度为 O(n);在最优情况下(树是平衡的),时间复杂度为 O(logn)。
2.插入(Insert)
算法:从根节点开始,找到合适的位置插入新节点。如果目标键值小于当前节点的键值,则递归地在左子树中查找插入位置;如果目标键值大于当前节点的键值,则递归地在右子树中查找插入位置;如果目标键值已经存在,则根据具体需求更新节点(例如,更新节点的值或不做任何操作)。
时间复杂度:与查找操作类似,最坏情况下为 O(n),最优情况下为 O(logn)。
3.删除(Delete)
算法:找到要删除的节点,然后分三种情况处理:
叶子节点:直接删除。
只有一个子节点:用其子节点替代被删除节点。
有两个子节点:找到该节点的中序后继(或中序前驱),用其值替代被删除节点的值,然后递归删除中序后继(或中序前驱)。
时间复杂度:最坏情况下为 O(n),最优情况下为 O(logn)。
三、时间复杂度分析
二叉搜索树的时间复杂度依赖于树的高度。在最坏情况下(树退化为链表),树的高度为 n,因此各种操作的时间复杂度均为 O(n)。然而,在最优情况下(树是平衡的),树的高度为 logn,因此各种操作的时间复杂度均为 O(logn)。
四、变体
为了改善二叉搜索树在最坏情况下的性能,人们提出了多种变体:
平衡二叉搜索树(Balanced BST):如AVL树、红黑树等,通过维护树的平衡来确保操作的时间复杂度始终为 O(logn)。
B树(B-Tree):一种自平衡的树,能够保持数据有序,其设计目的是减少磁盘I/O操作,广泛应用于数据库和文件系统。
伸展树(Splay Tree):在每次查找操作后,通过一系列旋转操作将查找路径上的节点重新组织成一条链,使得下次查找更加高效。
五、动态图解
元素查找:
元素插入:
元素删除:
中序遍历
六、代码模版
#include<iostream>
using namespace std;template<typename T>
struct TreeNode {T val;TreeNode* left;TreeNode* right;TreeNode(T x):val(x),left(NULL),right(NULL){}TreeNode():val(0),left(NULL),right(NULL){}
};template<typename T>
class BinarySearchTree {
private:TreeNode<T>* root;TreeNode<T>* insertNode(TreeNode<T>* node, T val);TreeNode<T>* removeNode(TreeNode<T>* node, T val);bool searchNode(TreeNode<T>* node, T val);void inOrder(TreeNode<T>* node);
public:BinarySearchTree():root(NULL){}~BinarySearchTree();void insert(T val) {root = insertNode(root, val);}void remove(T val) {root = removeNode(root, val);}bool search(T val) {return searchNode(root, val);}void inOrderTraversal() {inOrder(root);cout << endl;}
};template<typename T>
BinarySearchTree<T>::~BinarySearchTree() {while (root) {remove(root->val);//每次都把root节点删除,每次删除都产生新的root节点}
}template<typename T>
TreeNode<T>* BinarySearchTree<T>::insertNode(TreeNode<T>* node, T val) {if (!node) {return new TreeNode<T>(val);//递归出口,该节点为空时就说明插入到当前位置,定义新的变量接收val}if (node->val > val) {node->left = insertNode(node->left, val);}else if (node->val < val) {node->right = insertNode(node->right, val);}return node;//说明当前节点与插入节点的值一致返回该节点即可
}template<typename T>
TreeNode<T>* BinarySearchTree<T>::removeNode(TreeNode<T>* node, T val) {if (!node)return NULL;//递归出口,如果找完了整棵树都没找到该值就返回NULLif (node->val > val) node->left = removeNode(node->left, val);else if (node->val < val)node->right = removeNode(node->right, val);else {//该节点的值等于要删除节点的值一致就说明找到了if (node->left == NULL && node->right == NULL) {//如果该节点为叶子结点,接直接删除该节点就行delete node;return NULL;//因为删除了该节点所以它就为空了返回即可}else if (node->left == NULL) {//要删除的节点只有右节点TreeNode<T>* rightChild = node->right;//定义一个变量储存该节点右节点的树delete node;return rightChild;}else if (node->right == NULL) {//与上同理TreeNode<T>* leftChild = node->left;delete node;return leftChild;}else {//如果左右节点都有TreeNode<T>* replacement = node->right;//从右子树中找值最小的节点while (replacement->left) {replacement = replacement->left;}node->val = replacement->val;//找到之后赋给该节点node->right = removeNode(node->right, replacement->val);//最后在删除最小值的节点}}return node;
}template<typename T>
bool BinarySearchTree<T>::searchNode(TreeNode<T>* node, T val) {if (!node)return false;//递归出口如果找完了整棵树都没找到该值就返回falseif (val < node->val) {//递归查找如果要查找的值小于当前节点那么就继续递归找左节点return searchNode(node->left, val);}else if (val > node->val) return searchNode(node->right, val);//与上同理return true;
}template<typename T>
void BinarySearchTree<T>::inOrder(TreeNode<T>* node) {if (node) {//中序遍历inOrder(node->left);cout << node->val << ',';inOrder(node->right);}
}int main() {BinarySearchTree<int> bst;bst.insert(30);bst.insert(10);bst.insert(20);bst.insert(40);bst.insert(90);bst.insert(69);bst.inOrderTraversal();//中序遍历为递增有序的数列bst.remove(40);bst.inOrderTraversal();return 0;
}
七、经典例题
1.——700. 二叉搜索树中的搜索
(蓝色字体可以点进去看原题)
代码题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root==NULL)return NULL;if(val>root->val)return searchBST(root->right,val);else if(root->val>val)return searchBST(root->left,val);return root;}
};
2.——938. 二叉搜索树的范围和
代码题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int rangeSumBST(TreeNode* root, int low, int high) {if(root==NULL)return 0;int sum=0;if(root->val>=low&&root->val<=high){sum+=root->val;}sum+=rangeSumBST(root->left,low,high);sum+=rangeSumBST(root->right,low,high);return sum;}
};
3.——98. 验证二叉搜索树
代码题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {vector<int> ret;void inOrder(TreeNode*root){if(root){inOrder(root->left);ret.push_back(root->val);inOrder(root->right);}}
public:bool isValidBST(TreeNode* root) {ret.clear();inOrder(root);//中序遍历之后就是递增的数列for(int i=1;i<ret.size();i++){if(ret[i]<=ret[i-1])return false;}return true;}
};
八、总结
二叉搜索树是一种简单而有效的数据结构,适用于许多查找、插入和删除操作。然而,其性能受树的高度影响,因此在最坏情况下可能退化为链表。为了克服这一缺点,可以使用平衡二叉搜索树等变体来确保操作的时间复杂度始终为 O(logn)。
结语
下期我会更新二叉搜索树的题库一共十多道,希望大家看完之后能去多多刷题巩固和运用知识点,敬请期待下期文章。
相信大家通过本期学习初步了解二叉树,下期作品我会更新二叉树的十几道题库,我们下期一起学习二叉树的实战应用。
相关文章:

初级数据结构——二叉搜索树
目录 前言一、定义二、基本操作三、时间复杂度分析四、变体五、动态图解六、代码模版七、经典例题[1.——700. 二叉搜索树中的搜索](https://leetcode.cn/problems/search-in-a-binary-search-tree/)代码题解 [2.——938. 二叉搜索树的范围和](https://leetcode.cn/problems/ra…...
C++设计模式之组合模式中如何实现同一层部件的有序性
在组合模式中,为了实现同一层上部件的有序性,可以采取以下几种设计方法: 1. 使用有序集合 使用有序集合(如 std::list、std::vector 或其他有序容器)来存储和管理子部件。这种方法可以确保子部件按照特定顺序排列&am…...
duxapp RN 端使用AppUpgrade 进行版本更新
版本更新包含了组件和工具的组合 注册 下面这是 duxcms 入口文件检查更新的注册方法,注册的同时会检查更新 import {request,updateApp,userConfig } from ./utils// 检查app更新 setTimeout(async () > {if (process.env.TARO_ENV rn) {// eslint-disable-n…...

【计网】自定义序列化反序列化(三) —— 实现网络版计算器【下】
🌎实现网络版计算器【下】 本次序列化与反序列化所用到的代码,Tcp服务自定义序列化反序列化实现网络版计算器。 文章目录: 实实现网络版计算器【下】 客户端实现 基于守护进程的改写 🚀客户端实现 在这之前,…...
神经网络中的优化方法(一)
目录 摘要Abstract1. 与纯优化的区别1.1 经验风险最小化1.2 代理损失函数1.3 批量算法和小批量算法 2. 神经网络中优化的挑战2.1 病态2.2 局部极小值2.3 高原、鞍点和其他平坦区域2.4 悬崖和梯度爆炸2.5 长期依赖2.6 非精确梯度2.7 局部和全局结构间的弱对应 3. 基本算法3.1 随…...

Linux 计算机网络基础概念
目录 0.前言 1.计算机网络背景 1.1 独立模式 1.2 网络互联 1.3 局域网(Local Area Network,LAN) 1.4 广域网(Wide Area Network,WAN) 2.协议 2.1什么是协议 2.2协议分层和软件分层 2.3 OSI七层网络模型 2.3…...

qt QGraphicsEllipseItem详解
1、概述 QGraphicsEllipseItem是Qt框架中QGraphicsItem的一个子类,它提供了一个可以添加到QGraphicsScene中的椭圆项。QGraphicsEllipseItem表示一个带有填充和轮廓的椭圆,也可以用于表示椭圆段(通过startAngle()和spanAngle()方法ÿ…...
Python websocket
router.websocket(/chat/{flow_id}) 接口代码,并了解其工作流程、涉及的组件以及如何基于此实现你的新 WebSocket 接口。以下内容将分为几个部分进行讲解: 接口整体概述代码逐行解析关键组件和依赖关系如何基于此实现新功能示例:创建一个新的…...

【MySQL-5】MySQL的内置函数
目录 1. 整体学习的思维导图 2. 日期函数 编辑 2.1 current_date() 2.2 current_time() 2.3 current_timestamp() 2.4 date(datetime) 2.5 now() 2.6 date_add() 2.7 date_sub() 2.8 datediff() 2.9 案例 2.9.1 创建一个出生日期登记簿 2.9.2 创建一个留言版 3…...

深度学习笔记之BERT(三)RoBERTa
深度学习笔记之RoBERTa 引言回顾:BERT的预训练策略RoBERTa训练过程分析静态掩码与动态掩码的比较模型输入模式与下一句预测使用大批量进行训练使用Byte-pair Encoding作为子词词元化算法更大的数据集和更多的训练步骤 RoBERTa配置 引言 本节将介绍一种基于 BERT \t…...
C++知识点总结(59):背包型动态规划
背包型动态规划 一、背包 dp1. 01 背包(限量)2. 完全背包(不限量)3. 口诀 二、例题1. 和是质数的子集数2. 黄金的太阳3. 负数子集和4. NASA的⻝物计划 一、背包 dp 1. 01 背包(限量) 假如有这几个物品&am…...

C++:反向迭代器的实现
反向迭代器的实现与 stack 、queue 相似,是通过适配器模式实现的。通过传入不同类型的迭代器来实现其反向迭代器。 正向迭代器中,begin() 指向第一个位置,end() 指向最后一个位置的下一个位置。 代码实现: template<class I…...
webGL入门教程_04vec3、vec4 和齐次坐标总结
vec3、vec4 和齐次坐标总结 1. vec3 和 vec4 1.1 什么是 vec3 和 vec4? vec3: GLSL 中的三维向量类型,包含 3 个浮点数:(x, y, z)。常用于表示三维坐标、RGB 颜色、法线、方向等。 vec4: GLSL 中的四维向量类型&…...

uniapp中父组件数组更新后与页面渲染数组不一致实战记录
简单描述一下业务场景方便理解: 商品设置功能,支持添加多组商品(点击添加按钮进行增加).可以对任意商品进行删除(点击减少按钮对选中的商品设置进行删除). 问题: 正常添加操作后,对已添加的任意商品删除后,控制台打印数组正常.但是与页面显示不一致.已上图为例,选中尾…...
优化 Conda 下载速度:详细的代理配置和网络管理策略
优化 Conda 下载速度:详细的代理配置和网络管理策略 为了彻底解决使用 Conda 下载 PyTorch 时遇到的速度问题,并确保下载过程稳定可靠,这需要一个详细、综合的技术方案。让我们更深入地分析问题原因,然后详尽地解释采取的解决策略…...

服务器遭受DDoS攻击后如何恢复运行?
当服务器遭受 DDoS(分布式拒绝服务)攻击 后,恢复运行需要快速采取应急措施来缓解攻击影响,并在恢复后加强防护以减少未来攻击的风险。以下是详细的分步指南: 一、应急处理步骤 1. 确认服务器是否正在遭受 DDoS 攻击 …...

MFC音视频播放器-支持电子放大等功能
前言 本播放器在VS2019下开发,使用ffmpegD3D实现视频播放渲染功能。同时本播放器支持录像功能、截图功能、音视频播放功能、码流信息显示、电子放大功能等。D3D的渲染同时支持surface和texture两种方式,电子放大功能是在D3D Texture方式下进行实现。以下…...
c语言编程1.17蓝桥杯历届试题-回文数字
题目描述 观察数字:12321,123321 都有一个共同的特征,无论从左到右读还是从右向左读,都是相同的。这样的数字叫做:回文数字。 本题要求你找到一些5位或6位的十进制数字。满足如下要求: 该数字的各个数位之…...
el-table 纵向 横向 多级表头
<el-table :data"tableData" class"diaTable":span-method"handleSpanMethod"border:header-cell-style"{background:#292929,color:#fff}"><!-- 纵向表头 --><el-table-column label"纵向表头" width"…...

uniapp开发微信小程序笔记8-uniapp使用vant框架
前言:其实用uni-app开发微信小程序的首选不应该是vant,因为vant没有专门给uni-app设置专栏,可以看到目前Vant 官方提供了 Vue 2 版本、Vue 3 版本和微信小程序版本,并由社区团队维护 React 版本和支付宝小程序版本。 但是vant的优…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...

android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...