二叉搜索树模拟实现

目录

认识二叉搜索树：

模拟实现：

节点结构体构建：

insert（插入）:

 find（查找）：

erase（删除）（重点）：

 全部代码

认识二叉搜索树：

        二叉搜索树（BST，Binary Search Tree）又称二叉排序树，二叉查找树，主要功能是排序，去重，查找一个值是否存在。

        二叉搜索树在普通二叉树的特性上加上了一点，也就是每个根节点，左子树的值始终比根节点的值小，右子树的值始终比根节点的值要大。

        这样做的好处是什么呢？当我们在这颗树中查找某个值时，若这个值比根小就往左走，若这个值比根大就往右走，也就是说，我们最少走高度次，就能找到它，根据二叉树特性：n = 2^h - 1,n表示节点数，h表示高度，换算一下，h = log(n+1)，所以我们查找一个数的时间复杂度就为O(logn),这个时间复杂度是个什么概念呢？若有10亿个数据在树里，当我们查找时，最坏查找30次就能找到，因为2的30次方约等于10亿，相比我们遍历一遍，最坏情况需要查找10亿次，所以它的含金量就不必我多说了。

模拟实现：

节点结构体构建：

        树中的每个节点，我使用结构体来存储：

接下来就可以开始构建类模板了：

insert（插入）:

注意：二叉搜索树一般不允许数据冗余，所以如果插入树中已有的值，则插入失败

思路：用cur找到插入的位置， 将要插入的值和根节点作比较，会出现3种情况，1，比根节点小，cur往左走，2，比根节点大，cur往右走，3，与根节点相等，插入失败。我们每次移动cur都要用parent记录它父节点的位置，这样当找到应该插入的位置时，用parent的左子树或者右子树指向它。

bool insert(const K& val){if (_root == nullptr)//若原来树为空{_root = new node(val);return true;}node* cur = _root;node* parent = nullptr;while (cur)//开始找插入位置{if (val < cur->_val){parent = cur;cur = parent->left;}else if (val > cur->_val){parent = cur;cur = parent->right;}else{return false;}}cur = new node(val);if (val > parent->_val){parent->right = cur;}else{parent->left = cur;}}

 find（查找）：

思路：这个简单，被查找的值比根节点小就往左走，比根节点大就往右走，相等返回true，走到空节点还没找到就返回false：

	bool find(const K& val){node* cur = _root;while (cur){if (val > cur->_val){cur = cur->right;}else if (val < cur->_val){cur = cur->left;}else{return true;}}return false;}

erase（删除）（重点）：

思路：

在二叉搜索树中删除一个值，先找到这个值所在的节点，删除这个节点后，返回true，找不到返回false，这个被删除的节点肯定不能空出来，还是要它组成一颗二叉搜索树，我们在删除的时候就会遇到这几种情况：

1，要删除的节点的左子树为空，我们只需将要删除的节点的父节点指向该左子树就行，右子树同理：

如图所示：

我们要删除1，因为1只有一个孩子，所以我们只需要将3的左子树指向1的孩子就行。不过要注意，当要删除的就是最上面的根节点时，也就是父节点为空，如下图删除13时，这时需要特判的，我们只需将根节点改成那个唯一的孩子就行。

 2.要删除的节点，左右孩子都存在

        这时要删除这个节点就有点复杂了，就需要使用替代法删除，看下图这个场景，当我们要删除3：

替代法删除， 就是在被删除节点的左右子树中找到能在这个位置占得住脚的值来替换掉这个位置，所以现在主要就是到底哪些值是能在被删除节点的位置站的住脚。如上图，也就是要比1大比6小。

 这些值就是，左子树的最大节点和右子树的最小节点，原理不再多说，想必看上图应该都能体会出来，上图左子树的最大节点是2，右子树的最小节点是4，都能在3的位置占住脚，所以我们只需要随便找到一个，这里我找右子树的最小值，找到后交换右子树最小值和需要删除节点的值，再让右子树最小值的父节点的左子树指向右子树最小值的右一个孩子就行（因为左孩子肯定为空，不然它就不是右子树的最小值），然后删除右节点最小值位置的节点，。

为了帮助理解来模拟一下：

1.找到右子树的最小值4及它的父亲节点：

2.交换需要删除的节点和左子树最小值的值：

 ​​​​​​​3.再让右子树最小值的父节点的左子树指向右子树最小值的右一个孩子：

4.最后删除RIghtMin所在的节点：

 最后达成预期！

注意有特殊情况，需要特判！当右子树的最小值就是右子树的第一个根时，如下图删除3时

这时右子树的最小节点就是第一个根6，此时当我们走到上面模拟的第三步后就会出现这样的情况：

画圈部分直接被抛弃掉了，而且还会造成内存泄漏。

解决方法很简单，只需简单用if判断一下这种情况即可，如果RightMinparent->right==RightMin，就让RightMinparent->right=RightMin->right, 如果RightMinparent->left==RightMin,就让RightMinparent->left=RightMin->right.

	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 = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root)//特判{_root = cur->_left;}else{// 右为空，父亲指向我的左if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空，替换法删除// // 查找右子树的最小节点替代删除Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left)//找右子树的最小节点放在rightMin中{rightMinParent = rightMin;rightMin = rightMin->_left;}swap(cur->_key, rightMin->_key);//找到后交换if (rightMinParent->_left == rightMin)//特判rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;}return true;}}return false;}

 全部代码：

