c++实现B树(下)

 书接上回小吉讲的是B树的搭建和新增方法的实现(blog传送门🚪:B树实现上)(如果有小可爱对B树还不是很了解的话,可以先看完上一篇blog,再来看小吉的这篇blog)。那这一篇主要讲的是B树中删除操作的实现。
 在看小吉的数据结构与算法(c++实现)系列博客中,各位小可爱们应该能发现,其实在实现一个数据结构时,删除操作普遍比新增操作要难。小吉浅浅预告一下B树的删除操作可以说是天花板级别的难。但是各位小可爱们不要怕,跟着小吉的博客看下去B树删除易如反掌(哈哈,夸张了🤣)

在实现B树删除操作之前,小吉先在这声明一下:B树的删除是删除某个节点的key并不是将节点删除(无需使用delete)

九个成员方法

 在正式分析B树删除之前,先要实现9个方法(不要害怕,这九个方法都非常简单),这九个方法在后期实现删除操作代码时大有用处(可以小小期待一下)

int removeKey(int index);//移除指定index处的key
int removeRightmostKey();//移除最右边的key
Node* removeChild(int index);//移除指定index处的child
Node* removeLeftmostChild();//移除最左边的child
Node* removeRightmostChild();//移除最右边的child
Node* childLeftSibling(int index);//index孩子处左边的兄弟
Node* childRightSibling(int index);//index孩子处右边的兄弟
void moveToTarget(Node* target);//复制当前节点的所有key和child到target

这些方法都定义在Node节点类中,这些方法都比较简单,小吉在这就不详细讲解了,直接上代码。

int Node::removeKey(int index)
{
	int t = _keys[index];
	_keys.erase(_keys.begin() + index);
	KeyNumber--;
	return t;
}

int Node::removeLeftmostKey()
{
	return removeKey(0);
}

int Node::removeRightmostKey()
{
	return removeKey(KeyNumber - 1);
}

Node* Node::removeChild(int index)
{
	Node* t = _children[index];
	_children.erase(_children.begin() + index);
	return t;
}

Node* Node::removeLeftmostChild()
{
	return removeChild(0);
}

Node* Node::removeRightmostChild()
{
	return removeChild(KeyNumber - 1);
}

Node* Node::childLeftSibling(int index)
{
	return index > 0 ? _children[index - 1] : nullptr;
}

Node* Node::childRightSibling(int index)
{
	return index == KeyNumber ? nullptr : _children[index + 1];
}

void Node::moveToTarget(Node* target)
{
	int start = target->KeyNumber;
	if (!this->_leaf)
	{
		for (int i = 0; i <= this->KeyNumber; i++)
		{
			target->_children[start + i] = this->_children[i];
		}
	}
	for (int i = 0; i < this->KeyNumber; i++)
	{
		target->_keys[target->KeyNumber++] = this->_keys[i];
	}
}

搭建remove删除方法的架子

首先明确一点要删除节点的前提是要先找到节点才能进行删除操作,所以remove方法最初的雏形就是找要删除的节点(采用递归进行查找)

 找节点的思路在上一篇blog新增节点时有体现,小吉在这也不详细讲解了,直接上代码👇

void BTree::remove(int key)
{
	doremove(_root, key,0);
}

void BTree::doremove(Node* node, int key)
{
	int i = 0;
	while (i < node->KeyNumber)
	{
		if (node->_keys[i] >= key)
		{
			break;
		}
		i++;
	}

	if (node->_leaf)//叶子节点
	{
		if (i < node->KeyNumber && node->_keys[i] == key)//i找到:代表待删除key的索引
		{
			
		}
		else//i没找到
		{
			return;
		}
	}
	else//非叶子节点
	{
		if (i < node->KeyNumber && node->_keys[i] == key)//i找到:代表待删除key的索引
		{
			
		}
		else//i没找到:代表第i个孩子继续查找
		{
			doremove(node,node->_children[i], key,i);
		}
	}
}

remove删除情况分类

主要分为以下4种情况:
case1:当前节点是叶子节点,没找到
case2:当前节点是叶子节点,找到了
case3:当前节点是非叶子节点,没找到
case4:当前节点是非叶子节点,找到了

