标签搜索

目 录CONTENT

文章目录

B-、B树详解及模拟实现.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 10 阅读 / 5,382 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

B-、B树详解及模拟实现

@[toc]

一、B-树

B-树就是B树

二、B树

1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是 一种平衡的多叉树

1.性质

(关键字就是存储的数据)

一棵M阶B树(balanced tree of order m)是一棵平衡的M路搜索树。它或者是空树,或者是满足 下列性质 的树:

  •  1.定义任意非叶子结点最多只有M个儿子;且M>2;
  •  2.根结点的儿子数为[2, M];
  •  3.除根结点以外的非叶子结点的儿子数为[M/2,M];
  •  4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字
  •  5.非叶子结点的关键字个数=指向儿子的指针个数-1;
  •  6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];即2从左往右是递增的
  •  7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
  •  8.所有叶子结点位于同一层;

如:M == 3
在这里插入图片描述

B树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束否则进入查询关键字所属范围的儿子结点;重复直到所对应的儿子指针为空,或已经是叶子结点;

2.特性解释

B树的特性:

  •  1.关键字(数据)集合分布在整颗树中;

  •  2.任何一个关键字出现且只出现在一个结点中;

  •  3.搜索有可能在非叶子结点结束;

  •  4.其搜索性能等价于在关键字全集内做一次二分查找;

  •  5.自动层次控制;

  •  6.仍然遵循跟节点的左子树的值都比跟节点的值小,跟节点右子树的值都比跟节点大

  •  7.一个节点有多个关键字、有多个孩子,但是每个节点的孩子数量始终比关键字的数量多1个(因为对于每个关键字都有左右指针)

  •  8.跟节点的关键字数量[1,m - 1],孩子数量[2,m]

  •  9.M阶就代表最多有M个孩子,也就是M叉树

  •  10.非跟节点关键字的数量[M / 2 - 1,M - 1],孩子的数量[M / 2,M],(M / 2向上取整)

  •  由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:

在这里插入图片描述

其中,M为设定的非叶子结点最多子树个数,N为关键字总数
所以B树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;
由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;

3.B树的插入操作

  •  步骤:

  • 1、插入一个元素时,首先在B树中是否存在如果不存在,即比较大小寻找插入位置,在叶子结点处结束,然后在叶子结点中插入该新的元素

  • 2、如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行“分裂”将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要“分裂”操作)

  • 3、当结点中关键元素向右移动了,相关的指针也需要向右移。如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层

  •  下面以5阶B树为例,介绍B树的插入操作,在5阶B树中,非跟结点最多有4个key,最少有2个key

  •  a)在空树中插入39
    在这里插入图片描述
    此时根结点就一个key,此时根结点也是叶子结点

  •  b)继续插入22,97和41
    在这里插入图片描述
    根结点此时有4个key

  •  c)继续插入53
    在这里插入图片描述

插入后超过了最大允许的关键字个数4,所以以key值为41为中心进行分裂,结果如下图所示,分裂后当前结点指针指向父结点,满足B树条件,插入操作结束。当阶数m为偶数时,需要分裂时就不存在排序恰好在中间的key,那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。

在这里插入图片描述

  •  d)依次插入13,21,40,同样会造成分裂,结果如下图所示。

在这里插入图片描述

  •  e)依次插入30,27, 33 ;36,35,34 ;24,29,结果如下图所示。
    在这里插入图片描述

  •  f)插入key值为26的记录,插入后的结果如下图所示。
    在这里插入图片描述

  •  当前结点需要以27为中心分裂,并向父结点进位27,然后当前结点指向父结点,结果如下图所示。
    在这里插入图片描述

  •  进位后导致当前结点(即根结点)也需要分裂,分裂的结果如下图所示。
    在这里插入图片描述
    分裂后当前结点指向新的根,此时无需调整。

  •  g)最后再依次插入key为17,28,29,31,32的记录,结果如下图所示。
    在这里插入图片描述

4. B树的删除操作

  •  删除操作是指,根据key删除记录,如果B树中的记录中不存对应key的记录,则删除失败。

  • 1)如果当前需要删除的key位于非叶子结点上,则用后继key(这里的后继key均指后继记录的意思)覆盖要删除的key,然后在后继key所在的子支中删除该后继key此时后继key一定位于叶子结点上,这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

  • 2)该结点key个数大于等于Math.ceil(m / 2) - 1,结束删除操作,否则执行第3步

  • 3)如果兄弟结点key个数大于Math.ceil(m / 2) - 1,则父结点中的key下移到该结点,兄弟结点中的一个key上移,删除操作结束

  • 否则,将父结点中的key下移与当前结点及它的兄弟结点中的key合并,形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针,指向这个新结点。然后当前结点的指针指向父结点,重复上第2步。

有些结点它可能即有左兄弟,又有右兄弟,那么我们任意选择一个兄弟结点进行操作即可。

  •  下面以5阶B树为例,介绍B树的删除操作,5阶B树中,结点最多有4个key,最少有2个key
  •  a)原始状态
    在这里插入图片描述
  •  b)在上面的B树中删除21,删除后结点中的关键字个数仍然大于等2,所以删除结束。
    在这里插入图片描述
  •  c)在上述情况下接着删除27。从上图可知27位于非叶子结点中,所以用27的后继替换它。从图中可以看出,27的后继为28,我们用28替换27,然后在28(原27)的右孩子结点中删除28。删除后的结果如下图所示。
    在这里插入图片描述
  •  删除后发现,当前叶子结点的记录的个数小于2,而它的兄弟结点中有3个记录(当前结点还有一个右兄弟,选择右兄弟就会出现合并结点的情况,不论选哪一个都行,只是最后B树的形态会不一样而已),我们可以从兄弟结点中借取一个key。所以父结点中的28下移,兄弟结点中的26上移,删除结束。结果如下图所示。

