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

🕗 发布于 2024-11-29 01:57 数据结构 开发语言 c++ visualstudio

在这里插入图片描述

文章目录

🧨前言

🧨前言

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

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;//说明没找到。
}

删除操作：

要删除结点N左右孩⼦均为空。即叶子节点，可以直接删除。
要删除的结点N左孩⼦位空，右孩⼦结点不为空。
要删除的结点N右孩⼦位空，左孩⼦结点不为空。
要删除的结点N左右孩⼦结点均不为空。

对应序号的解决策略：

把N结点的⽗亲对应孩⼦指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）。
把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点。
把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点。
⽆法直接删除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;
}
}
//没找到就返回false
return 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;
}
}
//没找到就返回false
return 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;
};
}

原文地址：https://blog.csdn.net/2301_78704584/article/details/143991523

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：前端设置 div 标签内子多个子 div 内容，在一行展示，并且可以字段自动换行
下一篇：ubuntu，rocky的安装和使用远程连接工具连接服务器

Flink 任务启动脚本-V2（包括ck启动）
备注：由于Flink checkpoint 个别情况下，不一定能保证落地的checkpoint文件一定有效，所以需要人工介入支持。本次新增一个不从 ck 启动的选择，默认从最新 ck 启动，用法 s
阅读更多2024-11-29
UML的相关介绍
UML作为一种标准化的建模语言，在软件开发中扮演着重要的角色。通过一套丰富的图表和符号，UML为复杂系统的设计和分析提供了强大的支持。这种通用性和标准化使得UML成为各类软件项目中不可或缺的工具。
阅读更多2024-11-29
23种设计模式-外观(Facade)设计模式
软考中级-软件设计师外观模式
阅读更多2024-11-29
RabbitMQ学习-Four
昨天我们通过Linux命令，创建好了角色，那么我们就可以登录管理端的web页面，然后进行响应的操作；今天来学习一下RabbitMQ的具体的。
阅读更多2024-11-29
ftdi_sio应用学习笔记 5 - SPI
SPI的SCK/MOSI/MISO分别对应（A/B)D0/D1/D2，其他IO作为CS。和I2C一样，最大支持2路MPSSE通道，一路MPSSE最大13路SPI。定义spi设备的信息结构体。
阅读更多2024-11-29
＜＜WTF-Solidity＞＞学习笔记(part 5-8)
尤其是如果返回数据类型是变长的情况下，必须加memory修饰，例如：string, bytes, array和自定义结构。在不同存储类型相互赋值时候，有时会产生独立的副本（修改新变量不会影响原变量），
阅读更多2024-11-29
大数据实战之Zookeeper集群
zookeeper集群部署
阅读更多2024-11-29
word2vec
无监督训练模式 model 可选 'skipgram'(默认) or 'cbow'print(f'donkey的词向量类型是{type(result)}')print(f'donkey的词向量形状是{
阅读更多2024-11-29
vue element-ui的el-image 和 el-table冲突层级冲突问题问题preview-teleported
image-viewer 是否插入至 body 元素上。嵌套的父元素属性会发生修改时应该将此属性设置为。解决代码:preview-teleported。
阅读更多2024-11-29
CTF-RE 从0到N:Chacha20逆向实战 2024 强网杯青少年专项赛 EnterGame WP (END)
化简,因为i + j + a4 等价于 a4[i + j]直接定位到比较函数,在此处动态调试抽取s2的值。建立数组使用插件dump数组备用。无视换位直接动态调试在此句断下。
阅读更多2024-11-29