【数据结构专栏】二叉搜索树(Binary Search Tree)的剖析?

embedded/2024/11/28 18:37:51/

在这里插入图片描述

文章目录

  • 🧨前言
    • 1、二叉搜索树的基本概念?
    • 2、二叉搜索树的节点结构组成?
    • 3、二叉搜索树的插入操作?
    • 4、二叉搜索树的删除操作?
    • 5、二叉搜索树的遍历?
    • 6、二叉搜索树的性能分析?
    • 🎉完整代码如下:

🧨前言

该章节主要就是明确二叉树是什么?二叉树的基本操作等。

1、二叉搜索树的基本概念?

二叉所搜索树:它是一棵有一定规则的二叉树。它的每个节点的都遵循这两个条件:
①左子树不为空的时候,左子树的所有节点的值都小于当前节点的值。
②右子树不为空的时候,右子树的所有节点的值都大于当前节点的值。
③左右子树也必须是二叉搜索树。

二叉搜索树的性质决定了节点之间的连接方式,也就是说它可能会连接长满二叉树,亦可能为完全二叉树,但是在插入的而数据是有序的时候,那连接形式就会成一棵链表,会导致该树的高度非常高,影响操作效率。但是有一种平衡二叉搜索树,比如AVL树或红黑树,可以解决这个问题,但这里先不考虑平衡,先假设是一棵普通的二叉搜索树进行讲述。

2、二叉搜索树的节点结构组成?

⼆叉搜索树中可以⽀持插⼊相等的值,也可以不⽀持插⼊相等的值,具体看使⽤场景定义,map/set/multimap/multiset系列容器底层是⼆叉搜索树,其中map/set不⽀持插⼊相等
值,multimap/multiset⽀持插⼊相等值。
此文章的前提是使用一个普通二叉搜索树来分析,同时不包含重复值的节点
该树的节点组成有:
_key:用于存储数据值的变量。
_left:指向左子树的变量
_right:指向右子树的变量

代码结构如下:

template<class K>
class BSTNode
{
public://构造函数,初始化列表给变量赋值BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
public:K _key;BSTNode<K>* _left;BSTNode<K>* _right;
};

3、二叉搜索树的插入操作?

插入‌:如果树为空,新节点成为根节点;否则,按照二叉搜索树的性质找到插入位置并插入新节点‌。
从根节点开始,比较目标值与当前节点的值:
若目标值较小,则移动到左子树;
若目标值较大,则移动到右子树。
重复上述过程,直到找到一个空位置插入新节点。
代码加注释讲解:

//插入数据函数。
bool Insert(const K& key)
{//首先,为空的时候,直接插入到根节点。if (_root == nullptr){_root = new Node(key);return true;}//根节点不为空的时候,那就先从根节点开始。Node* cur = _root;Node* parent = nullptr;//直到为空就插入while (cur){//若插入的数据值 小于 当前节点的数据值,往左走。if (key < cur->_key){//临时记录当前节点的父节点,不然后面链接不上新节点。parent = cur;cur = cur->_left;}//插入的数据值 大于 当前节点的数据值,往右走。else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//走到此处说明找到一个空位置,跳出循环进行链接。return false;}}//找到cur==nullptr,此时parent节点就是最后一个节点,在插入key时候,//还需要判断一次,看插入的值比父节点值大,那么就当作右孩子,反之就当作左孩子。//由于此时cur是为空的,没必要另开空间来存储新节点,因此就把key放入该节点中cur = new Node(key);if (key < parent->_key){//插入到左边parent->_left = cur;}else{//插入到右边parent->_right = cur;}return true;
}

4、二叉搜索树的删除操作?

在实现二叉搜索树删除的接口的时候先是来说一下查找函数。
二叉搜索树的查找:思路和插入的一样,只是需要比较一下大小。

①通过需要查找的值key和二叉搜索树里面的每个节点的值cur->_key进行比较。查找值key 大于 当前节点值cur->_key,则就往当前节点cur的右子树走。
②查找值key 小于 当前节点值cur->_key,则就往当前节点cur的左子树走。
③找到后就返回当前节点cur

代码如下:

	//查找函数bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){//往左走cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return cur;//在判断是否存在某个值的时候,直接返回true即可。}}return false;//说明没找到。}

删除操作:

  1. 要删除结点N左右孩⼦均为空。即叶子节点,可以直接删除。
  2. 要删除的结点N左孩⼦位空右孩⼦结点不为空
  3. 要删除的结点N右孩⼦位空左孩⼦结点不为空
  4. 要删除的结点N左右孩⼦结点均不为空

对应序号的解决策略:

  1. 把N结点的⽗亲对应孩⼦指针指向空,直接删除N结点(情况1可以当成2或者3处理,效果是⼀样的)。
  2. 把N结点的⽗亲对应孩⼦指针指向N的右孩⼦,直接删除N结点。
  3. 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦,直接删除N结点。
  4. ⽆法直接删除N结点,因为N的两个孩⼦⽆处安放,只能⽤替换法删除。