叶子节点

 分析当前节点是叶子节点的情况,这种情况比较简单,找到就删除当前节点要删除的key值(调用前面实现的九个小方法中的removeKey方法即可),没找到说明B树中没有我们要删除的key值,直接return退出即可。

if (node->_leaf)//叶子节点
	{
		if (i < node->KeyNumber && node->_keys[i] == key)//i找到:代表待删除key的索引
		{
			node->removeKey(i);
		}
		else//i没找到
		{
			return;
		}
	}
非叶子节点

没找到:递归继续寻找
找到:1.找后继的key 2.替换待删除的key 3.删除后继的key
非叶子节点删除

else//非叶子节点
	{
		if (i < node->KeyNumber && node->_keys[i] == key)//i找到:代表待删除key的索引
		{
			//1.找到后继key
			Node* s = node->_children[i + 1];
			while (!s->_leaf)
			{
				s = s->_children[0];
			}
			int skey = s->_keys[0];
			//2.替换待删除key
			node->_keys[i] = skey;
			//3.删除后继key
			doremove(node,node->_children[i + 1], skey,i+1);
		}
		else//i没找到:代表第i个孩子继续查找
		{
			doremove(node,node->_children[i], key,i);
		}
	}

删除完不平衡的处理

  在删除节点完可能存在删除后key数目<下限(根节点除外),导致不平衡的情况
 对平衡的调整又可以分为一下三种情况:
case1:左边富裕,右旋
case2:右边富裕,左旋
case3:两边都不够借,向左合并
 void balance (Node* parent,Node* x,int i) //x为要调整的节点,i为被调整孩子的索引
 注: 为了实现平衡函数的传参,doremove方法还要再加上两个参数void BTree::doremove(Node* parent,Node* node, int key,int index)//index被删除节点的索引

左边富裕,右旋

右旋

右旋:1)父节点中前驱key旋转下来(前驱key是要删除节点的前驱)
2)left中最大的孩子换爹(被调整节点的左兄弟不为叶子节点要执行这一步)
2)left中最大的的key旋转上去

下面👇是代码实现旋转的过程:

void BTree::balance(Node* parent, Node* x, int i)
{
    Node* left = parent->childLeftSibling(i);
	if (left != nullptr && left->KeyNumber > MIN_KEYNUMS)
	{//左边富裕,右旋
		x->insertKey(0, parent->_keys[i - 1]);
		if (!left->_leaf)
		{
			x->insertChild(0, left->removeRightmostChild());
		}
		parent->_keys[i-1]= left->removeRightmostKey();
		return;
	}
}
右边富裕,左旋

左旋:1)父结点中后继key旋转下来(后继key是要删除节点的后继)
2)right中最小的孩子换爹(被调整节点的右兄弟不为叶子节点时要执行这一步)
3)right中最小的key旋转上去

 和左边富裕,右旋的情况类似,小吉这里就不画图了,直接上代码

