B-樹：

創(chuàng)新互聯(lián)建站主營(yíng)西吉網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,成都App定制開發(fā),西吉h5微信小程序搭建,西吉網(wǎng)站營(yíng)銷推廣歡迎西吉等地區(qū)企業(yè)咨詢

    一種適合外查找的平衡多叉樹（有些地方寫的是B-樹，注意不要誤讀 成"B減樹"） 。

M階的B樹滿足如下性質(zhì)：

    1、根節(jié)點(diǎn)至少有兩個(gè)孩子；

    2、每個(gè)非根節(jié)點(diǎn)有[[M/2],M]個(gè)孩子；

    3、每個(gè)非根節(jié)點(diǎn)有[[M/2],M-1]個(gè)關(guān)鍵字，并且以升序排列；

    4、key[i]和key[i+1]之間的孩子節(jié)點(diǎn)的值介于key[i]和key[i+1]之間；

    5、所有的葉子節(jié)點(diǎn)都在同一層。

M階的B樹----M=3

 插入：

        如果插入值后，該節(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)大于規(guī)定的要求，則需要調(diào)整，即分裂（新創(chuàng)建一個(gè)節(jié)點(diǎn)，把位于關(guān)鍵字序列中的中位數(shù)（不包含中位數(shù)）以后的值包括子樹都拷貝到新建的節(jié)點(diǎn)中，將中位數(shù)提出成樹的根節(jié)點(diǎn)，中位數(shù)以前的值將成為中位數(shù)的左子樹，后半部分成為右子樹），如下圖：

應(yīng)用：運(yùn)用于數(shù)據(jù)庫(kù)和文件系統(tǒng)。

具體實(shí)現(xiàn)代碼如下：

#pragma once

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

//性質(zhì)：

//   1、根節(jié)點(diǎn)至少有兩個(gè)孩子

//   2、每個(gè)非根節(jié)點(diǎn)有[[M/2],M]個(gè)孩子

//   3、每個(gè)非根節(jié)點(diǎn)有[[M/2],M-1]個(gè)關(guān)鍵字，并且以升序排列

//   4、key[i]和key[i+1]之間的孩子節(jié)點(diǎn)的值介于key[i]和key[i+1]之間

//   5、所有的葉子節(jié)點(diǎn)都在同一層

template<class K,int M>//B數(shù)一個(gè)節(jié)點(diǎn)的結(jié)構(gòu)

struct BTreeNode

{

K _key[M];//關(guān)鍵字的個(gè)數(shù)為M-1，多留一個(gè)位置可以更加方便的求取中位數(shù)

BTreeNode<K,M>* _subs[M+1];//方便插入時(shí)分裂，子樹的大個(gè)數(shù)為M個(gè)，關(guān)鍵字比他少一個(gè)

BTreeNode<K,M>* _parent;//指向父親節(jié)點(diǎn)

size_t _size;//數(shù)組中存放的有效關(guān)鍵字的個(gè)數(shù)

BTreeNode()

:_parent(NULL)

,_size(0)

{

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

{

_subs[i] = NULL;

}

}

};

template<class K,class V>//需要返回兩個(gè)參數(shù)，使用結(jié)構(gòu)體

struct Pair

{

K _first;

V _second;

Pair(const K& key = K(),const V& value = V())//缺省參數(shù)，會(huì)調(diào)用默認(rèn)構(gòu)造函數(shù)

:_first(key)

,_second(value)

{ }

};

template<class K,int M>

class BTree

{

typedef BTreeNode<K,M> Node;

public:

BTree()

:_root(NULL)

{ }

Pair<Node*,int> Find(const K& key)//查找

{

if(_root == NULL)

return Pair<Node*,int>(NULL,-1);

Node* parent = NULL;

Node* cur = _root;

while (cur)

{

int index = 0;

while (index < cur->_size)

{

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

{

return Pair<Node*,int>(cur,index);

}

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

{

break;

}

else

{

index++;

}

}

parent = cur;

cur = cur->_subs[index];

}

return Pair<Node* ,int>(parent,-1);

//找完也沒找到，為了使得該情況下方便插入節(jié)點(diǎn)，因此返回panrent，插入節(jié)點(diǎn)插入在parent上

}

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

{

//當(dāng)前無(wú)節(jié)點(diǎn)

if(_root == NULL)

{

_root = new Node;//開辟一個(gè)新的節(jié)點(diǎn)

_root->_key[0] = key;

_root->_subs[0] = NULL;

_root->_parent = NULL;

_root->_size++;

return true;

}

Pair<Node*,int> cur = Find(key);

if(cur._second != -1)//找到，則返回false，不插入重復(fù)關(guān)鍵字

{

return false;

}

//在節(jié)點(diǎn)cur中插入key和sub

Node* str = cur._first;

K newKey = key;

Node* sub = NULL;

while (1)

{

_InsertKey(str,newKey,sub);

if(str->_size < M)//關(guān)鍵字的數(shù)量小于M，則正確，直接返回

return true;

//插入數(shù)據(jù)后，該節(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)大于規(guī)定的數(shù)量，需要調(diào)整，進(jìn)行分裂

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

int index = 0;

Node* temp = new Node;

//先拷貝下標(biāo)為mid后的關(guān)鍵字

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

{

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

temp->_size++;

str->_key[i] = 0;

}

//接著拷貝下標(biāo)為mid的關(guān)鍵字的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<<endl;

}

protected:

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

{

int index = cur->_size - 1;

while (index >= 0 && cur->_key[index] > key)//若插入的節(jié)點(diǎn)比改位置的值小，則需要移位

{

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<<root->_key[i]<<" ";

}

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

}

protected:

Node* _root;

};

void BTreeTest()

{

BTree<int,3> 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();

}

運(yùn)行結(jié)果：

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站欄目：平衡搜索樹之B-樹-創(chuàng)新互聯(lián)
文章來(lái)源：http://aaarwkj.com/article2/ppjic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營(yíng)銷型網(wǎng)站建設(shè)、定制開發(fā)、企業(yè)網(wǎng)站制作、全網(wǎng)營(yíng)銷推廣、標(biāo)簽優(yōu)化、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)