C++二叉搜索树学习

news/2024/10/9 12:00:05/

目录

一、二叉搜索树概念

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

三、二叉搜索树的构建


一、二叉搜索树概念

二叉搜索树又叫做二叉排序树,它可以是一颗空树,或者是具有以下性质的二叉树:

  • 若该树的左子树不为空,那么左子树上的任一节点都小于等于根节点的值。
  • 若该树的右子树不为空,那么右子树上的任一节点都大于等于根节点的值。
  • 该树的左右子树也为二叉搜索树。
  • 二叉搜索树可以支持插入相等的值,也可以不支持插入相等的值。

如上图,为一个基本的二叉搜索树。本文将以不插入相等的值的二叉搜索树为例。

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

最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其高度为(log2 N),例如上方的二叉搜索树。

最差情况下,二叉搜索树退化为单支树(或者类似单支),其高度为(N/2 ~ N),例如:

综上所述,二叉搜索树的增删查改的时间复杂度为:O(N)。

三、二叉搜索树的构建

1. 基本框架

template<class K>
struct BSNode
{BSNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSNode<K>* _left;BSNode<K>* _right;
};template<class K>
class BSTree
{
public:using Node = BSNode<K>;
private:Node* _root = nullptr;int _num = 0;
};

我们以BSNode类,来构建二叉搜索树的每一个节点,这个节点有指向左右子树的指针_left和_right,并且每个节点都有一个值被_key所存储。

然后在BSTree类,是我们二叉搜索树的大框架,里面有着根节点_root,并且有着节点的数量_num。

2. 二叉搜索树的插入

bool _Insert(const K& key)
{Node* newnode = new Node(key);if (_root == nullptr){_root = newnode;_num++;return true;}else{Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}elsereturn false;}if (key < parent->_key){_num++;parent->_left = newnode;}if (key > parent->_key){_num++;parent->_right = newnode;}return true;}return false;
}

二叉搜索树的插入还是比较简单的,首先,我们要以传入的key值创建一个newnode的节点,如果根节点为空,那么直接把newnode给根节点,然后返回即可。

因为二叉搜索树的特殊性,所有左子树节点的值小于根节点,所有右子树节点的值大于根节点。因此当我们插入一个值(cur)时,首先要对到达的节点的值比较,如果跟该节点的值相等,因为我们讨论的是不支持有重复的值,返回false即可。

如果key小于该节点的值,那么我们就向该节点的左子树走,反之向该节点的右子树走,cur走到空,说明此处就是我们要插入的地方。因为我们提前已经创建parent指针来记录cur的父亲,所以此时我们只需要比较key的值和parent的值,然后决定插入在parent的左子树还是右子树即可。

3. 二叉树的查找

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

查找还是比较简单的,首先根节点不能为空,否则查找无意义。然后我们就和插入一样,从根节点开始,将我们要查找的key值与此时节点的值比较,key小就向节点的左子树走,key大就向节点的右子树走,若相等就返回true即找到了。如果cur都走到空了,那么就返回false即树中没有key值。

4. 二叉树的删除

二叉树的删除还是比较麻烦的,要分为以下四种情况:

  1. 该节点的左右子树均为空。
  2. 该节点的左子树为空,右子树不为空。
  3. 该节点的右子树为空,左子树不为空。
  4. 该节点的左右子树军不为空。
Node* cur = _root;
Node* parent = cur;
while (cur != nullptr && cur->_key != key)
{if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}	
}
//先找到要删除的cur节点,并记录该节点的父节点。

对于情况1,比较好处理,因为我们完全可以找到该节点,并记录该节点的父节点,然后直接删除该节点并且让父节点的对应指针指向空即可。

if (cur->_left == nullptr && cur->_right == nullptr)
{if (cur->_key < parent->_key)parent->_left = nullptr;elseparent->_right = nullptr;delete cur;_num--;return true;
}

对于情况2,3我们可以同样地处理,以2为例。如果该节点的左子树为空,那么我们找到该节点后,并且记录了父节点,直接将父节点指向该节点的指针,指向该节点的右子树,然后直接删除该节点即可。情况3相同,只是注意左右子树不同。

else if(cur->_left == nullptr)
{Node* r_parent = cur;Node* r_root = cur->_right;while (r_root->_left){r_parent = r_root;r_root = r_root->_left;}if (r_parent->_key > r_root->_key)r_parent->_left = r_root->_right;else if (r_parent->_key < r_root->_key)r_parent->_right = r_root->_right;cur->_key = r_root->_key;delete r_root;_num--;return true;
}
else if (cur->_right == nullptr)
{Node* l_parent = cur;Node* l_root = cur->_left;while (l_root->_right){l_parent = l_root;l_root = l_root->_right;}if (l_parent->_key > l_root->_key)l_parent->_left = l_root->_left;else if (l_parent->_key < l_root->_key)l_parent->_right = l_root->_left;cur->_key = l_root->_key;delete l_root;_num--;return true;
}

