【高阶数据结构】二叉搜索树

Ne0inhk

— 17 min read
【高阶数据结构】二叉搜索树

二叉搜索树

1.二叉搜索树的概念

二叉搜索树又称搜索二叉树，它或者是一棵空树，或者是具有以下性质的⼆叉树：

若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。它的左右子树也分别为⼆叉搜索树。

⼆叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，map/set/multimap/multiset 系列容器底层就是⼆叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。

在这里插入图片描述

2.二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全⼆叉树），其高度为：O(logN)最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：O(N)所以综合而言二叉搜索树增删查改时间复杂度为：O(N)
在这里插入图片描述

那么这样的效率显然是无法满足我们需求的，所以有了⼆叉搜索树的变形，平衡⼆叉搜索树。

平衡⼆叉搜索树：AVL树和红黑树平衡多叉搜索树：B树系列（B+树…）

它们适用于我们在内存中存储和搜索数据，另外需要说明的是，⼆分查找也可以实现O(logN) 级别的查找效率，但是⼆分查找有两大缺陷：

需要存储在支持下标随机访问的结构中，并且有序。插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

这里也就体现出了平衡⼆叉搜索树的价值。

3.二叉搜索树的实现

1.二叉搜索树的结构

  1. 准备树的节点（存放两个自己类型的指针找到左右孩子 + 保存某个类型的数据）
  2. 准备二叉搜索树：存放根节点。
  3. 这里实现的是不能含有重复的数据。
namespace xzy {template<classK>structBSNode{ BSNode<K>* _left; BSNode<K>* _right; K _key;BSNode(const K& key =K()):_left(nullptr),_right(nullptr),_key(key){}};template<classK>classBSTree{public://以下两种功能一样：都是取别名//typedef BSNode<K> Node;using Node = BSNode<K>;private: Node* _root =nullptr;//给出缺省值};}

2.二叉搜索树的插入

插入的具体过程如下：

树为空：则直接新增结点，赋值给root指针。树不空：按⼆叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑⼀致性，插入相等的值不要一会往右走，一会往左走）
在这里插入图片描述
在这里插入图片描述
//迭代boolInsert(const K& key){//若树为空：将要插入的节点赋值给根节点if(_root ==nullptr){ _root =newNode(key);returntrue;}//若树不为空：查找要插入的位置 + 它的父亲节点 Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{returnfalse;//相等，则无法插入}}//找到了要插入的位置 + 它的父亲节点, 然后判断插入的位置 Node* newnode =newNode(key);if(parent->_key > key){ parent->_left = newnode;}elseif(parent->_key < key){ parent->_right = newnode;}returntrue;}//递归public:voidInsert(const K& key){ _root =_Insert(_root, key);}private: Node*_Insert(Node* root,const K& key){if(root ==nullptr)returnnewNode(key);if(root->_key < key) root->_right =_Insert(root->_right, key);elseif(root->_key > key) root->_left =_Insert(root->_left, key);return root;}

3.二叉搜索树的查找

从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。最多查找高度次，走到到空，还没找到，这个值不存在。如果不支持插入相等的值，找到x即可返回。如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回。
在这里插入图片描述
//循环boolFind(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{returntrue;//找到了}}returnfalse;//未找到}
//递归public:boolFind(const K& key){return_Find(_root, key);}private:bool_Find(Node* _root,const K& key){if(_root ==nullptr)returnfalse;bool ret1 =false;bool ret2 =false;if(_root->_key == key){returntrue;}elseif(_root->_key < key){ ret1 =Find(_root->_right, key);}else{ ret2 =Find(_root->_left, key);}return ret1 || ret2;}

4.二叉搜索树的删除

首先查找元素是否在⼆叉搜索树中，如果不存在，则返回false。如果查找元素存在则分以下四种情况分别处理：

要删除结点N左右孩子均为空。要删除的结点N左孩子为空，右孩子结点不为空。要删除的结点N右孩子为空，左孩子结点不为空。要删除的结点N左右孩子结点均不为空。

对应以上四种情况的解决方案：

