从零开始的c++之旅——二叉搜索树

🕗 发布于 2024-11-17 11:55 c++

1、二叉搜索树概念

1. ⼆叉搜索树的概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:

• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值

• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值

• 它的左右⼦树也分别为⼆叉搜索树

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

以下就是两颗二叉搜索树

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

最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为：O(log2 N)

最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：O( N/2 )

所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为：O(N)

这样的效率显然是⽆法满⾜我们需求的，后续会讲解⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。

⼆分查找也可以实现O( logN ) 级别的查找效率，但是⼆分查找有两⼤缺陷：

1. 需要存储在⽀持下标随机访问的结构中，并且有序。

2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。

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

3. 二叉搜索树的实现

需要明确的一点是，我们此处实现的是不可插入相同值的二叉搜索树。

而搜索二叉树的本质还是使用递归来完成，因此与我们之前博客实现的二叉树逻辑大体相似，因此一些类似的操作我们简略描述。

3.1 定义二叉搜索树

3.1.2 定义二叉搜索树节点

这与之前实现的二叉树类似，只不过用上了模板跟构造函数，因为构造函数我们在后面需要用来生成节点。

template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;

BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};

3.1.2 定义二叉搜索树结构

template<class K>
class BSTree
{
//这里也能体现封装思想，不管我们如何实现的类此处我们只需定义成Node即可
    typedef BSTNode<K> Node; 

private:
Node* _root = nullptr;//头节点
}

3.2 中序遍历

根据二叉搜索树的性质，中序遍历得到的应该是一个有序的升序列表。

中序搜索的逻辑与之前大差不差，我们只需记住：先遍历左子树，在打印当前根节点的值，而后遍历右子树，这就是“ 左根右”。

不要忘记了返回条件：遍历到空需要返回到上一级。

最后需要注意的一点是，我们遍历时需要传入头节点root，但是root是我们类的私有成员变量，在类外无法访问，那我们怎么办呢？对于这种问题有个统一的办法，我们可以将这个函数定义成类的私有成员，在写一个类的公有成员函数，去调用类的私有成员函数即可。

pubilc：
 void InOder()
{
_InOder(_root);
cout << endl;
}   

private：
    void _InOder(Node* root)
{
if (root == nullptr)
{
return;
}

_InOder(root->_left);
cout << root->_key << " ";
_InOder(root->_right);
}

3.3 插入

我们根据搜索二叉树的特点可以得出我们的插入逻辑：

1.若当前的树是一颗空树，那么我们只需新增节点赋给root节点即可。

2.若树不为空我们只需根据二叉搜索树的性质，定义一个指针cur遍历二叉搜索树，若cur指向的节点值大于我们要插入的值va，则cur往右子树走，反之则往左子树走，知道cur的下一节点为空时，用val初始化一个节点并根据cur和val的值比较，判断插入到左子树还是右子树

bool Insert(const K& val)
{
if (_root == nullptr)
{
_root = new Node(val);
return true;
}

Node* parent = _root;
Node* cur = _root;
while (cur)
{
if ( val < cur->_key )
{
parent = cur;
cur = cur->_left;
}
else if ( val > cur->_key )
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}

cur = new Node(val);
if (val > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left= cur ;
}

return true;
}

3.4 查找

从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。⾛到到空，还没找到，这个值不存在，返回false。找到则返回true。

bool Find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (val > cur->_key)
{
cur = cur->_right;
}
else if (val < cur->_key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}

3.5 删除

二叉搜索树的插入时整个步骤中最复杂的，因为在插入数据时我们需要对二叉搜索树的部分结构进行适当的调整，使其保持原有的性质。

我们以下图的删除二叉数为例

在删除之前，我们还需要明确一点，我们删除节点释放完资源之后，还需使其对应的父亲节点指向nullptr，避免产生野指针的问题，因此我们我们要一个指针cur来搜寻要删除的节点，还需要一个指针parent来记录cur的前一节点。

在删除的过程中，分为了好几种情况。，我们需要分别讨论

1. 删除的位置为叶子节点
这时候只需要cur搜索到对应的节点，再删除即可。

2. 删除的位置只有一个孩子节点。
若cur为parent的左节点，则使 parent->left 指向cur的非空节点
反之则使 parent->right 指向cur的非空节点

3.删除位置有两个孩子节点
这是最后一种也是最复杂的一种情况。有两个孩子意味着删除了该节点后我们需要对搜索二叉树部分结构进行适当的调整。

这里我没有两种方法：我们定义一个指针MaxLeft，使其找到要删除节点cur左子树的最大值，或者定义一个指针MinRight，使其找到cur右子树的最小节点，将其与cur的值进行交换，在删除LeftMax或者MinRight指向的节点即可
为什么可以选择这两个节点的其中一个呢，因为只有选择这两个节点才会保证二叉搜索树的性质不变。
我们以交换右子树最小节点为例，下列图我们可以看出，MidRight指针与cur交换完之后二叉搜索树的性质依然符合。