对于情况4,我们不能直接删除该节点,因为该节点左右子树均不为空。我们此时就可以使用替换法。找到该节点(N)左子树的最大节点(L)或者右子树的最小节点(R)来替换该节点的值,因为这两个节点中的任意一个,放到N的位置,都不会破坏整个二叉搜索树的性质,然后我们删除交换后废弃的节点即可。例如:

我们要删除3这个节点,3的左子树根节点为1,右子树根节点为6,那么左子树最大的值为2,右子树最小的值为4,所以我们将2/4与3交换后不会改变整个二叉搜索树的性质。我们以交换4为例:

这样就实现了二叉搜索树的删除,也没有破坏本来的性质,注意如果4的右子树还有节点,那么交换后3的右子树就会有节点,那么我们只需要将6的左指针指向3的右子树即可。

else
{/*Node* parent = cur;Node* root = cur->_right;*/Node* r_parent = cur;Node* r_root = cur->_right;while (r_root->_left){r_parent = r_root;r_root = r_root->_left;}if (r_parent->_key > r_root->_key)r_parent->_left = r_root->_right;else if (r_parent->_key < r_root->_key)r_parent->_right = r_root->_right;cur->_key = r_root->_key;delete r_root;_num--;return true;
}

注意,如果一开始根节点本来就为空,那么我们不需要删除,直接返回false即可,如果树只有一个节点,也就是_num为1,我们直接将_root给为nullptr即可:

if (cur == nullptr)
{return false;
}
if (_num == 1)
{_root = nullptr;_num = 0;return true;
}

整个删除的框架如下,最终只需将上述所以删除代码加入即可:

bool _Erase(const K& key)
{Node* cur = _root;Node* parent = cur;while (cur != nullptr && cur->_key != key){//查找要删除的节点位置,并且记录父节点}if (cur == nullptr){return false;//如果树为空或者没找到,直接返回false}if (_num == 1){//只有一个节点情况}if (cur->_left == nullptr && cur->_right == nullptr){//该节点左右子树均为空}else if(cur->_left == nullptr){//该节点左子树为空}else if (cur->_right == nullptr){//该节点右子树为空}else{该节点左右子树均不为空}return false;
}

以上内容如有错误,欢迎批评指正!!!


http://www.ppmy.cn/news/1527060.html

相关文章

MATLAB系列04:循环结构

MATLAB系列04&#xff1a;循环结构 4. 循环结构4.1 while循环4.2 for循环4.2.1 运算的细节4.2.2 break语句和continue语句4.2.3 嵌套循环 4.3 逻辑数组和向量化4.3.1 逻辑数组的重要性4.3.2 用 if/else 结构和逻辑数组创建等式 4.4 总结 4. 循环结构 循环(loop)是一种 MATLAB …

SprinBoot+Vue工商局商家管理系统的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍&#xff1a;CSDN认证博客专家&#xff0c;CSDN平台Java领域优质…

Linux 文件 IO 管理(第一讲)

Linux 文件 IO 管理&#xff08;第一讲&#xff09; 回顾 C 语言文件操作&#xff0c;提炼理解新创建的文件为什么被放在可执行文件的同级目录下&#xff1f;上述 log.txt 何时被创建&#xff1f;又是谁在打开它&#xff1f;那文件没有被打开的时候在哪里&#xff1f;一个进程可…

计算左边(比自己小的元素)的最长距离

前言&#xff1a;一般做的题目都是使用单调栈来求出距离这个点最近的那个比这个数大或小的元素&#xff0c;但是如果是需要找到最远的那个元素呢&#xff1f;我们可以用到类似逆序对的思路&#xff0c;我们先进行排序从小到大&#xff0c;接着我们先处理左边&#xff0c;每次维…

常见的限流算法

限流算法是用于控制访问频率、保护系统免受过载攻击的重要手段。常见的限流算法有以下几种&#xff0c;每种算法都有不同的应用场景和优缺点。下面是几种常见的限流算法的详细介绍&#xff1a; 1. 计数器算法&#xff08;Counter&#xff09; 原理 计数器算法是最简单的限流…

项目实训:CSS基本布局理解——WEB开发系列38

对CSS学习已经接近尾声&#xff0c;下面你可以对以下两道“小卡拉米”测试进行测试下CSS理解程度。 题 1&#xff1a;基于栅格布局的现代博客首页设计 题目要求&#xff1a; 创建一个博客首页布局&#xff0c;包含一个顶部导航栏、一个主要的内容区域&#xff08;左侧为博客文…

深入了解C语言的内核--数据在内存中的存储

前言&#xff1a;新手开始学C语言&#xff0c;首先学习的是语法&#xff0c;在懂语法的基础上&#xff0c;在去思考解决问题的方法。大家应该也听说过c语言是最接近底层的编程语言吧&#xff0c;所以我认为最重要的是要理解C语言的内核--1.栈帧空间的销毁和创建 2.数据在内存中…

golang中连接达梦数据库使用域名来代替IP时会出现解析问题

中间件使用gorm driverName : "dm" dataSourceName : fmt.Sprintf("dm://%s:%s%s:%s/SYSDBA?charsetutf8&parseTimetrue", config.Database.Username, config.Database.Password, config.Database.Address, config.Database.Port)config.Database.Ad…