第4种情况替换如下:
①先找到右子树的最小值节点(或左子树的最大值节点)。
②再用该最小值(或最大值)替换被删除节点的值。
③最后记得删除找到的最小值(或最大值)节点。

	//删除函数bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;//先查找到对应删除的节点while (cur){if (cur->_key < key)//若当前节点的数据小于要比较的数据元素,则向右走{parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//找到节点直接后就可以删除该节点//主要分为四种情况//1、左右都为空;2、左位空,右不为空;3、右位空,左不为空;4、左右都不为空// 左右为空的都可以划分到其中一个为空的情况,因为当左右都为空的时候,//下面检测到左节点为空,则就会进入左为空的程序//左为空if (cur->_left == nullptr){//先判断是否为根节点if (cur == _root){//直接把节点给到根节点_root = cur->_right;}else if (cur == parent->_left)//若是父节点的左孩子为空,则//把cur->_right给到父节点的左孩子{parent->_left = cur->_right;}else//反之就是把父节点的右孩子{parent->_right = cur->_right;}delete cur;}//右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}//左右都不为空else{//替代法Node* replaceParent = cur;//在删除左右都不为空的时候,需要找一个节点的值来替代,可以//是当前节点的右子树的最左节点,也可以是当前节点左子树的最右节点,//下面是用的右子树的最左节点。Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}//此处replace就是右子树的最左孩子节点//把值给到要删除的节点,即替换cur->_key = replace->_key;//此时需要判断replace节点是replaceParent节点的左孩子还是右孩子if (replace == replaceParent->_left){replaceParent->_left = replace->_right;}else{replaceParent->_right = replace->_right;}delete replace;//相当于替换后,就删除替换的那个节点}return true;}}//没找到就返回falsereturn false;}

5、二叉搜索树的遍历?

中序遍历:对于二叉搜索树,中序遍历会按升序输出所有节点的值。
前序遍历、后序遍历:按照特定顺序访问节点,但不保证有序性。

下面把三种遍历方式都写出来:

//中序遍历搜索二叉树
void _InOrder(Node* root)
{if (root == nullptr){return;}//左 根 右_InOrder(root->_left);cout << root->_key<<" ";_InOrder(root->_right);
}void _PrevOrder(Node* root)
{if (root == nullptr){return;}cout << root->_key << " ";_InOrder(root->_left);_InOrder(root->_right);
}void _PostOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);_InOrder(root->_right);	cout << root->_key << " ";
}

运行结果如下:
在这里插入图片描述

6、二叉搜索树的性能分析?

最好和平均情况:树的高度为O(log n),插入、删除和查找操作的时间复杂度为O(log n)

最坏情况:树的高度为O(n),时间复杂度退化为O(n),通常发生在插入有序数据时,树退化为链表

为避免性能下降,通常使用平衡二叉搜索树,如AVL树或红黑树,以保证树的高度始终接近O(log n)。后续文章会讲述。

总结:二叉搜索树是一种高效的数据结构,适用于需要频繁进行插入、删除和查找操作的场景。理解其基本操作和实现细节是掌握更复杂数据结构和算法的基础。在实际应用中,通常需要结合平衡技术来保证性能的稳定性。

🎉完整代码如下:

#pragma once#include<iostream>
using namespace std;namespace N
{//先创建二叉树结构template<class K>class BSTNode{public://构造函数BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}public:K _key;BSTNode<K>* _left;BSTNode<K>* _right;};template<class K>class BSTree{typedef BSTNode<K> Node;public://插入数据函数bool Insert(const K& key){//首先,为空的时候,直接插入到根节点if (_root == nullptr){_root = new Node(key);return true;}//根节点不为空的时候,那就先从根节点开始Node* cur = _root;Node* parent = nullptr;//直到为空就插入while (cur){//若插入的数据小于节点的数据值,往左走if (key < cur->_key){//记录下一节点的父节点parent = cur;cur = cur->_left;}//大于节点的值else if (key > cur->_key){parent = cur;//往右边走cur = cur->_right;}//相等就返回else{return false;}}//找到cur==nullptr,此时parent节点就是最后一个节点,在插入key时候,//还需要判断一次,比父节点值大,就插入到右孩子处,反之就左孩子//由于cur是为空的,因此把key放入该节点中cur = new Node(key);if (key < parent->_key){//插入到左边parent->_left = cur;}else{//插入到右边parent->_right = cur;}return true;}//查找函数bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){//往左走cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;}//删除函数bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;//先查找到对应删除的节点while (cur){if (cur->_key < key)//若当前节点的数据小于要比较的数据元素,则向右走{parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//找到节点直接后就可以删除该节点//主要分为四种情况//1、左右都为空;2、左位空,右不为空;3、右位空,左不为空;4、左右都不为空// 左右为空的都可以划分到其中一个为空的情况,因为当左右都为空的时候,//下面检测到左节点为空,则就会进入左为空的程序//左为空if (cur->_left == nullptr){//先判断是否为根节点if (cur == _root){//直接把节点给到根节点_root = cur->_right;}else if (cur == parent->_left)//若是父节点的左孩子为空,//则把cur->_right给到父节点的左孩子{parent->_left = cur->_right;}else//反之就是把父节点的右孩子{parent->_right = cur->_right;}delete cur;}//右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}//左右都不为空else{//替代法Node* replaceParent = cur;//在删除左右都不为空的时候,需要找一个节点的值来替代,//可以是当前节点的右子树的最左节点Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}//此处replace就是右子树的最左孩子节点//把值给到要删除的节点,即替换cur->_key = replace->_key;//此时需要判断replace节点是replaceParent节点的左孩子还是右孩子if (replace == replaceParent->_left){replaceParent->_left = replace->_right;}else{replaceParent->_right = replace->_right;}delete replace;//相当于替换后,就删除替换的那个节点}return true;}}//没找到就返回falsereturn false;}void InOrder(){_InOrder(_root);}void PrevOrder(){_PrevOrder(_root);}void PostOrder(){_PostOrder(_root);}private://中序遍历搜索二叉树void _InOrder(Node* root){if (root == nullptr){return;}//左 根 右_InOrder(root->_left);cout << root->_key<<" ";_InOrder(root->_right);}void _PrevOrder(Node* root){if (root == nullptr){return;}cout << root->_key << " ";_InOrder(root->_left);_InOrder(root->_right);}void _PostOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);_InOrder(root->_right);	cout << root->_key << " ";}private://BSTNode<K>* _root=nullptr;//定义根节点Node* _root = nullptr;};
}

