C++:二叉搜索树模拟实现(KV模型)

C++:二叉搜索树模拟实现(KV模型)

  • 前言
  • 模拟实现KV模型
  • 1. 节点封装
  • 2、前置工作(默认构造、拷贝构造、赋值重载、析构函数等)
  • 2. 数据插入(递归和非递归版本)
  • 3、数据删除(递归和非递归版本)
    • 3.1 查找待删除节点位置
    • 3.2 删除数据及相关节点调整
    • 3.3 完整代码以及递归和非递归版本
  • 四、查找数据
  • 五、中序遍历
  • 六、所有代码

前言

 二叉搜索树又称二叉排序树,他对数据有严格的要求,具体表现在以下几个方面:

  1. 如果一个根节点的左子树不为空,则左子树中所有节点的值都必须小于根节点的值;如果它的右子树不为空,则右子树中所有节点的值都必须大于根节点的值。
  2. 它的左右子树也都必须是一个二叉搜索树,也都必须满足第一条。
  3. 二叉搜索树中的每个节点都是唯一的,不允许重复!!!
    在这里插入图片描述

 二叉搜索树的实际应用主要分为K模型和KV模型。

  1. K模型即Key作为关键码,二叉搜索树中只存储Key一个数据。而关键码则是待搜索的值。比如:我们经常通过软件查找是否存在某个单词,是否拼写正确。
  2. KV模型存储的数据中,每个Key对应一个Value,即键值对<Key, Value>。 我们经常通过Key去查找对应的Val.比如:我们通过英文来查找对应的中文,就是一个最常见的KV场景。

模拟实现KV模型

1. 节点封装

由于是KV模型,我们需要存储Key和Value俩个值。同时二叉搜索树也是二叉树,我们需要它的左右节点。因此节点疯转如下:

template<class K, class V>
struct BSTreeNode
{K _key;V _value;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;//默认构造函数, 用于后续new创建节点BSTreeNode(const K& key, const V& value):_key(key), _value(value), _right(nullptr), _left(nullptr){}
};

2、前置工作(默认构造、拷贝构造、赋值重载、析构函数等)

接下来是KV模型封装的框架,以及默认构造、拷贝构造、赋值重载、析构函数。比较简单,就直接给出代码了哈。

template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;//节点重命名public://默认构造BSTree():_root(nullptr){}//拷贝构造BSTree(BSTree<K, V>& t){_root = Copy(t._root);}//赋值重载BSTree<K, V>& operator=(BSTree<K, V> t){swap(_root, t._root);return *this;}//析构函数~BSTree(){Destory(_root);}private:Node* _root = nullptr;};
}

2. 数据插入(递归和非递归版本)

首先我们需要查找数据待插入的位置(为了保证插入数据后整体依然是一颗二叉搜索树).。同时查找插入位置时,只有key是有严格要求的,Value只是附带。
即:如果根节点为空,即是待插入数据位置;否则开始查找,如果待插入数据大于根节点往右子树节点走;如果待插入数据小于根节点往左子树节点走。不断循环,直到查找到空节点时,即为数据待插入的位置;如果查找到的大小和待插入数据值相等则返回false(确保二叉搜索树中的每个节点唯一)

【非递归版本】:

bool Insert(const K& key, const V& value)
{if (_root == nullptr)//根节点为空{_root = new Node(key, value);return true;}Node* cur = _root;Node* parent = nullptr;//后续插入数据链接时,需要和父节点相连while (cur){if (cur->_key > key)//待插入数据小于当前节点,往左子树查找{parent = cur;cur = cur->_left;}else if(cur->_key < key)//待插入数据大于当前节点,往右子树查找{parent = cur;cur = cur->_right;}else//待插入数据等于当前节点,不允许插入{return false;}}//链接Node* newNode = new Node(key, value); //链接时,我们无法确定插入节点时在父节点的左边还是右边,需要进一步比较if (parent->_key > key)parent->_left = newNode;elseparent->_right = newNode;return true;
}

【递归版本】:

bool InsertR(const K& key, const V& value)
{//由于我们查找位置需要从根节点开始查找,所以这里通过另一个函数来传递实现return _InsertR(_root, key, value);
}bool _InsertR(Node*& root, const K& key, const V& value)
{if (root == nullptr){//注意上述我们形参都是引用,所以不用新增Parent节点root = new Node(key, value);return true;}if (root->_key > key)//待插入数据小于当前节点,往左子树查找return _InsertR(root->_left, key, value);else if (root->_key < key)//待插入数据大于当前节点,往右子树查找return _InsertR(root->_right, key, value);elsereturn false;
}

3、数据删除(递归和非递归版本)

3.1 查找待删除节点位置

删除数据,我们首先需要和插入数据一样,先查找到待删除节点。和插入类似就不多说了。

【查找待删除数据】:

bool Erase(const K& key)
{if (_root == nullptr)//为空即不存在待删除数据return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key)//待删除数据小于当前节点,往左子树查找{parent = cur;cur = cur->_left;}else if (cur->_key < key)//待删除数据大于当前节点,往右子树查找{parent = cur;cur = cur->_right;}else{//当前位置即为待删除节点,装备删除数据	}}return false;//整棵树中不存在待删除数据
}

3.2 删除数据及相关节点调整

插找到待删除数据后,显然如果只是简单将该节点删除,有可能将不满足二叉搜索树的要求,那怎么办呢?
删除数据分为以下三种情况:

  1. 左子树为空

左子树为空主要分为以下情形:右子树为空,左子树不为空;左右子树均为空(省略)。
在这里插入图片描述
 不管上述那种情况,我们发现只需将父节点的下一个节点指向待删除节点的右指针即可。但需要注意的是,如果待删除节点为根节点,它将没有父节点,需要单独处理。

【代码实现】:

if (cur->_left == nullptr)//左子树为空
{if (parent == _root)//cur为根节点{_root = cur->_right;}else{if (parent->_key > cur->_key)//待删除节点在父节点左子树中{parent->_left = cur->_right;}else//待删除节点在父节点右子树中{parent->_right = cur->_right;}}delete cur;
}
  1. 右子树为空

右子树为空分为单纯右子树为空和左右子树均为空(省)。具体处理方式和左子树为空类似就不多说了。
在这里插入图片描述
【代码实现】:

//左右子树均不为空,查找右子树最小元素进行交换后删除
if (parent == _root)//cur为根节点
{_root = cur->_left;}else{if (parent->_key > cur->_key){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;
}
  1. 左右子树均不为空

这种情况我们可以查找左子树最大值或右子树最小值和待删除删除节点进行交换,交换后我们可以转化为上述两种子问题来删除数据。(接下来博主以交换右子树最小值为例)
在这里插入图片描述

Node* subLeft = cur->_right;
Node* parent = cur;
while (subLeft->_left)
{parent = cur;subLeft = subLeft->_left;
}
//交换
swap(cur->_key, subLeft->_key);
swap(cur->_value, subLeft->_value);
//删除
if (parent->_right = subLeft)
{parent->_right = subLeft->_right;
}
else
{parent->_left = subLeft->_right;
}
delete subLeft;

3.3 完整代码以及递归和非递归版本

递归思路和非递归差球不多,就不一一分析了,下面直接给出两种实现方式代码。

【非递归版本】:

bool Erase(const K& key)
{if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//装备删除数据if (cur->_left == nullptr)//左子树为空{if (parent == _root)//cur为根节点{_root = cur->_right;}else{if (parent->_key > cur->_key){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//右子树为空{if (parent == _root)//cur为根节点{_root = cur->_left;}else{if (parent->_key > cur->_key){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{//左右子树均不为空,查找右子树最小元素进行交换后删除Node* subLeft = cur->_right;Node* parent = cur;while (subLeft->_left){parent = cur;subLeft = subLeft->_left;}//交换swap(cur->_key, subLeft->_key);swap(cur->_value, subLeft->_value);//删除if (parent->_right = subLeft){parent->_right = subLeft->_right;}else{parent->_left = subLeft->_right;}delete subLeft;}return true;}}return false;
}

【递归版本】:

//删除:递归版本
bool EraseR(const K& key)
{return _EraseR(_root, key);//同理,由于需要根节点,在通过一层函数来实现
}
bool _EraseR(Node*& root, const K& key)
{if (root == nullptr)//非找到return false;if (root->_key > key)//转化成递归子问题,在左子树中删除keyreturn _EraseR(root->_left, key);else if (root->_key < key)//转化成递归子问题,在右子树中删除keyreturn _EraseR(root->_right, key);else{//删除数据if (root->_left == nullptr){Node* del = root;root = root->_right;delete del;return true;}else if (_root->_right == nullptr){Node* del = root;root = root->_left;delete del;return true;}else{Node* subLeft = root->_right;while (subLeft->_left){subLeft = subLeft->_left;}//交换swap(root->_key, subLeft->_key);swap(root->_value, subLeft->_value);return _EraseR(root->_right, key); }}
}

四、查找数据

【递归版本】:

//查找:递归版本
Node* FindR(const K& key)
{return _FindR(_root, key);
}
Node* _FindR(Node*& root, const K& key)
{if (root == nullptr)return nullptr;if (root->_key > key)return _FindR(root->_left, key);else if (root->_key < key)return _FindR(root->_right, key);elsereturn root;
}

【非递归版本】:

//查找:非递归版本
Node* 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;}}return nullptr;
}

