资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

平衡搜索树之B-树-创新互联

B-树:

创新互联建站主营西吉网站建设的网络公司,主营网站建设方案,成都App定制开发,西吉h5微信小程序搭建,西吉网站营销推广欢迎西吉等地区企业咨询

    一种适合外查找的平衡多叉树(有些地方写的是B-树,注意不要误读 成"B减树") 。

M阶的B树满足如下性质:

    1、根节点至少有两个孩子;

    2、每个非根节点有[[M/2],M]个孩子;

    3、每个非根节点有[[M/2],M-1]个关键字,并且以升序排列;

    4、key[i]和key[i+1]之间的孩子节点的值介于key[i]和key[i+1]之间;

    5、所有的叶子节点都在同一层。

M阶的B树----M=3

平衡搜索树之B-树

 插入:

        如果插入值后,该节点的关键字的个数大于规定的要求,则需要调整,即分裂(新创建一个节点,把位于关键字序列中的中位数(不包含中位数)以后的值包括子树都拷贝到新建的节点中,将中位数提出成树的根节点,中位数以前的值将成为中位数的左子树,后半部分成为右子树),如下图:平衡搜索树之B-树

应用:运用于数据库和文件系统。

具体实现代码如下:

#pragma once

//使用外查找的平衡多叉树

//性质:

//   1、根节点至少有两个孩子

//   2、每个非根节点有[[M/2],M]个孩子

//   3、每个非根节点有[[M/2],M-1]个关键字,并且以升序排列

//   4、key[i]和key[i+1]之间的孩子节点的值介于key[i]和key[i+1]之间

//   5、所有的叶子节点都在同一层

template//B数一个节点的结构

struct BTreeNode

{

K _key[M];//关键字的个数为M-1,多留一个位置可以更加方便的求取中位数

BTreeNode* _subs[M+1];//方便插入时分裂,子树的大个数为M个,关键字比他少一个

BTreeNode* _parent;//指向父亲节点

size_t _size;//数组中存放的有效关键字的个数

BTreeNode()

:_parent(NULL)

,_size(0)

{

for(int i = 0;i < M+1;++i)

{

_subs[i] = NULL;

}

}

};

template//需要返回两个参数,使用结构体

struct Pair

{

K _first;

V _second;

Pair(const K& key = K(),const V& value = V())//缺省参数,会调用默认构造函数

:_first(key)

,_second(value)

{ }

};

template

class BTree

{

typedef BTreeNode Node;

public:

BTree()

:_root(NULL)

{ }

Pair Find(const K& key)//查找

{

if(_root == NULL)

return Pair(NULL,-1);

Node* parent = NULL;

Node* cur = _root;

while (cur)

{

int index = 0;

while (index < cur->_size)

{

if(key == cur->_key[index])

{

return Pair(cur,index);

}

else if(key < cur->_key[index])

{

break;

}

else

{

index++;

}

}

parent = cur;

cur = cur->_subs[index];

}

return Pair(parent,-1);

//找完也没找到,为了使得该情况下方便插入节点,因此返回panrent,插入节点插入在parent上

}

bool Insert(const K& key)//插入

{

//当前无节点

if(_root == NULL)

{

_root = new Node;//开辟一个新的节点

_root->_key[0] = key;

_root->_subs[0] = NULL;

_root->_parent = NULL;

_root->_size++;

return true;

}

Pair cur = Find(key);

if(cur._second != -1)//找到,则返回false,不插入重复关键字

{

return false;

}

//在节点cur中插入key和sub

Node* str = cur._first;

K newKey = key;

Node* sub = NULL;

while (1)

{

_InsertKey(str,newKey,sub);

if(str->_size < M)//关键字的数量小于M,则正确,直接返回

return true;

//插入数据后,该节点的关键字的个数大于规定的数量,需要调整,进行分裂

int mid = (str->_size - 1)/2;

int index = 0;

Node* temp = new Node;

//先拷贝下标为mid后的关键字

for(size_t i = mid + 1;i < str->_size;i++)

{

temp->_key[index++] = str->_key[i];

temp->_size++;

str->_key[i] = 0;

}

//接着拷贝下标为mid的关键字的sub

index = 0;

for(size_t i = mid + 1;i <= str->_size;i++)

{

temp->_subs[index++] = str->_subs[i];

if(str->_subs[i] != NULL)

str->_subs[i]->_parent = temp;

}

//更改str的大小

str->_size = (str->_size - 1)/2;

if(str->_parent == NULL)

{

_root = new Node;

_root->_key[0] = str->_key[mid];

str->_key[mid] = 0;

_root->_subs[0] = str;

_root->_subs[1] = temp;

_root->_size = 1;

str->_parent = _root;

temp->_parent = _root;

return true;

}

else

{

newKey = str->_key[mid];

str->_key[mid] = 0;

sub = temp;

str = str->_parent;

}

}

}

void InOrder()

{

_InOrder(_root);

cout<

}

protected:

void _InsertKey(Node* cur,const K& key,Node* sub)

{

int index = cur->_size - 1;

while (index >= 0 && cur->_key[index] > key)//若插入的节点比改位置的值小,则需要移位

{

cur->_key[index+1] = cur->_key[index];

cur->_subs[index+2] = cur->_subs[index+1];

--index;

}

//否则,直接插入

cur->_key[index + 1] = key;

cur->_subs[index+2] = sub;

if(sub != NULL)

sub->_parent = cur;

cur->_size++;

}

void _InOrder(Node* root)

{

if(root == NULL)

return;

for(int i = 0;i < root->_size;i++)

{

_InOrder(root->_subs[i]);

cout<_key[i]<<" ";

}

_InOrder(root->_subs[root->_size]);

}

protected:

Node* _root;

};

void BTreeTest()

{

BTree tree;

int a[] = {53,75,139,49,145,36,101};

for(int i = 0;i < sizeof(a)/sizeof(a[i]);i++)

{

tree.Insert(a[i]);

}

tree.InOrder();

}

运行结果:

平衡搜索树之B-树

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


本文名称:平衡搜索树之B-树-创新互联
转载来源:http://www.cdkjz.cn/article/ppjic.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220