  1. 把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成情况2或者情况3处理，效果是一样的）
在这里插入图片描述
  1. 把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点。
在这里插入图片描述
  1. 把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点。
在这里插入图片描述
  1. 无法直接删除N结点，因为N的两个孩子无处安放，可以用替换法删除。找N左子树的值最大结点R（最右节点）或者N右子树的值最小结点R（最左节点）替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点又符合情况2或情况3，可以直接删除。
在这里插入图片描述
boolErase(const K& key){ Node* parent =nullptr; Node* cur = _root;//找要删除的节点while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{//找到了，开始删除操作：删除cur，cur的父亲节点是parent//1.删除节点的左孩子为空if(cur->_left ==nullptr){if(cur == _root){ _root = cur->_right;}else{if(parent->_left == cur){ parent->_left = cur->_right;}else{ parent->_right = cur->_right;}}delete cur;}//2.删除节点的右孩子为空elseif(cur->_right ==nullptr){if(cur == _root){ _root = cur->_left;}else{if(parent->_left == cur){ parent->_left = cur->_left;}else{ parent->_right = cur->_left;}}delete cur;}//3.删除节点的左孩子和右孩子都为空else{//用要删除节点的左子树中最大值的节点替换要删除的节点（值覆盖）//当然也可以使用右子树中最小值的节点 Node* replace = cur->_left; Node* replaceParent = cur;while(replace->_right){ replaceParent = replace; replace = replace->_right;} cur->_key = replace->_key;//值覆盖//要删除的replace节点的孩子最多只有一个，复用情况1/2if(replaceParent->_left == replace){ replaceParent->_left = replace->_left;}else{ replaceParent->_right = replace->_left;}delete replace;}returntrue;}}returnfalse;//没有要删除的数据}

5.二叉搜索树的中序遍历

  1. 由于二叉搜索树的性质，左子树小于根，根又小于右子树，那么它的中序遍历就可以得到一个有序的数据
  2. 但是由于要传入根节点，而外面是访问不到根节点的，可以封装另一个接口，如下：
public:voidInOrder(){_InOrder(_root); cout << endl;}private:void_InOrder(Node* _root){if(_root ==nullptr)return;_InOrder(_root->_left); cout << _root->_key <<" ";_InOrder(_root->_right);}
intmain(){ vector<int> v ={8,3,1,10,6,4,7,14,13}; xzy::BSTree<int> t;for(auto& e : v){ t.Insert(e);} t.InOrder();//输出: 1 3 4 6 7 8 10 13 14return0;}

6.默认构造

//强制生成默认构造BSTree()=default;

7.拷贝构造

前序遍历构造二叉搜索树

public:BSTree(const BSTree& t){ _root =Copy(t._root);}private: Node*Copy(Node* root){if(root ==nullptr)returnnullptr; Node* newRoot =newNode(root->_key); newRoot->_left =Copy(root->_left); newRoot->_right =Copy(root->_right);return newRoot;}

8.赋值重载

现代写法：利用传值传参+拷贝构造

BSTree&operator=(BSTree tmp){swap(_root, tmp._root);return*this;}

9.析构函数

后序遍历析构二叉搜索树

public:~BSTree(){Destory(_root);}private:voidDestory(Node* _root){if(_root ==nullptr)return;Destory(_root->_left);Destory(_root->_right);delete _root;}

4.二叉搜索树key和key/value使用场景

1.key搜索场景（set容器）

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。

场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在⼆叉搜索树中，不在则波浪线标红提示。

在这里插入图片描述

2.key/value搜索场景（map容器）

每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中（结点）除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树结构了，可以修改value。

场景1：简单中英互译字典，树的结构中（结点）存储key（英文）和vlaue（中文），搜索时输入英文，则同时查找到了英文对应的中文。

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。

场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现（单词，1），单词存在，则++单词对应的次数。

在这里插入图片描述

5.key二叉搜索树代码

namespace key {template<classK>structBSNode{ BSNode<K>* _left; BSNode<K>* _right; K _key;BSNode(const K& key =K()):_left(nullptr),_right(nullptr),_key(key){}};template<classK>classBSTree{public://以下两种功能一样：都是取别名//typedef BSNode<K> Node;using Node = BSNode<K>;boolInsert(const K& key){//若树为空：将要插入的节点赋值给根节点if(_root ==nullptr){ _root =newNode(key);returntrue;}//若树不为空：查找要插入的位置 + 它的父亲节点 Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{returnfalse;//相等，则无法插入}}//找到了要插入的位置 + 它的父亲节点; 然后判断左右孩子 Node* newnode =newNode(key);if(parent->_key > key){ parent->_left = newnode;}elseif(parent->_key < key){ parent->_right = newnode;}returntrue;}boolFind(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{returntrue;}}returnfalse;}boolErase(const K& key){ Node* parent =nullptr; Node* cur = _root;//找要删除的节点while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{//找到了，开始删除操作：删除cur，cur的父亲节点是parent//1.删除节点的左孩子为空if(cur->_left ==nullptr){if(cur == _root){ _root = cur->_right;}else{if(parent->_left == cur){ parent->_left = cur->_right;}else{ parent->_right = cur->_right;}}delete cur;}//2.删除节点的右孩子为空elseif(cur->_right ==nullptr){if(cur == _root){ _root = cur->_left;}else{if(parent->_left == cur){ parent->_left = cur->_left;}else{ parent->_right = cur->_left;}}delete cur;}//3.删除节点的左孩子和右孩子都为空else{//用要删除节点的左子树中最大值的节点替换要删除的节点（值覆盖）//当然也可以使用右子树中最小值的节点 Node* replace = cur->_left; Node* replaceParent = cur;while(replace->_right){ replaceParent = replace; replace = replace->_right;} cur->_key = replace->_key;//值覆盖//要删除的replace节点的孩子最多只有一个，复用情况1/2if(replaceParent->_left == replace){ replaceParent->_left = replace->_left;}else{ replaceParent->_right = replace->_left;}delete replace;}returntrue;}}returnfalse;//没有要删除的数据}voidInOrder(){_InOrder(_root); cout << endl;}private:void_InOrder(Node* _root){if(_root ==nullptr)return;_InOrder(_root->_left); cout << _root->_key <<" ";_InOrder(_root->_right);}private: Node* _root =nullptr;};}intmain(){ vector<int> v ={8,3,1,10,6,4,7,14,13}; key::BSTree<int> t;for(auto& e : v){ t.Insert(e);}for(auto& e : v){ t.Erase(e); t.InOrder();}return0;}

6.key/value二叉搜索树代码

namespace key_value {template<classK,classV>structBSNode{ BSNode<K, V>* _left; BSNode<K, V>* _right; K _key; V _value;BSNode(const K& key =K(),const V& value =V()):_left(nullptr),_right(nullptr),_key(key),_value(value){}};template<classK,classV>classBSTree{public://以下两种功能一样：都是取别名//typedef BSNode<K> Node;using Node = BSNode<K, V>;boolInsert(const K& key,const V& value){//若树为空：将要插入的节点赋值给根节点if(_root ==nullptr){ _root =newNode(key, value);returntrue;}//若树不为空：查找要插入的位置 + 它的父亲节点 Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{returnfalse;//相等，则无法插入}}//找到了要插入的位置 + 它的父亲节点; 然后判断左右孩子 Node* newnode =newNode(key, value);if(parent->_key > key){ parent->_left = newnode;}elseif(parent->_key < key){ parent->_right = newnode;}returntrue;} Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}boolErase(const K& key){ Node* parent =nullptr; Node* cur = _root;//找要删除的节点while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}else{//找到了，开始删除操作：删除cur，cur的父亲节点是parent//1.删除节点的左孩子为空if(cur->_left ==nullptr){if(cur == _root){ _root = cur->_right;}else{if(parent->_left == cur){ parent->_left = cur->_right;}else{ parent->_right = cur->_right;}}delete cur;}//2.删除节点的右孩子为空elseif(cur->_right ==nullptr){if(cur == _root){ _root = cur->_left;}else{if(parent->_left == cur){ parent->_left = cur->_left;}else{ parent->_right = cur->_left;}}delete cur;}//3.删除节点的左孩子和右孩子都为空else{//用要删除节点的左子树中最大值的节点替换要删除的节点（值覆盖） Node* replace = cur->_left; Node* replaceParent = cur;while(replace->_right){ replaceParent = replace; replace = replace->_right;} cur->_key = replace->_key;//值覆盖//要删除的replace节点的孩子最多只有一个，复用情况1/2if(replaceParent->_left == replace){ replaceParent->_left = replace->_left;}else{ replaceParent->_right = replace->_left;}delete replace;}returntrue;}}returnfalse;//没有要删除的数据}voidInOrder(){_InOrder(_root); cout << endl;}private:void_InOrder(Node* _root){if(_root ==nullptr)return;_InOrder(_root->_left); cout << _root->_key <<" "<< _root->_value << endl;_InOrder(_root->_right);}private: Node* _root =nullptr;};}inttest01(){ key_value::BSTree<string, string> dict; dict.Insert("left","左边"); dict.Insert("right","右边"); dict.Insert("insert","插入"); dict.Insert("string","字符串"); string str;while(cin >> str){auto ret = dict.Find(str);if(ret){ cout <<"->"<< ret->_value << endl;}else{ cout <<"无此单词，请重新输入"<< endl;}}return0;}inttest02(){ string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"}; key_value::BSTree<string,int> countTree;for(constauto& str : arr){//先查找水果在不在搜索树中 //1、不在，说明水果第一次出现，则插入<水果, 1> //2、在，则查找到的结点中水果对应的次数++ //BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if(ret ==NULL){ countTree.Insert(str,1);}else{ ret->_value++;}} countTree.InOrder();return0;}

Read more

Java Web从入门到精通：全面探索与实战（二）

Java Web从入门到精通：全面探索与实战（二）

Java Web从入门到精通：全面探索与实战（一）-ZEEKLOG博客    目录 四、Java Web 开发中的数据库操作：以 MySQL 为例 4.1 MySQL 数据库基础操作 4.2 JDBC 技术深度解析 4.3 数据库连接池的应用 五、Java Web 中的会话技术：Cookie 与 Session 5.1 Cookie 详解 5.2 Session 详解 四、Java Web 开发中的数据库操作：以 MySQL 为例 4.1 MySQL 数据库基础操作

By Ne0inhk
【征文计划】玩转 Rokid JSAR：基于 Web 技术栈的 AR 开发环境搭建、核心 API 应用与 3D 时钟等创意项目全流程解析

【征文计划】玩转 Rokid JSAR：基于 Web 技术栈的 AR 开发环境搭建、核心 API 应用与 3D 时钟等创意项目全流程解析

【征文计划】玩转 Rokid JSAR：基于 Web 技术栈的 AR 开发环境搭建、核心 API 应用与 3D 时钟等创意项目全流程解析 前言 随着 AR 技术在消费级场景的普及，开发者对 “低门槛、高兼容” AR 开发工具需求愈发迫切，传统 AR 开发往往依赖专属引擎或复杂语法，导致 Web 开发者难以快速切入，而 Rokid 推出的 JSAR 技术，恰好打破了这一壁垒：以 “可嵌入空间的 Web 运行时” 为核心，让开发者无需学习新的开发范式，仅用 JavaScript/TypeScript 等熟悉的 Web 技术栈，就能快速开发出支持 3D 物体、

By Ne0inhk

从Web到全平台：Capacitor打包工具实战指南

作为前端开发者，你是否曾面临这样的困境：好不容易用React、Vue或Angular开发完Web应用，却被要求适配iOS和Android端？学习原生开发成本太高，找原生团队协作又耗时费力。今天要给大家介绍的Capacitor，正是解决这个痛点的利器——由Ionic团队打造的现代跨平台打包工具，能让Web开发者零原生基础也能构建全平台应用。 一、为什么选Capacitor？先看它的核心优势 在接触具体用法前，我们得先搞清楚：Capacitor凭什么成为Web转原生的优选？对比传统方案，它的优势太明显了： 1. 零框架侵入，适配所有Web项目 不同于某些强绑定框架的工具，Capacitor对前端技术栈完全无要求。不管你是用React写的管理系统、Vue开发的移动端页面，还是原生HTML/CSS/JS写的项目，都能直接接入打包。我曾把一个基于Vue3的官网快速打包成APP，整个过程没改一行业务代码。 2. 现代WebView加持，性能接近原生 Capacitor在iOS端采用WKWebView，Android端使用Chromium WebView，这俩都是各平台性能最优的Web

By Ne0inhk
基于YOLO26/11/v8算法的Web目标检测系统，人脸表情识别系统，Django+Vue3 的前后端分离，实现摄像头实时识别，YOLO26/YOLO11/v8 + LLM大模型智能分析，科研必备

基于YOLO26/11/v8算法的Web目标检测系统，人脸表情识别系统，Django+Vue3 的前后端分离，实现摄像头实时识别，YOLO26/YOLO11/v8 + LLM大模型智能分析，科研必备

✨ 更新日志 * ✔️ 2026/3/3，2.0 版本，前端导航栏改为侧边栏系统，视频流采用websocket框架延迟更低， YOLO26/YOLO11/YOLOv8 视频流更稳定，在之前的系统增加 LLM 大模型智能分析，是科研必备，支持 YOLO26/11/v8 分类模型、目标检测、分割、obb、关键点检测任务，还支持双模型联合检测与识别，如人脸表情识别、人脸识别等一些识别任务需要检测模型与分类模型共同完成，在人脸表情识别中，单独使用检测模型去识别人脸表情也不是不可以，但有一个问题数据集如果全是头部照片的话，当模型预测的照片是全身照片时，模型识别准确率就没有这么高了， 那么这时候可以用检测模型识别人脸，把人脸信息输入到表情分类模型进行分类即可，反正这是一个通用的系统，更换自己模型即可，大家懂得都懂的，更多功能看下文即可。 摘要 在人工智能迈向通用化（AGI）的今天，“视觉感知 + 语言理解”的多模态联合是未来的趋势。单纯的检测画框已经无法满足复杂的业务需求，如何让系统“看懂”

By Ne0inhk