http://www.ppmy.cn/embedded/141237.html

相关文章

BERT简单理解;双向编码器优势

目录 BERT简单理解 一、BERT模型简单理解 二、BERT模型使用举例 三、BERT模型的优势 双向编码器优势 BERT简单理解 (Bidirectional Encoder Representations from Transformers)模型是一种预训练的自然语言处理(NLP)模型,由Google于2018年推出。以下是对BERT模型的简…

matlab代码--卷积神经网络的手写数字识别

1.cnn介绍 卷积神经网络&#xff08;Convolutional Neural Network, CNN&#xff09;是一种深度学习的算法&#xff0c;在图像和视频识别、图像分类、自然语言处理等领域有着广泛的应用。CNN的基本结构包括输入层、卷积层、池化层&#xff08;Pooling Layer&#xff09;、全连…

P1198 [JSOI2008] 最大数

P1198 [JSOI2008] 最大数https://www.luogu.com.cn/problem/P1198 牵制芝士&#xff1a;单调队列 思路&#xff1a; 我们的任务是找出一个区间最大值的 因为插入的数与上一次的答案有关 所以它是强制在线的&#xff08;真无语了&#xff09; 我们可以在每次插入时整一个叫…

Android 14之HIDL转AIDL通信

Android 14之HIDL转AIDL通信 1、interface接口1.1 接口变更1.2 生成hidl2aidl工具1.3 执行hidl2aidl指令1.4 修改aidl的Android.bp文件1.5 创建路径1.6 拷贝生成的aidl到1和current1.7 更新与冻结版本1.8 编译模块接口 2、服务端代码适配hal代码修改2.1 修改Android.bp的hidl依…

全渠道供应链变革下“小程序 AI 智能名片 S2B2C 商城系统”的赋能与突破

摘要&#xff1a;本文围绕全渠道供应链构建这一核心主题&#xff0c;剖析零售企业面临的挑战与机遇&#xff0c;着重探讨在整合采购、营销、仓储、物流等多环节进程中&#xff0c;物流环节整合困境及全渠道模式应对策略。深入研究“小程序 AI 智能名片 S2B2C 商城系统”如何契合…

Java入门:17.正则表达式,String的intern方法,StringBuilder可变字符串特点与应用,+连接字符串特点--001

1 String中的常用方法2 1.1 split方法 将字符串按照指定的内容进行分割&#xff0c;将分割成的每一个子部分组成一个数组 分割内容不会出现在数组中 实际上该方法不是按照指定的简单的符号进行分割的&#xff0c;而是按照正则表达式进行分割 1.2 正则表达式 用简单的符号组…

[高阶数据结构四] 初始图论

1.前言 本篇着重讲解图的相关知识&#xff0c;大家跟随我的脚步往下阅读。 本章重点&#xff1a; 本章着重讲解图的基本知识&#xff0c;图的存储结构&#xff1a;邻接矩阵&#xff0c;邻接表以及图的模拟实现 2.图的基本概念 图是由顶点集合及顶点间的关系组成的一种数据结构…

Tri Mode Ethernet MAC IP核详解

本文对 Vivado 的三速 MAC IP 核&#xff08;Tri Mode Ethernet MAC&#xff0c;TEMAC&#xff09;进行介绍。 在自行实现三速以太网 MAC 控制器时&#xff0c;GMII/RGMII 接口可以通过 IDDR、ODDR 原语实现&#xff0c;然而实际使用中自己实现的模块性能不是很稳定&#xff08…