#pragma once
#include<string>template<class T>
struct BSTNode
{BSTNode<T>* left;//左子树BSTNode<T>* right;//右子树T _val;//值BSTNode(T& val)//构造函数:left(nullptr), right(nullptr), _val(val);{}
};
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* cur = _root;node* parent = nullptr;while (cur)//开始找插入位置{if (val < cur->_val){parent = cur;cur = parent->left;}else if (val > cur->_val){parent = cur;cur = parent->right;}else{return false;}}cur = new node(val);if (val > parent->_val){parent->right = cur;}else{parent->left = cur;}}bool find(const K& val){node* cur = _root;while (cur){if (val > cur->_val){cur = cur->right;}else if (val < cur->_val){cur = cur->left;}else{return true;}}return false;}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 = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root)//特判{_root = cur->_left;}else{// 右为空，父亲指向我的左if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空，替换法删除// // 查找右子树的最小节点替代删除Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left)//找右子树的最小节点放在rightMin中{rightMinParent = rightMin;rightMin = rightMin->_left;}swap(cur->_key, rightMin->_key);//找到后交换if (rightMinParent->_left == rightMin)//特判rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;}return true;}}return false;}
private:node* _root = nullptr;
};

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

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

相关文章

第十一讲：指针（3）

第十一讲：指针（3）

第十一讲&#xff1a;指针&#xff08;3&#xff09; 1.字符指针变量1.1存储一个字符1.2存储一个字符串1.3一个有趣的面试题 2.数组指针变量2.1什么是数组指针变量2.2数组指针变量的初始化 3.二维数组传参的本质4.函数指针变量4.1介绍函数指针变量4.2 两段有趣的代码4.2.1代码1…
阅读更多...
内容安全（AV）

内容安全（AV）

防病毒网关&#xff08;AV&#xff09;简介 基于网络侧 识别 病毒文件&#xff0c;工作范围2~7层。这里的网关指的是内网和外网之间的一个关口&#xff0c;在此进行病毒的查杀。在深信服中就有一个EDR设备&#xff0c;该设备就是有两种部署&#xff0c;一个部署在网关&#xf…
阅读更多...
Java----数组的定义和使用

Java----数组的定义和使用

1.数组的定义 在Java中&#xff0c;数组是一种相同数据类型的集合。数组在内存中是一段连续的空间。 2.数组的创建和初始化 2.1数组的创建 在Java中&#xff0c;数组创建的形式与C语言又所不同。 Java中数组创建的形式 T[] 数组名 new T[N]; 1.T表示数组存放的数据类型…
阅读更多...
FPGA学习笔记（1）——Vivado和HLS