void BTree::balance(Node* parent, Node* x, int i)
{
    Node* right = parent->childRightSibling(i);
    if (right != nullptr && right->KeyNumber > MIN_KEYNUMS)
	{//右边富裕,左旋
		x->insertKey(x->KeyNumber, parent->_keys[i]);
		if (!right->_leaf)
		{
			x->insertChild(x->KeyNumber+1, right->removeLeftmostChild());
		}
		parent->_keys[i] = right->removeLeftmostKey();
		return;
	}
两边都不够借,向左合并

case1:被调整节点有左兄弟,往左兄弟处合并
case2:被调整节点没有左兄弟,父节点和右边的兄弟向自己处合并

case1:
向左合并
case2:
向自己处合并
代码呈现👇:

//两边都不够借,向左合并
	if (left != nullptr)
	{//向左兄弟合并
		parent->removeChild(i);
		left->insertKey(left->KeyNumber, parent->removeKey(i - 1));
		x->moveToTarget(left);
	}
	else
	{//向自己合并
		parent->removeChild(i + 1);
		x->insertKey(x->KeyNumber, parent->removeKey(i));
		right->moveToTarget(x);
	}

到这里,B树删除的所有涉及到的知识点都已经讲完了,下面小吉给大家提供一个B树删除的测试代码。

B树删除的测试代码

void testRemove()
{
	BTree tree(3);
	for (int i = 1; i <= 6; i++)
	{
		tree.put(i);
	}
	tree.remove(2);
	Node* root = tree._root;
	Node* leftchild = root->_children[0];
	cout << root->_keys[0] << endl;
	for (int i = 0; i < leftchild->KeyNumber; i++)
	{
		cout << leftchild->_keys[i] << ' ';
	}
	cout << endl;
}

到这里,这篇blog要结束了,有点小长,也有点小难,可能一次性看完对一些小可爱们有难度,不要急,慢慢看,多给自己一点时间❤️
(其实这篇博客从9月份写到了11月🤣,可以说是小吉已经发表的博客中最长的一篇了,也是最难的一篇,原计划打算九月份写完的,中途去备考了一下软设,所以就一直拖到现在才写完,不好意思耽误了这么久了😖)

&emps;最后,创作不易(这篇blog小吉真的写了很久),还望大家多多支持(点赞收藏关注小吉🌹)

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Oracle篇】掌握SQL Tuning Advisor优化工具:从工具使用到SQL优化的全方位指南(第六篇,总共七篇)

&#x1f4ab;《博主介绍》&#xff1a;✨又是一天没白过&#xff0c;我是奈斯&#xff0c;DBA一名✨ &#x1f4ab;《擅长领域》&#xff1a;✌️擅长Oracle、MySQL、SQLserver、阿里云AnalyticDB for MySQL(分布式数据仓库)、Linux&#xff0c;也在扩展大数据方向的知识面✌️…

使用Java绘制图片边框,解决微信小程序map组件中marker与label层级关系问题,label增加外边框后显示不能置与marker上面

今天上线的时候发现系统不同显示好像不一样&#xff0c;苹果手机打开的时候是正常的&#xff0c;但是一旦用安卓手机打开就会出现label不置顶的情况。尝试了很多种办法&#xff0c;也在官方查看了map相关的文档&#xff0c;发现并没有给label设置zIndex的属性&#xff0c;只看到…

关于sass在Vue3中编写bem框架报错以及警告问题记录

在编写完bem框架后 在vite.config.ts文件进行预编译处理时&#xff0c;报错的错误 1. 处理方式&#xff1a;使用新版api&#xff0c; 如图&#xff1a; 2. 处理方式&#xff1a;使用 use 替换掉 import&#xff0c; 如图&#xff1a; 3. 处理方式&#xff1a;使用路径别名&am…

BizDevOps:从理念到实践,贯通企业全链路协同

&#x1f446; 点击蓝字 关注我们 引言 BizDevOps的概念由DevOps发展和进化而来&#xff0c;其目标超越了开发和运维的协同&#xff0c;进一步实现业务、研发和运维的全链条协作&#xff0c;让业务作为价值的起点及核心目标。 BizDevOps的核心驱动力在于解决效率和正确性上的割…

C#与C++交互开发系列(二十二):跨进程通信之使用基于HTTP协议的REST风格的API

1. 前言 REST API&#xff08;Representational State Transfer Application Programming Interface&#xff09;是一种基于HTTP协议的通信方式&#xff0c;广泛用于网络服务和分布式应用程序之间的通信。通过REST API&#xff0c;可以让C#和C应用程序进行跨进程、甚至跨平台的…

ECharts饼图-饼图15,附视频讲解与代码下载

引言&#xff1a; 在数据可视化的世界里&#xff0c;ECharts凭借其丰富的图表类型和强大的配置能力&#xff0c;成为了众多开发者的首选。今天&#xff0c;我将带大家一起实现一个饼图图表&#xff0c;通过该图表我们可以直观地展示和分析数据。此外&#xff0c;我还将提供详…

Python在数据科学中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 Python在数据科学中的应用 Python在数据科学中的应用 Python在数据科学中的应用 引言 Python 概述 定义与特点 发展历程 Python…

IDEA2024:右下角显示内存

使用场景&#xff1a; 实时知晓idea内存使用情况 解决方案: 开启内存显示 View -> Apperance -> Status Bar Widgets -> Memory Indicator 效果如下&#xff1a;

【计算机网络】【网络层】【习题】

计算机网络-传输层-习题 文章目录 13. 图 4-69 给出了距离-向量协议工作过程&#xff0c;表&#xff08;a&#xff09;是路由表 R1 初始的路由表&#xff0c;表&#xff08;b&#xff09;是相邻路由器 R2 传送来的路由表。请写出 R1 更新后的路由表&#xff08;c&#xff09;。…

vue 计算属性get set

<template><div id"app"><h1>用户信息</h1><p>全名&#xff1a;{{ fullName }}</p><input v-model"fullName" placeholder"请输入全名" /><p>姓&#xff1a;{{ firstName }}</p><p>…

74HC245

74HC245&#xff1a;典型的CMOS型缓冲门电路 在这里用于增加电压

【代码管理之道】Git 高级工作流与团队协作实践:深入探讨与实战案例

引言 在前几篇文章中&#xff0c;我们详细介绍了 Git 的基本概念、高级功能、最佳实践以及高级工作流和团队协作实践。本文将继续深入探讨 Git 的高级工作流和团队协作实践&#xff0c;帮助读者更好地理解和应用这些概念。我们将通过具体的实战案例&#xff0c;展示如何在实际…

NopReport中如何通过可扩展性设计实现二维码导出

NopReport是从零开始编写的下一代中国式报表引擎&#xff0c;它的核心仅有3000多行代码&#xff0c;但是完整实现了中国式非线性报表理论所定义的层次坐标和行列对称展开算法。 使用介绍&#xff1a;采用Excel作为设计器的开源中国式报表引擎:NopReport, 视频讲解源码分析: 非…

Linux(光速安装+rocky linux镜像)

寻找镜像 Download - Rocky Linux 如果用作桌面的&#xff0c;下载DVD的选项&#xff0c;占的存储比较多了&#xff0c;如果下载最小的&#xff0c;则没有桌面环境。 配置虚拟机 Linux&#xff08;光速安装centos镜像 图片大白话&#xff09;-CSDN博客 有些一样的我就不一…

python文件命名,不注意容易出错

在python中&#xff0c;文件名也会作为模块的名称使用。 举个例子 工程目录如下&#xff1a; 其中&#xff0c;文件夹为sys_check&#xff0c;其下还有一个sys_check1.py文件。 如果该文件名也是sys_check.py&#xff0c;可能会导致问题&#xff0c;在其它文件中引用模块时…

给阿里云OSS启用SSL

自定义域名需要指向阿里云 OSS&#xff0c;并且你希望为这个域名获取 SSL 证书&#xff0c;可以使用 DNS 验证的方法来获取证书。以下是详细步骤&#xff1a; 关键前提&#xff1a; 关键是需要在阿里云控制台的域名 权威域名解析中添加子域名aliyuncs.xxx.com 使用 DNS 验证获取…

边缘计算在智能制造中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 边缘计算在智能制造中的应用 边缘计算在智能制造中的应用 边缘计算在智能制造中的应用 引言 边缘计算概述 定义与原理 发展历程 …

定时任务进行简单监控、爬虫的自动化之旅

原文链接&#xff1a;「定时任务」进阶指南&#xff1a;监控、爬虫的自动化之旅

『VUE』25. 组件事件与v-model(详细图文注释)

目录 功能介绍示例总结 欢迎关注 『VUE』 专栏&#xff0c;持续更新中 欢迎关注 『VUE』 专栏&#xff0c;持续更新中 功能介绍 预期拿到一个输入搜索框,用户在搜索框中输入数据后实时把数据发送给父组件使用. 示例 主要是对前面的v-model和watch的结合使用,实现获取更新的子…

【Python TensorFlow】进阶指南(续篇二)

在前面的文章中&#xff0c;我们详细探讨了TensorFlow在实际应用中的高级功能和技术细节。本篇将继续深入探讨一些前沿话题&#xff0c;包括但不限于分布式训练、混合精度训练、神经架构搜索&#xff08;NAS&#xff09;、模型微调以及在实际项目中的最佳实践等&#xff0c;帮助…