二叉搜索树的实现

本文旨在讲解如何编写一颗二叉搜索树,包括基本的增删查改的操作。

目录

一、二叉搜索树的概念

 ​编辑二、二叉搜索树的编写

2.1节点的编写

2.2节点的插入

2.3节点的查找

2.4节点的删除

三、二叉搜索树的应用

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

五、完整代码 


一、二叉搜索树的概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
1.若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树

 二、二叉搜索树的编写

2.1节点的编写

作为一颗树他的节点应该包括储存的内容和找到其他节点的方式,而因为它是一棵二叉树,所以这里我采用左右孩子法去定义它的孩子。

template <class K, class V>
struct BSTreeNode
{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _val;BSTreeNode(const K& key,const V& val)//可能存自定义类型,所以用引用节省空间提升效率:_left(nullptr),_right(nullptr),_key(key),_val(val){}
};

这里我预计储存一个k_val两个类型的数据,但是其实写多少个类型的数据都可以(>=1)。但是要明确的是,只有一个数据参与了对应节点在二叉树中位置相关的代码。

2.2节点的插入

当节点的插入实现后,我们就可以将这颗树建立起来。 根据二叉树的特性,比当前节点小的在左边,大的在右边。

插入的具体过程如下:
a. 树为空,则直接新增节点,赋值给root指针
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

 代码如下

bool Insert(const K& key, const V& val){if (_root == nullptr){_root = new Node(key,val);return true;}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{return false;}} cur = new Node(key,val);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}

2.3节点的查找

这里我希望当节点找到后返回它对应的地址,根据二叉搜索树代码如下:

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

当然我们也可以使用递归的方式来判断一棵树中是否有某个节点

    bool FindR(const K& key){return _FindR(_root, key);}bool _FindR(Node* root,const K& key)//带R表示是递归实现{if (root == nullptr){return false;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key>key){return _FindR(root->_left, key);}else{return true;}}

2.4节点的删除

节点的删除是二叉搜索树最困难的部分。首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况:

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

 看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程 如下

情况 b :删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 -- 直接删除
情况 c :删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 -- 直接删除
情况 d :在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ,用它的值填补到被删除节点
中,再来处理该结点的删除问题 -- 替换法删除

其中替换法删除就是用要删除节点的左边最大的节点或着右边最小的节点的值来替换当前节点,然后情况d就转换成了情况b或c。

此外,我们还应该考虑的时如果要删除的节点时根节点的情况。 

    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 // 找到了{if (cur->_left == nullptr){if (cur == _root)_root = _root->_right;else{if (parent->_right == cur)parent->_right = cur->_right;else parent->_left = cur->_right;}}if (cur->_right == nullptr){if (cur == _root)_root = _root->_left;else{if (parent->_right == cur)parent->_right = cur->_left;else parent->_left = cur->_left;}}else{//找替换节点,左面最大或者右面最小parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}std::swap(cur->_key, leftMax->_key);std::swap(cur->_val, leftMax->_val);if (parent->_left == leftMax)parent->_left = leftMax->_left;else parent->_right= leftMax->_left;}delete cur;return true;}}return false;}

最终我们就将整颗二叉搜索树的基本功能实现了

三、二叉搜索树的应用

1. K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。 比如:给一个单词word,判断该单词是否拼写正确,具体方式如下:
1>以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树
2>在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。
2. KV模型:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见:
比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英
文单词与其对应的中文<word, chinese>就构成一种键值对;
再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出
现次数就是<word, count>就构成一种键值对

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

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数,即结点越深,则比较次数越多。 但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树: 最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:$log_2 N 最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为:N/2问题:如果退化成单支树,二叉搜索树的性能就失去了。那能否进行改进,不论按照什么次序插 入关键码,二叉搜索树的性能都能达到最优?那么我们后续章节学习的AVL树和红黑树就可以上 场了。

五、完整代码 