FPGA学习笔记（1）——Vivado和HLS

1 Vivado设计 1.1 FPGA基本知识 Xilinx Atrix-7使用6输入LUT结构&#xff08;0-63&#xff09;CLB&#xff1a;可配置逻辑块Slice&#xff1a;每个CLB包含2个Slice(包含查找表LUT和8位寄存器REG)布线池&#xff1a;围绕在CLB周围&#xff0c;衔接FPGA的资源调度I/O块&#xf…
阅读更多...
vivado Spartan-7 配置存储器器件

vivado Spartan-7 配置存储器器件

下表所示闪存器件支持通过 Vivado 软件对 Spartan -7 器件执行擦除、空白检查、编程和验证等配置操作。 本附录中的表格所列赛灵思系列非易失性存储器将不断保持更新 &#xff0c; 并支持通过 Vivado 软件对其中所列非易失性存储器 进行擦除、空白检查、编程和验证。赛灵…
阅读更多...
带EXCEL附件邮件发送相关代码

带EXCEL附件邮件发送相关代码

1.查看生成的邮件 2.1 非面向对象的方式&#xff08;demo直接copy即可&#xff09; ​ REPORT Z12. DATA: IT_DOCUMENT_DATA TYPE SODOCCHGI1,IT_CONTENT_TEXT TYPE STANDARD TABLE OF SOLISTI1 WITH HEADER LINE,IT_PACKING_LIST TYPE TABLE OF SOPCKLSTI1 WITH HEADER LIN…
阅读更多...
在做题中学习（57）：寻找数组的中心下标

在做题中学习（57）：寻找数组的中心下标

724. 寻找数组的中心下标 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a;前缀和后缀和 思路&#xff1a;要看一个数是不是中心下标&#xff0c;就看他前面数的和 与 后面数的和 相不相等。 1.i前面数的和&#xff0c;是[0,i-1] 的前缀和&#xff0c;i后面数的和&am…
阅读更多...
快递物流查询：如何实现快递批量查询？这些技巧助你轻松应对

快递物流查询：如何实现快递批量查询？这些技巧助你轻松应对

在日常生活和工作中&#xff0c;我们经常需要查询快递物流信息&#xff0c;尤其是当面对大量的快递包裹时&#xff0c;逐一查询无疑会耗费大量的时间和精力。这时&#xff0c;实现快递批量查询就显得尤为重要。本文将为你介绍办公提效工具一些实现快递批量查询的技巧&#xff0…
阅读更多...
国内有哪些知名的网络安全厂商？

国内有哪些知名的网络安全厂商？

首先就是360&#xff0c;这个我相信大家并不陌生了吧&#xff0c;你的电脑装过360么&#xff1f; 360在个人终端服务那是妥妥的扛把子&#xff0c;但是在企业服务里虽然有他们的身影却略显不足。 第二个就是深信服&#xff0c;网络安全的老牌大佬&#xff0c;业务覆盖了全球5…
阅读更多...
【数据分析】 JupyterNotebook安装及使用简介

【数据分析】 JupyterNotebook安装及使用简介

各位大佬好 &#xff0c;这里是阿川的博客 &#xff0c; 祝您变得更强 个人主页&#xff1a;在线OJ的阿川 大佬的支持和鼓励&#xff0c;将是我成长路上最大的动力 阿川水平有限&#xff0c;如有错误&#xff0c;欢迎大佬指正 在数据分析中&#xff0c;一般用Pycharm编辑代…
阅读更多...
18 分页：介绍

18 分页：介绍

目录 简单例子 页表存在哪里 列表中究竟有什么 分页&#xff1a;也很慢 内存追踪 小结 在解决大多数空间管理问题上面&#xff0c;操作系统有两种方法&#xff1a; 第一种就是将空间分割成不同长度的分片&#xff0c;类似于虚拟内存管理中的分段&#xff0c;但是这个方法…
阅读更多...
MySQL45讲(一)(40)

