投稿
  1. 首页
  2. C

数据结构——B-树（c++）

dsp公司 • 2022-6-25 • C • 阅读 54

数据结构——B-树（c++）,第1张

目录

简介

定义

与二叉排序树区别

构建一个二叉排序树时如图：

构建一个B-树如图所示（以五叉B-树为例）

总的来说，B-树就是把二叉树的树节点整合在一起使用：

构建B-树的节点(以五叉B-树为例)

相关分析

相关代码

B-树的查询

相关分析

相关代码

B-树的插入

相关原理

case1：如果插入关键码的B-树为空，则只需要建立一个根节点，并且赋值，如图；

 case2：插入的值小于存在的值时，如图；

case3：插入满的情况进行分裂，如图；

case4：当插入满是并且双亲节点不为空，并且双亲节点未满，如图1->2： 

相关代码

B-树删除

情况分析

case1：删除的关键码是叶子结点x，并且num>minsize时，如图；

case2：删除的关键码是非叶子Q时，如图：

case3：删除后如果num小minsize则需要修改树的结构；右满足；

case4：删除后如果num小minsize则需要修改树的结构；左满足；

case5：当两边都不满足时，如果有右兄弟则进行合并；

case6：当两边都不满足且右孩子为空，则进行和左兄弟合并

 相关代码：

简介

       在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写 *** 作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

定义

一颗m阶B-Tree是一颗m路搜索树，它或者是空树，或者满足下列性质的树：

（1）根节点子女个数为[2,m]；

（2）根节点和叶节点以外的所有分支节点至少有

（3）所有的叶节点都位于同一层。

（4）m阶B-Tree的节点结构如下：

                    n,S0,(K1,S1),(K2,S2),...........(Kn,Sn)

其中，Si是指向子树的指针，0<=i<=n

  • 在子树Si中所有的关键码都小于Ki+1，且大于Ki，0
  • 在子树Sn中所有的关键码都大于Kn。
  • 在子树S0中的所有关键码都小于K1。
  • 子树Si也是m路搜索树，0<=i<=n;

事实上，在B_树的每个结点中还包括友谊徐指针D[m]，指向实际对象存放地址。

K[i]与D[i]（1<=i<=n

B-Tree的一些特点: 

  • 根节点关键字个数是: [1,m-1]x 非根节点的关键字的个是
  • 关键字集合分布在整颗树中;
  • 任何一个关键字出现一次，且只出现在一个结点中; (关键字不容许重复)
  • 搜索有可能在非叶子结点结束;
  • 其搜索性能等价于在关键字全集内做一次二分查找;
与二叉排序树区别

当用该数组{53,17,78,45,87,65,81,94,9,23}；

构建一个二叉排序树时如图：

构建一个B-树如图所示（以五叉B-树为例）

总的来说，B-树就是把二叉树的树节点整合在一起使用：

 一个蓝色的圈就代表一个二叉树

构建B-树的节点(以五叉B-树为例) 相关分析

可以从B-树的相关原理得出：一个B-树的节点至少包含下面几个内容：

  • 每个节点都有自己的双亲节点，所以双亲指针不能少（树的必要指针）；
  • 五个存储关键码的存储单元，及一个大小为五的数组，实际 *** 作中多开辟一个空间用于标志位。
  • 五个存储结构体指针的数组，用于存储自己的左右孩子，实际 *** 作增加一个；
  • 一个整数值用来保存实时关键码个数；
  • 一个整数值保存节点的个数；

如图：

为了后面画图简单，用图二右边代替结构，但是明确指出，其中d，s没有任何意义只是观看方  便；

相关代码 
#define  M  5   //  M 奇数 // 
#define  MAXSIZE (M-1)   // MAX ELEM	 4
#define  MINSIZE (M/2)   // MIN ELEM; 	 2	3  4 
typedef char KeyType;
typedef struct {}Record;
typedef struct
{
	KeyType key;
	Record* recptr;
}ElemType;  // key _ value;

typedef struct BNode
{
	int num; // 
	struct BNode* parent;
	ElemType data[M + 1];    // 0 1 2 3 4 5
	struct BNode* sub[M + 1]; // 0 1 2 3 4 5 
}BNode;
typedef struct
{
	struct BNode* root;
	int cursize;
}BTree;

typedef struct
{
	struct BNode* pnode;	// 
	int index;			//
	bool tag;			//
}Result;
B-树的查询 相关分析

假设一个B-树如图所示：

 现在开始查询是否存在M值；过程如图：

 （1）将M存入标志位，从n开始依次减小与M比较；如果没找到，退出；

 （2）如果大于某个值，比如图中M>K;此时K的下标为1，则指向s->[2];

 （3）重复上述两个步骤；