五、中序遍历

//中序遍历
void Inorder()
{_Inorder(_root);cout << endl;
}void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << "->" << root->_value << " " << endl;_Inorder(root->_right);
}

六、所有代码

gitee:所有代码及测试代码

namespace KeyValue
{template<class K, class V>struct BSTreeNode{K _key;V _value;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;//默认构造函数BSTreeNode(const K& key, const V& value):_key(key), _value(value), _right(nullptr), _left(nullptr){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:
////默认构造BSTree():_root(nullptr){}//拷贝构造BSTree(BSTree<K, V>& t){_root = Copy(t._root);}//赋值重载BSTree<K, V>& operator=(BSTree<K, V> t){swap(_root, t._root);return *this;}//析构函数~BSTree(){Destory(_root);}
////插入, 非递归版本bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if(cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}//链接Node* newNode = new Node(key, value); if (parent->_key > key)parent->_left = newNode;elseparent->_right = newNode;return true;}// 插入: 递归遍布bool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}
///查找:非递归版本Node* 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;}}return nullptr;}//查找:递归版本Node* FindR(const K& key){return _FindR(_root, key);}
///删除:非递归版本bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//装备删除数据if (cur->_left == nullptr)//左子树为空{if (parent == _root)//cur为根节点{_root = cur->_right;}else{if (parent->_key > cur->_key){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//右子树为空{if (parent == _root)//cur为根节点{_root = cur->_left;}else{if (parent->_key > cur->_key){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{//左右子树均不为空,查找右子树最小元素进行交换后删除Node* subLeft = cur->_right;Node* parent = cur;while (subLeft->_left){parent = cur;subLeft = subLeft->_left;}//交换swap(cur->_key, subLeft->_key);swap(cur->_value, subLeft->_value);//删除if (parent->_right = subLeft){parent->_right = subLeft->_right;}else{parent->_left = subLeft->_right;}delete subLeft;}return true;}}return false;}//删除:递归版本bool EraseR(const K& key){return _EraseR(_root, key);}
///中序遍历void Inorder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << "->" << root->_value << " " << endl;_Inorder(root->_right);}private:Node* Copy(Node*& root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destory(Node*& root){if (root == nullptr)return;Destory(root->_right);Destory(root->_left);delete root;root = nullptr;}bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key > key)return _EraseR(root->_left, key);else if (root->_key < key)return _EraseR(root->_right, key);else{//删除数据if (root->_left == nullptr){Node* del = root;root = root->_right;delete del;return true;}else if (_root->_right == nullptr){Node* del = root;root = root->_left;delete del;return true;}else{Node* subLeft = root->_right;while (subLeft->_left){subLeft = subLeft->_left;}//交换swap(root->_key, subLeft->_key);swap(root->_value, subLeft->_value);return _EraseR(root->_right, key); }}}bool _InsertR(Node*& root, const K& key, const V& value){if (root == nullptr){root = new Node(key, value);return true;}if (root->_key > key)return _InsertR(root->_left, key, value);else if (root->_key < key)return _InsertR(root->_right, key, value);elsereturn false;}Node* _FindR(Node*& root, const K& key){if (root == nullptr)return nullptr;if (root->_key > key)return _FindR(root->_left, key);else if (root->_key < key)return _FindR(root->_right, key);elsereturn root;}Node* _root = nullptr;};
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

2024-02-08(Flume)

1.Flume 的架构和MQ消息队列有点类似 2.Flume也可以做数据的持久化操作 在Channel部分选择使用File channel组件 3.Flume进行日志文件监控 场景&#xff1a;企业中应用程序部署后会将日志写入到文件中&#xff0c;我们可以使用Flume从各个日志文件将日志收集到日志中心以便…

双非本科准备秋招(20.2)—— 线程活跃性:死锁、活锁、饥饿

一、死锁 一个线程需要获得多把锁&#xff0c;就容易出现死锁。 比如此时有两把锁&#xff0c;分别是A和B。线程1首先需要获得A&#xff0c;然后获得B&#xff1b;线程2首先需要获得B&#xff0c;然后获得A。于是两个线程就一直等待对方释放锁。 二、死锁之哲学家就餐 一个圆桌…

Oracle 面试题 | 20.精选Oracle高频面试题

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

JavaScript实现轮播图方法

效果图 先来看下效果图&#xff0c;嫌麻烦就不用具体图片来实现了&#xff0c;主要是理清思路。&#xff08;自动轮播&#xff0c;左右按钮切换图片&#xff0c;小圆点切换图片&#xff0c;鼠标移入暂停轮播&#xff0c;鼠标移出继续轮播&#xff09; HTML 首先是html内容&am…

Open CASCADE学习|求圆的切线与切点

在几何学中&#xff0c;一个圆的切线被定义为与圆相切于一点的直线&#xff0c;而该点被称为切点。这意味着切线在切点处与圆仅有一个交点&#xff0c;并且在该点处&#xff0c;切线的方向与圆的半径垂直。 以下是关于圆的切线和切点的一些重要性质&#xff1a; 切线与半径的…

【开源】SpringBoot框架开发医院门诊预约挂号系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 功能性需求2.1.1 数据中心模块2.1.2 科室医生档案模块2.1.3 预约挂号模块2.1.4 医院时政模块 2.2 可行性分析2.2.1 可靠性2.2.2 易用性2.2.3 维护性 三、数据库设计3.1 用户表3.2 科室档案表3.3 医生档案表3.4 医生放号…

讯飞星火认知大模型V3.5 python调用 Web API

具体参考 科大讯飞:星火认知大模型Web API文档 目录 1.首先要注册一个 讯飞星火账号&#xff0c;2. 按照自己的业务需求&#xff0c;翻看相关SDK开发文档&#xff0c; 如图1所示。3. 星火认知大模型Web API python示例源码文件共两个*接口请求与接口解析函数&#xff1a;Spark…

TCP和UDP相关问题(重点)——8.TCP的拥塞控制怎么实现的?

在某段时间内&#xff0c;若对网络中某一资源的需求超过了该资源所能提供的可用部分&#xff0c;网络性能就会变坏&#xff0c;比如在高速公路上行驶的车辆&#xff0c;如果一时期内涌入了太多的车辆&#xff0c;道路将变得拥堵&#xff0c;交通状况变差。网络中也是一样&#…

Quartus工程的qsf配置约束文件介绍

一、qsf文件概述 qsf&#xff1a;Quartus Setting File&#xff0c;是Quartus工程的配置文件&#xff1b; 包含一个Quartus工程的所有约束&#xff0c;包括工程的软件版本信息、FPGA器件信息、引脚约分配、引脚电平分配&#xff0c;编译约束和用于Classic TimingAnalyzer的时…

MATLAB环境下基于深层小波时间散射网络的ECG信号分类

2012年&#xff0c;法国工程学院院士Mallat教授深受深度学习结构框架思想的启发&#xff0c;提出了基于小波变换的小波时间散射网络&#xff0c;并以此构造了小波时间散射网络。 小波时间散射网络的结构类似于深度卷积神经网络&#xff0c;不同的是其滤波器是预先确定好的小波…

DMA直接内存访问,STM32实现高速数据传输使用配置

1、DMA运用场景 随着智能化、信息化的不断推进&#xff0c;嵌入式设备的数据处理量也呈现指数级增加&#xff0c;因此对于巨大的数据量处理的情况时&#xff0c;必须采取其它的方式去替CPU减负&#xff0c;以保证嵌入式设备性能。例如SD卡存储器和音视频、网络高速通信等其它情…

Vue中 常用的修饰符有哪些

Vue是一款建立在JavaScript框架上的开源前端库&#xff0c;已经成为当今前端开发人员最喜爱的选择之一。它的简洁语法和强大的功能使得开发者可以轻松地构建交互性的网页应用程序。在Vue中&#xff0c;修饰符是一个重要的概念&#xff0c;它们可以帮助我们更好地控制和定制DOM元…

【数据结构】二叉树的顺序结构及链式结构

目录 1.树的概念及结构 1.1树的概念 1.2树的相关概念 ​编辑 1.3树的表示 1.4树在实际中的运用&#xff08;表示文件系统的目录树结构&#xff09; 2.二叉树概念及结构 2.1二叉树的概念 2.2现实中的二叉树 ​编辑 2.3特殊的二叉树 2.4二叉树的性质 2.5二叉树的存储结…

c++新特性override和final

override 作用: 在子类中重写父类的虚函数&#xff0c;我们可以在子类的虚函数声明后加上override。 上图就在重写eat()的时候&#xff0c;加上override。 作用: 1. 可以提示读者&#xff0c;这个函数是重写自父类中的。 2. 加上override之后&#xff0c;我们在重…

数据库管理-第148期 最强Oracle监控EMCC深入使用-05(20240208)

数据库管理148期 2024-02-08 数据库管理-第148期 最强Oracle监控EMCC深入使用-05&#xff08;20240208&#xff09;1 性能主页2 ADDM Spotlight3 实时ADDM4 数据库的其他5 主机总结 数据库管理-第148期 最强Oracle监控EMCC深入使用-05&#xff08;20240208&#xff09; 作者&am…

实例分割论文阅读之:FCN:《Fully Convolutional Networks for Semantica Segmentation》

论文地址:https://openaccess.thecvf.com/content_cvpr_2015/papers/Long_Fully_Convolutional_Networks_2015_CVPR_paper.pdf 代码链接&#xff1a;https://github.com/pytorch/vision 摘要 卷积网络是强大的视觉模型&#xff0c;可以产生特征层次结构。我们证明&#xff0c…

Python解决SSL不可用问题

参考&#xff1a;https://blog.csdn.net/weixin_44894162/article/details/126342591 一、问题描述&#xff1a; 报错概述&#xff1a; WARNING: pip is configured with locations that require TLS/SSL, however the ssl module in Python is not available. ## 警告:pip配…

Project 2019下载安装教程,保姆级教程,附安装包和工具

前言 Project是一款项目管理软件&#xff0c;不仅可以快速、准确地创建项目计划&#xff0c;而且可以帮助项目经理实现项目进度、成本的控制、分析和预测&#xff0c;使项目工期大大缩短&#xff0c;资源得到有效利用&#xff0c;提高经济效益。软件设计目的在于协助专案经理发…

ubuntu原始套接字多线程负载均衡

原始套接字多线程负载均衡是一种在网络编程中常见的技术&#xff0c;特别是在高性能网络应用或网络安全工具中。这种技术允许应用程序在多个线程之间有效地分配和处理网络流量&#xff0c;提高系统的并发性能。以下是关于原始套接字多线程负载均衡技术的一些介绍&#xff1a; …

交通 | 共乘出行(下):基于图结构的动态多时空供需网络的均衡度量方法

博客&#xff1a;Alex Chin, & Tony Qin. (2023.02.25). Quantifying Efficiency in Ridesharing Marketplaces. Link: https://eng.lyft.com/quantifying-efficiency-in-ridesharing-marketplaces-affd53043db2 论文&#xff1a;Chin, Alex, and Zhiwei Qin. “A Unified…