数据结构 ----- 二叉搜索树

发布时间:2026/11/19 22:00:23

数据结构 ----- 二叉搜索树 BSTAVL红黑树共性本质都是二叉搜索树都遵守BST规则中序遍历的结果都是升序有序序列节点结构都是二叉树节点数据域左指针右指针基础操作逻辑一致查找插入删除的查找路径一致区别主要在平衡约束强度。普通 BST 不保证平衡AVL 严格平衡查找快但增删旋转多红黑树弱平衡旋转少增删性能更好。AVL 和红黑树是在 BST 基础上增加平衡约束解决普通 BST 最坏退化成链表的缺陷。二叉搜索树BST核心规则左子树所有节点值 根节点值右子树所有节点值 根节点值左、右子树本身也都是 BST三大基础操作1.查找从根开始比较小于根去左子树大于根去右子树相等找到平均O()最坏:O(n)有序插入树退化成一条链表TreeNode* search(TreeNode* root, int key) { if (root nullptr || root-val key)return root; if (key root-val) { return search(root-left, key); } return search(root-right, key); }2.插入与查找的逻辑一致新节点一定是叶子节点TreeNode* insert(TreeNode* root, int val) { if (root nullptr)return new TreeNode(val); if (val root-val) { root-left insert(root-left, val); } else if (val root-val) { root-right insert(root-right, val); } return root; }3.删除删除难点分 3 种情况叶子节点直接删除只有左孩子 / 只有右孩子用子节点替换当前节点左右孩子都存在两种选择取右子树的最小值右子树最左节点替换当前节点再删掉这个最小节点或者取左子树的最大值左子树最右节点替换当前节点再删掉该节点TreeNode* remove(TreeNode* root, int key) { if (root nullptr)return nullptr; if (key root-val) { root-left remove(root-left, key); } else if (key root-val) { root-right remove(root-right, key); } else { if (!root-left) { TreeNode* tmp root-right; delete root; return tmp; } if(!root-right) { TreeNode* tmp root-left; delete root; return tmp; } TreeNode* minParent nullptr; TreeNode* cur getMinAndParent(root-right,minParent); if (minParent nullptr) root-right cur-right; else minParent-left cur-right; cur-left root-left; cur-right root-right; delete root; return cur; } return root; }TreeNode* getMinAndParent(TreeNode* root, TreeNode* parent) { parent nullptr; while (root-left ! nullptr) { parent root; // 记录当前节点作为父 root root-left; } return root; // root停在最左就是最小值节点 }关于情况三关键是要断掉cur与树的联系所以要提前保存cur的父节点以免出现野指针AVL平衡二叉搜索树AVL 树 BST 平衡约束平衡因子 BF 左子树高度 − 右子树高度AVL 强制要求每个节点的平衡因子只能是 -1、0、1如果 (|BF|1) → 树失衡需要旋转修复目的限制树高保证查找 / 插入 / 删除 时间复杂度 O (logn)不会退化成链表普通 BST 最坏 O (n)结点结构struct TreeNode { int val; TreeNode *left; TreeNode *right; int height; // AVL独有记录以当前节点为根的子树高度 TreeNode(int v) : val(v), left(nullptr), right(nullptr), height(1){} };四种失衡情况LL左左右旋在失衡节点的左子树的左孩子处插入左子树过重此时为AVL树插入1根节点平衡因子为2失衡此时应该右旋把失衡节点的左孩子提上来作为新根左孩子原来的右子树变成失衡节点的左子树失衡节点变成其左孩子的右孩子代码:AVLNode* Right_Rotate(AVLNode* node) { AVLNode* child node-leftchild; AVLNode* grandchild child-rightchild; node-leftchild grandchild; child-rightchild node; //更新node和child的高度 Update_Height(node); Update_Height(child); return child;RR右右左旋失衡节点的右孩子 顶替失衡节点的位置右孩子提升为当前子树根失衡节点下沉变成其右孩子的左孩子T2 搬家右孩子原来的左子树 拿出来作为失衡节点的右子树AVLNode* Left_Rotate(AVLNode* node) { AVLNode* child node-rightchild; AVLNode* grandchild child-leftchild; node-rightchild grandchild; child-leftchild node; Update_Height(node); Update_Height(child); return child; }LR左-右左子树的右子树过重先左旋左孩子再右旋失衡点RL右-左右子树的左子树过重先右旋右孩子再左旋失衡点AVLNode* Rotate(AVLNode* node) { int ba Get_BalanceFactor(node); if (ba 2) { int cba Get_BalanceFactor(node-leftchild); if (cba 1) { Right_Rotate(node); }//LL单右旋 if (cba -1) { //先左旋再右旋 node-leftchild Left_Rotate(node-rightchild); } } int ba_right Get_BalanceFactor(node); if(ba_right- 2) { int cba_right Get_BalanceFactor(node-rightchild); if (cba_right-1){ return; }//RR单左旋 if (cba_right 1) { //先右旋再左旋 } } } //判断先左旋还是先右旋关键是看失衡节点左右孩子的平衡因子红黑树红黑树的特点红黑树是自平衡二叉搜索树 BST不是靠高度差约束靠 5 条颜色规则限制最长路径不超过最短路径 2 倍保证查找、插入、删除都是 O(logn)性质每个节点要么红色要么黑色。根节点一定是黑色。所有叶子节点NIL 空哨兵节点不是数据节点是黑色。红色节点的两个子节点一定都是黑色不能有连续红节点红不能连红。从任意一个节点到它所有后代 NIL 叶子的所有路径黑色节点数量相等→ 黑高相同。核心思想不强制左右高度差≤1只限制红节点分布。牺牲一点点查找效率大幅减少旋转次数。AVL 插入最多 2 次旋转红黑树删除最多 3 次旋转插入最多 2 次红黑树的插入插入新节点默认为红色然后向上回溯看是否违反了红连红规则叔叔节点是红色父、叔叔变黑祖父变红继续向上回溯。叔叔黑色LR / LL旋转 变色。叔叔黑色RL / RR旋转 变色
延伸阅读

更多相关文章

2026/11/18 0:18:03

BRD/MRD/PRD 本质是需求穿透三阶漏斗

简介:本资源是一份面向产品经理初学者与进阶从业者的专业文档资料,系统梳理商业需求文档(BRD)、市场需求文档(MRD)和产品需求文档(PRD)的核心定位、适用对象及协同逻辑。重点详解BRD…

2026/11/19 22:00:23

【流匹配模型Flow Maching】流匹配模型入门理解(2)

目录前言1. 模拟数据定义2. 构造训练路径3. 速度预测网络4. 训练5. 从噪声逐步生成6. 相同起点,一步与多步比较前言 之前已经介绍过DDMP以及流模型见如下四篇链接: 【扩散模型DDPM】扩散模型入门理解(1), 【扩散模型DDPM】扩散模…

2026/11/15 19:41:34

细胞衰老的核心密码:NAD+平衡状态决定人体机能的存续时长

细胞衰老的核心密码:NAD平衡状态决定人体机能的存续时长人体的器官衰老、体能衰退、机能下滑,所有老化表现的底层核心密码,都指向同一个物质:NAD。它不是普通的营养物质,是调控细胞代谢、修复、更新、维稳的核心辅酶&a…

2026/11/19 21:59:03

高压电工证新证领证怎么考?工地太忙还能刷考前押题

高压电工证新证领证怎么考?工地太忙还能刷考前押题 工地太忙根本没时间复习考试,这几乎是每个劳务班组负责人的心声。高压电工证新证领证是很多电工朋友的刚需,但考前复习、考试准备、甚至考试内容都让人头疼。别急,本文专门从郑州劳务班组负责人的角度出…

2026/11/19 21:59:03

工地太忙根本没时间复习考试?报低压电工证培训班怎么网上查询

工地太忙根本没时间复习考试?报低压电工证培训班怎么网上查询 工地太忙根本没时间复习考试,很多人想报低压电工证培训班,却不知道从哪开始,怎么查培训信息,甚至担心考试不过怎么办。如果你也正面临这样的情况,这篇内容能帮你理清思路,从…

2026/11/19 21:59:03

电工证国家正规报名入口在哪 手把手教你搞定考前押题

电工证国家正规报名入口在哪 手把手教你搞定考前押题 工地太忙根本没时间复习考试,我理解你,这年头特种作业证考试动不动就压在最后,你白天盯现场,晚上还得熬夜刷题,光是想想就头大。别急,今天我就从 鹤壁项目现场管理员…

2026/11/19 21:59:03

电工证能不能电焊 你上岗必备的真相来了

电工证能不能电焊 你上岗必备的真相来了 实操考试心里没底怕挂科?别慌,咱们今天就来聊聊【电工证能不能电焊】这个大家最关心的问题。特别是像洛阳涧西区市政公用工程这些一线岗位,电工证不仅是上岗必备,更是确保安全作业的“通行证”。很多人误以为电工…

2026/11/19 21:59:03

考电工证课图片到期换证流程

电工证课图片到期换证流程怎么走?外省证怎么转过来 之前考的证在外省能不能转过来?这几乎是所有准备考电工证或者已经在持证的小伙伴最关心的问题之一。如果你拿着的是 电子证书…

2026/11/19 21:54:03

成都市电工证地图继续教育学时要求

成都电工证过期了怎么处理?含金量高的电工证地图全解析 证书过期了不知道怎么复审延期?别急,这事儿真不是小事。电工证在成都这个建筑大市,含金量可是杠杠的,但一旦过期,不仅影响工作,还可能面临法律风险。别再因为不了解流程而耽误了你的职业生涯,下…

2026/11/18 21:12:58

电工证考试口诉怎么准备值不值得考

电工证考试口诉怎么准备值不值得考 实操考试心里没底怕挂科,这是大多数准备考电工证的人心里最真实的感受。尤其是面对【电工证考试口诉】环节,很多人不知道该怎么准备,甚至担心自己说不好就被淘汰。其实,只要掌握方法, 值不值得考…

2026/11/18 21:55:23

桑植县考电工证千万别踩坑!报名全流程教你避坑

桑植县考电工证千万别踩坑!报名全流程教你避坑 你是不是也遇到过这种情况:想考个电工证,但不知道从哪儿下手,怕被中介坑,怕花冤枉钱,更怕考了证还不能用?别急,这正是你该看这篇文章的原因。在桑植县考电工证,确实有很多人被坑过,但只要你知道流程、…

2026/11/19 0:04:42

深圳电工证培训考场模拟考试题库:郑州报考避坑指南

深圳电工证培训考场模拟考试题库:郑州报考避坑指南 证书过期了不知道怎么复审延期,很多人在遇到这个问题的时候才意识到特种作业证的重要性。其实,不管是电工证、焊工证还是高处作业证,这些证书不仅是上岗的“通行证”,更是法律对安全操作的硬性要求。尤…

2026/11/19 0:04:42

天津电工证查询入口多少钱能报上名

天津电工证查询入口多少钱能报上名 学历不高怕报不上名?别急,天津电工证查询入口其实没你想的那么难。今天咱们就来聊聊,怎么用最低的门槛、最少的钱,把电工证拿下来,还能查得到、用得上。 电工证到底值不值?先搞清楚它的作用…

2026/11/18 12:37:05

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

在智慧养宠时代,基于视觉的宠物身份识别技术正逐步从实验室走向家庭应用。然而,与配合度高的人类不同,宠物是典型的“非合作生物识别对象”——它们不会主动配合摄像头调整姿态,更无法控制光照环境。实际应用中,我们常…

2026/11/19 17:18:32

SSM电子书店源码全解析:结构、原理、部署与排错实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