相关代码 
Result FindKey(BTree& tree, KeyType kx)
{
	Result res = { nullptr,-1,false };
	struct BNode* p = tree.root;
	while (p != nullptr)
	{
		p->data[0].key = kx;
		int i = p->num;
		while (i >= 0 && kx < p->data[i].key)
		{
			--i;
		}
		res.pnode = p;
		res.index = i;
		if (i > 0 && kx == p->data[i].key)
		{
			res.tag = true;
			break;
		}
		p = p->sub[i];
	}
	return res;
}
B-树的插入 相关原理

对于B-树的插入分下面几种情况，为了阐述简单插入关键码为:

char ch[] = { "qwertyuiopasdfghjklzxcvbnm" };

case1：如果插入关键码的B-树为空，则只需要建立一个根节点，并且赋值，如图； 
if (tree.root == nullptr)
	{
		tree.root = MakeRoot(item, nullptr, nullptr);
		tree.cursize = 1;
		return true;
	}

 case2：插入的值小于存在的值时，如图；

如果查询到的位置的节点不为空，并且没有存储该值，则插入；

Result res = FindKey(tree, item.key);
	if (res.pnode != nullptr && res.tag)  return false;
	BNode* ptr = res.pnode;
	int pos = res.index;
	Insert_Item(ptr, pos, item, nullptr);

case3：插入满的情况进行分裂，如图； 
	if (ptr->num > MAXSIZE)
	{
		BNode* newroot = Splice(ptr);
		if (newroot != nullptr)
		{
			tree.root = newroot;
		}
	}
	tree.cursize += 1;

case4：当插入满是并且双亲节点不为空，并且双亲节点未满，如图1->2： 

相关代码 
BNode* MakeRoot(const ElemType& item, BNode* left, BNode* right)
{
	BNode* s = Buynode();
	s->num = 1;
	s->parent = nullptr;
	s->data[1] = item;
	s->sub[0] = left;
	if (left != nullptr) left->parent = s;
	s->sub[1] = right;
	if (right != nullptr) right->parent = s;
	return s;
}
ElemType Move_Item(BNode* s, BNode* ptr, int pos)
{
	for (int i = 0, j = pos + 1; j <= ptr->num; ++i, ++j)
	{
		s->data[i] = ptr->data[j];
		s->sub[i] = ptr->sub[j];
		if (s->sub[i] != nullptr)  // ptr leaf . brch;
		{
			s->sub[i]->parent = s;
		}
	}
	s->num = MINSIZE;
	ptr->num = MINSIZE;
	s->parent = ptr->parent;
	return s->data[0];
}
void Insert_Item(BNode* ptr, int pos, const ElemType& item, BNode* right)
{
	for (int i = ptr->num; i > pos; --i)
	{
		ptr->data[i + 1] = ptr->data[i];
		ptr->sub[i + 1] = ptr->sub[i];
	}
	ptr->data[pos + 1] = item;
	ptr->sub[pos + 1] = right;	 // right->parent;
	ptr->num += 1;
}
BNode* Splice(BNode* ptr)
{
	BNode* s = Buynode();
	ElemType item = Move_Item(s, ptr, MINSIZE);
	if (ptr->parent == nullptr)
	{
		return MakeRoot(item, ptr, s);
	}

	BNode* pa = ptr->parent;
	int pos = pa->num;
	pa->data[0] = item; //
	while (pos > 0 && item.key < pa->data[pos].key) { --pos; }
	Insert_Item(pa, pos, item, s);
	if (pa->num > MAXSIZE)
	{
		return Splice(pa);
	}
	else
	{
		return nullptr;
	}
}

bool Insert(BTree& tree, const ElemType& item)
{
	if (tree.root == nullptr)
	{
		tree.root = MakeRoot(item, nullptr, nullptr);
		tree.cursize = 1;
		return true;
	}
	Result res = FindKey(tree, item.key);
	if (res.pnode != nullptr && res.tag)  return false;
	BNode* ptr = res.pnode;
	int pos = res.index;
	Insert_Item(ptr, pos, item, nullptr); //

	if (ptr->num > MAXSIZE)
	{
		BNode* newroot = Splice(ptr);
		if (newroot != nullptr)
		{
			tree.root = newroot;
		}
	}
	tree.cursize += 1;
	return true;

}

B-树删除 情况分析

对于B-树的删除来说；可以分为以下几种情况讨论；

case1：删除的关键码是叶子结点x，并且num>minsize时，如图；

 这种直接删除即可;

case2：删除的关键码是非叶子Q时，如图：

 找到该节点的直接前驱，交换后删除叶子结点，

BNode* FindPrev(BNode* ptr, int pos)
{
	BNode* p = ptr->sub[pos];
	while (p != nullptr && p->sub[p->num])
	{
		p = p->sub[p->num];
	}
	return p;
}

 如果直接前驱没有，则找到直接后继节点如图：