但是我们还需要注意的是，和前面的两点一样，我们删除掉MidRight节点之后，不要文件将其父节点对应的指针指向nullptr，因此我们还需要定义一个指针PMidRight，防止释放完MidRight之后找不到其对应父节点。

以下是实现的代码

bool Erase(const K& val)
{
if (_root == nullptr)
{
_root = new Node(val);
return true;
}

Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (val < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_left == nullptr)
{
//让父亲指向我的右
if (cur==parent->_right)
{
parent->_right=cur->_right;
}
else
{
parent->_left = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}

delete cur;
return true;
}
else
{
Node* rightMin = cur->_right;
Node* rightMinP = cur;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}

cur->_key = rightMin->_key;

if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;

delete rightMin;
return true;
}
}
}


return false;
}

4.源代码

#pragma once
#include<iostream>
#include<vector>
using namespace std;

template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;

BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};

template<class K>
class BSTree
{
typedef BSTNode<K> Node;

public:
bool Insert(const K& val)
{
if (_root == nullptr)
{
_root = new Node(val);
return true;
}

Node* parent = _root;
Node* cur = _root;
while (cur)
{
if ( val < cur->_key )
{
parent = cur;
cur = cur->_left;
}
else if ( val > cur->_key )
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}

cur = new Node(val);
if (val > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left= cur ;
}

return true;
}

bool Find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (val > cur->_key)
{
cur = cur->_right;
}
else if (val < cur->_key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}

void InOder()
{
_InOder(_root);
cout << endl;
}

bool Erase(const K& val)
{
if (_root == nullptr)
{
_root = new Node(val);
return true;
}

Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (val < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_left == nullptr)
{
//让父亲指向我的右
if (cur==parent->_right)
{
parent->_right=cur->_right;
}
else
{
parent->_left = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}

delete cur;
return true;
}
else
{
Node* rightMin = cur->_right;
Node* rightMinP = cur;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}

cur->_key = rightMin->_key;

if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;

delete rightMin;
return true;
}
}
}


return false;
}

private:
Node* _root = nullptr;

void _InOder(Node* root)
{
if (root == nullptr)
{
return;
}

_InOder(root->_left);
cout << root->_key << " ";
_InOder(root->_right);
}
};

原文地址：https://blog.csdn.net/2302_81813630/article/details/143730612

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

上一篇：1、PyTorch介绍与张量的创建
下一篇：c/c++内存管理

【大数据学习 | flume】flume Sink Processors与拦截器Interceptor
比如：一个日志文件(多个系统的日志都在该文件中)，根据日志中某个字段值，比如type=1，是系统A日志，sink to hdfs；type=2，是系统B日志，sink to kafka，此时就可以使用
阅读更多2024-11-17
5. langgraph中的react agent使用 (从零构建一个react agent)
首先，我们需要定义 Agent 的状态，这包括 Agent 所持有的消息。Annotated,Sequence,TypedDict,我们需要定义工具节点和模型调用节点，以便在 Agent 工作流中使用
阅读更多2024-11-17
37.超级简易的计算器 C语言
超级简单，简单到甚至这个计算器输入都比较反人类。
阅读更多2024-11-17
TCP Analysis Flags 之 TCP Dup ACK
TCP 段大小为 0窗口大小非零且没有改变，或者有有效的 SACK 数据下一个期望的 Seq Num 和 LastACK Num 是非 0 的（即连接已经建立）没有设置 SYN、FIN、RST具体的代
阅读更多2024-11-17
【AI图像生成网站&Golang】雪花算法
使用更精准的时间单位。提供了自定义机器 ID 的能力。支持长时间运行，且避免了时钟回拨问题。改进点Snowflake 的问题Sonyflake 的优化符号位固定占用 1 位，没有实际用途去掉符号位，增
阅读更多2024-11-17
【go从零单排】Directories、Temporary Files and Directories目录和临时目录、临时文件
在 Go 语言中，path/filepath 包提供了一组用于处理文件路径的函数，特别是与文件系统路径相关的操作。这个包是 Go 标准库的一部分，主要用于跨平台的路径操作，确保在不同操作系统上（如 W
阅读更多2024-11-17
菜叶子芯酸笔记4：大模型训练、分布式训练、显存估算
大模型训练任务主要分为以下三种模型训练过程。预训练pretrain监督微调 supervised finetune training奖励模型 reward model。
阅读更多2024-11-17
前端面试笔试（四）
RADIUS是一种分布式的、客户端/服务器结构的信息交互协议，"100"是一个有效的数字，它等于十进制的4。哈希表有10个元素，采用的hash函数为H(key)=key%10，用线
阅读更多2024-11-17
力扣-Hot100-链表其一【算法学习day.34】
##我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！
阅读更多2024-11-17
机器学习实战笔记30-31：逻辑回归及对应调参实验代码
Class_weight:输入{0:1,1:3}则代表1类样本的每条数据在计算损失函数时都会*3，当输入balanced，则调整为真实样本比例的反比，以达到平衡，但实际情况中不常用。#UI多迭代10的
阅读更多2024-11-17