在这里插入图片描述

  •  d)在上述情况下接着32,结果如下图。
    在这里插入图片描述
  •  当删除后,当前结点中只有1个key,而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并,成为一个新的结点,当前结点的指针指向父结点。结果如下图所示。

在这里插入图片描述
当前结点key的个数满足条件,故删除结束。

  •  e)上述情况下,我们接着删除key为40的记录,删除后结果如下图所示。
    在这里插入图片描述
  •  同理,当前结点的记录数小于2,兄弟结点中没有多余key,所以父结点中的key下移,和兄弟(这里我们选择左兄弟,选择右兄弟也可以)结点合并,合并后的指向当前结点的指针就指向了父结点。
    在这里插入图片描述
  •  同理,对于当前结点而言只能继续合并了,最后结果如下所示。
    在这里插入图片描述
    合并后结点当前结点满足条件,删除结束。

5.B树摸拟实现

#include<iostream>
using namespace std;
 
template<class K,int M=3>
struct BTreeNode
{
	BTreeNode()
	:_pParent(NULL)
	, _size(0)
	{
		for (size_t i = 0; i <= M; i++)
		{
			_pSub[i] = NULL;
		}
	}
 
	K _key[M];
	BTreeNode<K, M> *_pSub[M + 1];
	BTreeNode<K, M> *_pParent;
	size_t _size;
};
 
template<class K,int M=3>
class BTree
{
	typedef BTreeNode<K, M> Node;
	typedef Node* pNode;
public:
	BTree()
		:_pRoot(NULL)
	{}
 
	bool Insert(K& key)
	{
		if (_pRoot == NULL)//无根节点
		{
			_pRoot = new Node();
			_pRoot->_key[0] = key;
			_pRoot->_size = 1;
			return true;
		}
 
		pair<pNode, int> ret = Find(key);
		if (ret.second >= 0)
			return false;
		pNode pCur = ret.first;
		pNode pSub = NULL;
		while (1)
		{
			_Insert(pCur, key, pSub);
			size_t size = pCur->_size;
			if (size < M)
				return true;
			else
			{
				size_t mid = size >> 1;
				pNode tmp = new Node();
				for (size_t i= mid + 1; i < size; i++)
				{
					tmp->_key[tmp->_size] = pCur->_key[i];
					tmp->_pSub[tmp->_size] = pCur->_pSub[i];
					if (tmp->_pSub[tmp->_size])
						tmp->_pSub[tmp->_size]->_pParent = tmp;
					tmp->_size++;
				}
				tmp->_pSub[tmp->_size] = pCur->_pSub[pCur->_size];
 
				if (tmp->_pSub[tmp->_size])
					tmp->_pSub[tmp->_size]->_pParent = tmp;
				pCur->_size -= (tmp->_size + 1); //处理size
 
				if (pCur == _pRoot)//如果当前结点是根结点,还需要再处理
				{
					_pRoot = new Node;
					_pRoot->_key[0] = pCur->_key[mid];
					_pRoot->_pSub[0] = pCur;
					pCur->_pParent = _pRoot;
					_pRoot->_pSub[1] = tmp;
					tmp->_pParent = _pRoot;
					_pRoot->_size = 1;
					return true;
				}
				else
				{
					key = pCur->_key[mid];
					pCur = pCur->_pParent;
					pSub = tmp;
				}
			}
		}
	}
 
	pair<pNode, int> Find(const K& key)
	{
		pNode pCur = _pRoot;
		pNode pParent = NULL;
 
		while (pCur)
		{
			size_t i = 0;
			while (i < pCur->_size)
			{
				if (key == pCur->_key[i])
					return pair<pNode, int>(pCur, i);
				else if (key < pCur->_key[i])
					break;
				else
					i++;
			}
			pParent = pCur;
			pCur = pCur->_pSub[i];
		}
		return make_pair(pParent, -1);//没找到返回-1
	}
private:
	void _Insert(pNode pCur, const K& key, pNode pSub)
	{
		//直接插入的思想
		int end = pCur->_size - 1;
		while (key < pCur->_key[end] && end >= 0)
		{
			pCur->_key[end + 1] = pCur->_key[end];
			pCur->_pSub[end + 2] = pCur->_pSub[end + 1];
			end--;
		}
 
		pCur->_key[end + 1] = key;
		pCur->_pSub[end + 2] = pSub;
		if (pSub)
			pSub->_pParent = pCur;
		pCur->_size += 1;
	}
private:
	Node *_pRoot;
};
 
int main()
{
	int arr[] = { 53, 75, 139, 49, 145, 36, 101 };
	
	BTree<int> b;
	size_t size = sizeof(arr) / sizeof(arr[0]);
	for (size_t i = 0; i < 7; i++)
		b.Insert(arr[i]);

	return 0;
}
0

评论区