BNode* FindNext(BNode* ptr, int pos)
{
	BNode* p = ptr->sub[pos];
	while (p != nullptr && p->sub[0] != nullptr)
	{
		p = p->sub[0];
	}
	return p;
}
case3：删除后如果num小minsize则需要修改树的结构；右满足；

如果右兄弟满足num大于minsize，则进行转移，将右兄弟的值转移，使其可以满足b-树性质；如图：

case4：删除后如果num小minsize则需要修改树的结构；左满足；

 case5：当两边都不满足时，如果有右兄弟则进行合并；

case6：当两边都不满足且右孩子为空，则进行和左兄弟合并

 相关代码： 
bool Delete_Leaf(BNode* ptr, int pos)
{
		for (int i = ptr->num; i >pos; --i)
		{
			ptr->data[i - 1] = ptr->data[i];
		}
		ptr->num -= 1;
		return true;
}
BNode* Meger_Leaf(BNode* ptr)
{
	BNode* par = ptr->parent;
	int flag= 0,j=ptr->num;
	for (flag; flag <= par->num+1; ++flag)//找到该节点
	{
		if (par->sub[flag] == ptr)
			break;
	}
	if (par->sub[flag+1]!=nullptr)//抓住右兄弟
	{
		BNode* Brt_righ = par->sub[flag + 1];
		if (Brt_righ->num > MINSIZE)
		{
			ptr->data[j+1]=par->data[flag];
			  par->data[flag]=Brt_righ->data[1];
			for (int j = Brt_righ->num; j >= 0; --j)
			{
				Brt_righ->data[j - 1] = Brt_righ->data[j];//向前移动
			}
			Brt_righ->num -= 1;
			ptr->num += 1;
		}
		else
		{
			ptr->data[j+1] = par->data[flag];
			ptr->num += 1;
			for (int i = Brt_righ->num; i > 0; i--)
			{
				ptr->data[j + 1] = Brt_righ->data[i];
				ptr->num += 1;
			}
			free(right);
			par->num--;
			par->sub[flag + 1] = nullptr;
			for (int i = par->num; i > flag; --i)
			{
				par->data[i - 1] = par->data[i];
				par->sub[i - 1] = par->sub[i];
			}
		}
		return ptr;
	}
	else if (par->num>=1&&par->sub[flag-1] != nullptr)//看有没有左兄弟
	{
		BNode* Brt_left = par->sub[flag - 1];
		if (Brt_left->num > MINSIZE)
		{
			ptr->data[MINSIZE] = par->data[flag];
			Brt_left->data[Brt_left->num] = par->data[flag];
			Brt_left->num -= 1;
			return ptr;
		}
		else
		{
			j = Brt_left->num;
			if (flag == 1)
			{
				Brt_left->data[j + 1] = par->data[flag - 1];
			}
			else
			{
				Brt_left->data[j+1] = par->data[flag];
			}
			Brt_left->num += 1;
			for (int i = ptr->num; i > 0; i--)
			{
				Brt_left->data[j + 1] = ptr->data[i];
				Brt_left->num += 1;
			}
			free(ptr);
			par->sub[flag] = nullptr;
			par->num -= 1;
			return Brt_left;
		}
		
	}
	return nullptr;
}
bool Remove(BTree& tree, KeyType kx)
{
	Result res = FindKey(tree, kx);
	if (res.pnode == nullptr || !res.tag)return false;
	BNode* ptr = res.pnode;
	int pos = res.index;
	BNode* pre = FindPrev(ptr, pos - 1);
	BNode* nt = FindNext(ptr, pos);
	if (pre != nullptr && pre->num > MINSIZE)
	{
		ptr->data[pos] = pre->data[pre->num];
		ptr = pre;
		pos = pre->num;
	}
	else if (nt != nullptr && nt->num > MINSIZE)
	{
		ptr->data[pos] = nt->data[1];
		ptr = nt;
		pos = 1;
	}
	else if (pre != nullptr)
	{
		ptr->data[pos]=pre->data[pre->num] ;
		ptr = pre;
		pos = pre->num;
	}
	Delete_Leaf(ptr, pos);
	if (ptr->parent == nullptr && ptr->num == 0)
	{
		free(ptr);
		tree.root = nullptr;
	}
	else if (ptr->num < MINSIZE)
	{
		BNode* newroot = Meger_Leaf(ptr);
		if (newroot != nullptr)
		{
			tree.root = newroot;
		}
	}
	return true;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1499124.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
dsp公司 dsp公司 一级用户组
0 0
上一篇 2022-06-25
下一篇 2022-06-25

发表评论

登录后才能评论

评论列表（0条）

保存