#pragma once
#include<iostream>
using namespace std;template <class K, class V>
struct BSTreeNode
{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _val;BSTreeNode(const K& key,const V& val)//可能存自定义类型,所以用引用节省空间提升效率:_left(nullptr),_right(nullptr),_key(key),_val(val){}
};
template<class K,class V>
class BSTree
{typedef BSTreeNode<K,V> Node;
public:BSTree():_root(nullptr){}bool Insert(const K& key, const V& val){if (_root == nullptr){_root = new Node(key,val);return true;}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{return false;}} cur = new Node(key,val);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if(key>cur->_key){cur = cur->_right;}else{return cur;}}return nullptr;}bool FindR(const K& key){return _FindR(_root, key);}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 // 找到了{if (cur->_left == nullptr){if (cur == _root)_root = _root->_right;else{if (parent->_right == cur)parent->_right = cur->_right;else parent->_left = cur->_right;}}if (cur->_right == nullptr){if (cur == _root)_root = _root->_left;else{if (parent->_right == cur)parent->_right = cur->_left;else parent->_left = cur->_left;}}else{//找替换节点,左面最大或者右面最小parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}std::swap(cur->_key, leftMax->_key);std::swap(cur->_val, leftMax->_val);if (parent->_left == leftMax)parent->_left = leftMax->_left;else parent->_right= leftMax->_left;}delete cur;return true;}}return false;}void InOrder()//中序遍历{_InOrder(_root);cout << endl;}
private:bool _FindR(Node* root,const K& key)//带R表示是递归实现{if (root == nullptr){return false;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key>key){return _FindR(root->_left, key);}else{return true;}}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << " :"<<root->_val;_InOrder(root->_right);}
private:Node* _root;
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/218732.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

mysql EXPLAIN命令的输出列简介

MySQL :: MySQL 8.2 Reference Manual :: 8.8.2 EXPLAIN Output Format explain命令提供了mysql数据库如何执行SQL语句的信息&#xff0c;可以跟 SELECT, DELETE, INSERT, REPLACE, UPDATE, 和 TABLE一起使用。 explain命令可能输出多行&#xff0c;每行涉及一个表 。 先来看…

Unity升级到2022版本后,打开Spine会卡住

1&#xff09;Unity升级到2022版本后&#xff0c;打开Spine会卡住 2&#xff09;iPhone在同时播放多个音效的时候会压低某些音源的音量 3&#xff09;在Y77手机上出现IMGSRV:GetMainShaderConstantBufferBaseAddress: Unsupported 4&#xff09;UE4打包后在部分安卓机型出现“花…

理解linux中反向映射与应用

反向映射的作用是根据物理页&#xff0c;找到全部相关进程的vma。 主要有两个结构&#xff0c;anon_vma_chain链表&#xff0c;和 anon_vma->rb_root红黑树 打个不恰当的比喻&#xff1a;可以简单认为&#xff0c;红黑树是用来读的&#xff08;遍历找全部映射的vm_area&am…

实战演示 H5 性能分析

W3C标准是浏览器标准&#xff0c;一般浏览器都支持W3C标准&#xff0c;它规定使用者可以通过api查询性能信息&#xff0c;可借用W3C协议完成自动化H5性能测试。 W3C官网&#xff1a;www.w3.org/TR/navigati… 使用chrome浏览器对webview进行手工查看&#xff0c;伴随着业务增多…

Oracle EBS PAC“定期成本分配处理程序”报错:30004不存在为成本类型、成本组和法人主体定义的帐户

Oracle EBS版本&#xff1a; RDBMS : 12.1.0.2.0 Oracle Applications : 12.2.6 问题症状&#xff1a; 中文环境&#xff1a; 30004不存在为成本类型、成本组和法人主体定义的帐户。 CSTPALPC.dyn_proc_call : Error Calling Package 30004不存在为成本类型、成本组和法人主…

Enterprise Portal Standard Edition [WS_ENT_STD]

拾取坐标系统 i18n internationalization-CSDN博客 另外一种网站 Content Management System(CMS)-CSDN博客

智能优化算法应用:基于象群算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于象群算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于象群算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.象群算法4.实验参数设定5.算法结果6.参考文献7.MA…

【Spring Boot】快速入门

一、引言 1、什么是spring boot&#xff1f; Spring Boot是由Pivotal团队提供的全新框架&#xff0c;其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置&#xff0c;从而使开发人员不再需要定义样板化的配置。通过这种方式&#xff…

Qt 文字描边(基础篇)