MySQL45讲(一)(40)

回顾binlog_formatstatement STATEMENT 记录SQL语句。日志文件小&#xff0c;节约IO&#xff0c;但是对一些系统函数不能准确复制或不能复制&#xff0c;如now()、uuid()等 在RR隔离级别下&#xff0c;binlog_formatstatement 如果执行insert select from 这条语句是对于一张…
阅读更多...
win10禁止自动更新的终极方法

win10禁止自动更新的终极方法

添加注册表值 1.运行&#xff0c;输入regedit 2.打开注册表编辑器依次进入以下路径“计算机\HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings”。 3.在Settings项中&#xff0c;新建DWORD&#xff08;32位&#xff09;值(D)&#xff0c;重命名为以下命名“Fl…
阅读更多...
vuex核心概念-getters

vuex核心概念-getters

除了state之外&#xff0c;有时我们还需要从state中派生出一些状态&#xff0c;这些状态是依赖state的&#xff0c;此时会用到getters。
阅读更多...
2023版brupsuite专业破解安装

2023版brupsuite专业破解安装

安装教程&#xff0c;分两部分&#xff1a; 1、安装java环境、参考链接JAVA安装配置----最详细的教程&#xff08;测试木头人&#xff09;_java安装教程详细-CSDN博客 2、安装2023.4版本brupsuite&#xff1a;参考链接 2023最新版—Brup_Suite安装配置----最详细的教程&…
阅读更多...
实体同城商家短视频获客，3天直播课，玩转实体商家私域，引爆门店增长

实体同城商家短视频获客，3天直播课，玩转实体商家私域，引爆门店增长

课程内容&#xff1a; 实体同城3天直播课【资料】 实体商家获客第一天 .mp4 实体商家获客第二天上.mp4 实体商家获客第二天,mp4 实体商家获客第三天.mp4 实体商家获客第4天.mp4 网盘自动获取 链接&#xff1a;https://pan.baidu.com/s/1lpzKPim76qettahxvxtjaQ?pwd0b8x…
阅读更多...
数据结构----二叉树

数据结构----二叉树

博主主页: 码农派大星. 关注博主带你了解更多数据结构知识 1. 树型结构 1.1 概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树&#xff0c;也就是说它是根朝上…
阅读更多...
对Windows超融合S2D的一些补充

对Windows超融合S2D的一些补充

先说一个不知道算不算BUG的例子&#xff0c;下面这个存储池是用两台服务器各2块10G建立的&#xff0c;除去系统保留的部分&#xff0c;显示还有13G可用。 但如果使用其新建虚拟磁盘会显示可用的空间为0 然后我又各增加了一块10G硬盘进池&#xff0c;变成了可用空间为30.5GB …
阅读更多...
如何理解VMware中的网络模式（NAT、桥接、仅主机）

如何理解VMware中的网络模式（NAT、桥接、仅主机）

目录 Ⅰ.NAT模式 Ⅱ.仅主机模式 Ⅲ.桥接模式 Ⅰ.NAT模式 NAT模式&#xff1a;将物理机的网卡作为虚拟交换机的上线链路&#xff0c;将vmware的私有网络转成可以上网的地址进行网络访问&#xff0c;因此在NAT模式下虚拟机是可以访问外部网络的&#xff08;图一&#xff09; …
阅读更多...
springboot整合redis多数据源(附带RedisUtil)

springboot整合redis多数据源(附带RedisUtil)

单数据源RedisUtil(静态) 单数据源RedisUtil,我这里implements ApplicationContextAware在setApplicationContext注入redisTemplate,工具类可以直接类RedisUtil.StringOps.get()使用 package com.vehicle.manager.core.util;import com.alibaba.fastjson.JSON; import lombok.e…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发