C++二叉搜索树

🕗 发布于 2024-09-24 11:51 c++ 数据结构

什么是二叉搜索树

二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
• 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
• 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
• 它的左右子树也分别为二叉搜索树
在这里插入图片描述

二叉搜索树中可以⽀持插⼊相等的值，也可以不支持插入相等的值，具体看使用场景定义
总得来说二叉搜索树他的左子树和根还有右子树的值形成一个阶梯状
在这里插入图片描述

二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为： O(log2 N)
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为： O( N/2）

所以综合而言二叉搜索树增删查改时间复杂度为： O(N)
那么这样的效率是无法满足我们在内存中的使用场景的
平衡二叉搜索树AVL树和红黑树才适合我们在内存中的存储
另外需要说明的是，二分查找也可以实现 O(logN) 级别的查找效率，但是二分查找有两中缺陷：
1. 需要存储在支持下标随机访问的结构中，并且有序。
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

这也就体现出了平衡二叉搜索树的价值。相较于普通二叉树而言。

下面我们就来说说二叉搜索树的实现

二叉树的插入

插入的具体过程如下：

树为空，则直接新增结点，赋值给root指针
树不空，按二叉搜索树的性质，和根节点进行比较，比根节点小的往左边插入，比根节点大的往右边插入，找到空节点在插入
如果插入相等的值，即可以往走走也可以往右边走，但是不能一会儿左一会儿右边，要保持一致性

这里我们就设定为不能插入相等的值，这样我们可以保证插入的唯一性

bool insert(const key& input_key)
{

if (_root == nullptr)
{
_root = new node(input_key);
return true;
}
else
{
node* cur = _root;
node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_key < input_key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > input_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
if (parent->_key < input_key)
{
cur = new node(input_key);
parent->_right = cur;
}
else
{
cur = new node(input_key);
parent->_left = cur;
}
return true;
}

这里首先判断根节点有没有数据，如果没有就创建一个根节点，如果有，我们需要两个指针来记录一下插入的位置一个上一个节点（parent）一个当前节点cur，当前cur节点依次和要插入的新节点进行比较，如果大于当前节点往右边反之左边，如果相等就返回假退出程序，为什么需要一个parent节点来记录呢，这是因为，我们cur节点走到空的时候无法知道上一个节点在哪里，就没办法插入新的数据进去，插入的数据找不到位置，所以需要一个parent节点来记录。

二叉搜索树的查找

查找就简单，就是从根节点往下面找，小的往左走，大的往右走

从根开始较，查找x，x比根大的值则往右边查找，x比根小值则往左边查找。
2. 最多查找高度次，走到空，还没找到，这个值不存在。
3. 如果不支持插相等的值，找到x即可返回

bool find(const key& input_key)
{
assert(_root != nullptr);
if (input_key == _root->_key)
{
return true;
}
else
{
node* cur = _root;
while (cur != nullptr)
{
if (cur->_key > input_key)
{
cur = cur->_left;
}
else if (cur->_key < input_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}

二叉搜索树的删除

删除就比较难了，删除要分3中情况，首先要看看要删除的节点在不在二叉树里面然后在判断，一种是当前删除的节点下面没有左右孩子，另一种是要删除的当前节点左边没有孩子，右边有孩子，右边没有孩子，左边有孩子，最后一种是要删除的节点左右两边都有孩子。
对应上面的情况的解决方案

把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是一样的）
把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点（这种情况
这里还需要特殊处理一下root节点）
把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
无法直接删除N结点，因为N的两个孩无处安放，只能用替换法删除。找N左子树的值最大结点
R(最右结点)或者N右子树的值最左结点R(最左结点)替代N，因为这两个结点中任意一个，放到N的位置，都满搜索叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转变成删除R结点，R结点符合情况2或情况3，可以直接删除。

在这里插入图片描述

在这里插入图片描述

下面是代码

bool erase(const key& input_key)
{
node* cur = _root;
node* parent = cur;
while (cur != nullptr)
{
if (cur->_key > input_key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < input_key)
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}
if (cur == nullptr)
{
return false;
}
else
{
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;
}
else if (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;
}
else
{//这里选用的是找右子树的最小节点
node* replace_parent = cur;
node* replace = cur->_right;
//?
while(replace->_left)
{
replace_parent = replace;
replace = replace->_left;
    }
cur->_key = replace->_key;
if (replace_parent->_left == replace)
{
replace_parent->_left = replace->_right;
}
else
{
replace_parent->_right = replace->_right;
}
delete replace;
return true;
} 
}
return false;
}

二叉搜索树的中序遍历

void _InOrder(node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

中序遍历出来的搜索二叉树才是有序的从最小节点开始一直遍历到最大的节点

拷贝构造函数

BinarySearch_(const key& input_key)
{
this->_root = copy(input._root);
}
node* copy(node* input_root)
{
if (input_root == nullptr)
{
return nullptr;
}
node* newnodes = new node(input_root->_key);
copy(input_root->_left);
copy(input_root->_right);
return newnodes;
        }

这里要结合着一起看，copy函数是私有成员函数
首先这里也运用了中序遍历思想，直白来说就是按照着原来的直接根据中序遍历拷贝一份。

析构函数

~BinarySearch_()
{
destory(_root);
_root = nullptr;
}

    void destory(node* input_root)
       {
if (input_root == nullptr)
{
return;
}
destory(input_root->_left);
destory(input_root->_right);
delete input_root;
        }

析构函数也是同理，走的是后序遍历从后往前删除

源码

这里用了一个单独的struct类型来存放节点。

#pragma once
# include<assert.h>
# include<iostream>
using namespace std;
namespace BinarySearch
{
template<class key>
struct BinarySearch_node
{
key _key;
BinarySearch_node<key>* _left;
BinarySearch_node<key>* _right;
BinarySearch_node(const key& input_key)
:_key(input_key)
,_left(nullptr)
,_right(nullptr)
{}
};
template<class key>
class BinarySearch_
{
typedef BinarySearch_node<key> node;
public:
BinarySearch_()
:_root(nullptr)
{}
                 BinarySearch_(const key& input_key)
{
this->_root = copy(input._root);
}
BinarySearch_& operator=(const key& input_key)
{
swap(this->_root, input._root);
return *this;
}

~BinarySearch_()
{
destory(_root);
_root = nullptr;
}
bool insert(const key& input_key)
{

if (_root == nullptr)
{
_root = new node(input_key);
return true;
}
else
{
node* cur = _root;
node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_key < input_key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > input_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
if (parent->_key < input_key)
{
cur = new node(input_key);
parent->_right = cur;
}
else
{
cur = new node(input_key);
parent->_left = cur;
}
return true;
}
}
bool find(const key& input_key)
{
assert(_root != nullptr);
if (input_key == _root->_key)
{
return true;
}
else
{
node* cur = _root;
while (cur != nullptr)
{
if (cur->_key > input_key)
{
cur = cur->_left;
}
else if (cur->_key < input_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
}
bool erase(const key& input_key)
{
node* cur = _root;
node* parent = cur;
while (cur != nullptr)
{
if (cur->_key > input_key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < input_key)
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}
if (cur == nullptr)
{
return false;
}
else
{
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;
}
else if (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;
}
else
{
node* replace_parent = cur;
node* replace = cur->_right;
//?
while(replace->_left)
{
replace_parent = replace;
replace = replace->_left;
    }
cur->_key = replace->_key;
if (replace_parent->_left == replace)
{
replace_parent->_left = replace->_right;
}
else
{
replace_parent->_right = replace->_right;
}
delete replace;
return true;
} 
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

                void destory(node* input_root)
       {
if (input_root == nullptr)
{
return;
}
destory(input_root->_left);
destory(input_root->_right);
delete input_root;
        }
                node* copy(node* input_root)
{
if (input_root == nullptr)
{
return nullptr;
}
node* newnodes = new node(input_root->_key);
copy(input_root->_left);
copy(input_root->_right);
return newnodes;
        }
private:
BinarySearch_node<key>* _root;
};
}

原文地址：https://blog.csdn.net/2302_80245587/article/details/142465670

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

上一篇：LabVIEW界面输入值设为默认值
下一篇：uniapp打包自动上传小程序后台

使用淘宝商品关键词搜索API接口提升销售利润
综上所述，淘宝商品关键词搜索API接口为商家和开发者提供了一个强大的工具，通过合理使用这一接口，商家可以轻松获取丰富的商品信息，提高运营效率，优化用户体验，并最终实现销售利润的提升。：传统的搜索方式需
阅读更多2024-09-24
USB总线同步数据采集卡6路高速模拟量采集带DIO功能USB2884/2885/2886
数据采集卡概述：系统框图：规格参数：板卡外形图：尺寸图及元器件功能说明：
阅读更多2024-09-24
python爬虫/引用requests/基本使用
3.找到该文件一般在第一个的位置，点击查看信息。进入控制台使用该命令安装requests。这里用对网站进行post请求，然后打印。1.访问网站打开发F12这里使用百度演示。这里用对网站进行get请求，
阅读更多2024-09-24
基于双向 LSTM 和 CRF 的序列标注模型
本文介绍了如何使用 Keras 构建一个基于双向 LSTM 和 CRF 的序列标注模型。这种模型结合了双向 LSTM 的上下文建模能力和 CRF 的标签依赖关系考虑，能够在序列标注任务中取得较好的性能
阅读更多2024-09-24
数据结构 - 查找算法
存储记录时，有意的建立key与记录的存储位置之间的关系，以构建哈希表。
阅读更多2024-09-24
蓝牙技术|详谈蓝牙信道探测技术，可实现厘米级精准定位
苹果发布AirTag发布以来，大家都更加注重物品的防丢，苹果的 Find My 就可以查找 iPhone、Mac、AirPods、Apple Watch，如今的Find My已经不单单可以查找苹果的设
阅读更多2024-09-24
JUC并发编程_ReadWriteLock
通过合理地使用读写锁，可以显著提高程序的并发性能和资源的利用率。当没有线程持有写锁时，读锁可以被多个线程同时获取，这提高了并发读取的效率。（Write Lock）：写锁是独占的，当一个线程获得写锁后，
阅读更多2024-09-24
Spring Boot 中实现任务后台处理的几种常见方式
在现代应用程序中，后台处理对于处理发送电子邮件、处理文件、生成报告等任务至关重要。Spring Boot 提供了多种机制来高效地实现后台任务。本文探讨了在 Spring Boot 中处理后台处理的各
阅读更多2024-09-24
时序约束进阶三：Create_clock与Create_Generated_Clock详解
时序约束中，使用Create_clock约束来生成主时钟，主时钟可以说是设计的心脏。主时钟是来自FPGA芯片外部的时钟，通过时钟输入端口或高速收发器GT的输出引脚进入FPGA内部。对于赛灵思7系列的器
阅读更多2024-09-24
ubuntu查看全部的磁盘分区命令
使用以上命令中的任何一个都可以获取完整的磁盘分区信息。这将显示磁盘和分区的层次结构以及文件系统类型。这个命令也可以显示所有分区信息。这将列出所有磁盘及其分区。
阅读更多2024-09-24