项目中有时需要文字描边的功能 1.基础的绘制文字 使用drawtext处理 void MainWindow::paintEvent(QPaintEvent *event) {QPainter painter(this);painter.setRenderHint(QPainter::Antialiasing, true);painter.setRenderHint(QPainter::SmoothPixmapTransform, true);painte…

lwIP 细节之六:connected、sent、poll 回调函数是何时调用的

使用 lwIP 协议栈进行 TCP 裸机编程&#xff0c;其本质就是编写协议栈指定的各种回调函数。将你的应用逻辑封装成函数&#xff0c;注册到协议栈&#xff0c;在适当的时候&#xff0c;由协议栈自动调用&#xff0c;所以称为回调。 注&#xff1a;除非特别说明&#xff0c;以下内…

RTMP流设置超时时间失败

使用FFmpeg(版本是5.0.3&#xff09;将rtmp流作为输入&#xff0c;设置超时时间&#xff08;使用-timeout参数&#xff09;&#xff0c;结果报错&#xff1a;Cannot open Connection tcp://XXX:1935?listen&listen_timeout 通过./ffmpeg -help full 命令查看FFmpeg帮助&am…

Flutter工具安装与环境搭建

1、下载 Flutter SDK&#xff0c;下载完成后&#xff0c;在需要放置SDK的地方解压即可。 注意&#xff1a; 请勿将 Flutter 有特殊字符或空格的路径下。请勿将 Flutter 安装在需要高权限的文件夹内&#xff0c;例如 C:\Program Files\。 2、配置环境变量 例如&#xff1a; …

YOLOv8改进 | 2023主干篇 | 替换LSKNet遥感目标检测主干 (附代码+修改教程+结构讲解)

一、本文介绍 本文给大家带来的改进内容是LSKNet&#xff08;Large Kernel Selection, LK Selection&#xff09;&#xff0c;其是一种专为遥感目标检测设计的网络架构&#xff0c;其核心思想是动态调整其大的空间感受野&#xff0c;以更好地捕捉遥感场景中不同对象的范围上下…

[Linux] Apache的配置与运用

一、web虚拟主机的构台服务器上运行多个网站&#xff0c;每个网站实际上并不独立占用整个服务器&#xff0c;因此称为"虚拟"虚拟主机的虚拟主机服务可以让您充分利用服务器的硬件资源&#xff0c;大大降低了建立和运营网站的成本 Httpd服务使构建虚拟主机服务器变得容…

Axure元件基本介绍进阶

Axure元件基本介绍进阶 1.Axure元件基本介绍1.在 Axure 中&#xff0c;元件是构建原型的基本构成单元&#xff0c;能够帮助设计师快速创建、重复使用和管理设计元素。以下是 Axure 中元件的基本介绍&#xff1a;1.基本元件&#xff1a; 2.基本元件的使用一.【举例说明】积木&am…

如何禁止服务器自动休眠

如何禁止服务器自动休眠 有时候服务器自己休眠&#xff0c;导致系统web站点无法访问&#xff0c;下面是解决办法&#xff01; 禁止服务器自动进入休眠状态的具体方法可能会因使用的Linux发行版而有所不同。以下是一些通用的方法&#xff0c;你可以根据你的系统选择适用的&#…

DS考研真题总结——客观题(1)

开始整理真题中的客观小题&#xff0c;至于和算法有关的大题统一最后整理~ 定义背诵&#xff1a;数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下&#xff0c;精心选择的数据结构可以带来更高的运行或者存储效…

深度学习基本概念

1.全连接层 全连接层就是该层的所有节点与输入节点全部相连&#xff0c;如图所 示。假设输入节点为X1&#xff0c; X 2&#xff0c; X 3&#xff0c;输出节点为 Y 1&#xff0c; Y 2&#xff0c; Y 3&#xff0c; Y 4。令 矩阵 W 代表全连接层的权重&#xff0c; W 12也就代表 …

初级数据结构(五)——树和二叉树的概念

文中代码源文件已上传&#xff1a;数据结构源码 <-上一篇 初级数据结构&#xff08;四&#xff09;——队列 | NULL 下一篇-> 1、树结构&#xff08;Tree&#xff09; 1.1、树结构的特点 自然界中的树由根部开始向上生长&#xff0c;随机长出分支&…