2-3-4樹和B樹


比如構造如下的2-3-4樹。



下面要刪除1和6。


刪除後如下圖所示:



下面刪除元素3



刪除元素4



下面是B樹


一個m階的B樹具有如下屬性:

如果根結點不是葉結點,則其至少有兩棵子樹

每一個非根的分支結點都有k-1個元素(關鍵字)和k個孩子,其中k滿足:⌈m/2⌉ <= k <= m

所有葉子結點都位於同一層次

每一個分支結點包含下列信息數據:

n, A₀, K₁, A₁, K₂, A₂, K₃, A₃……

其中K為關鍵字,且Ki < Ki+1

Ai為指向子樹根結點的指針


如下圖所示:



btree.h


//實現對order序(階)的B-TREE結構基本操作的封裝。
//查找:search,插入:insert,刪除:remove。
//創建:create,銷毀:destory,打印:print。
#ifndef BTREE_H
#define BTREE_H

#ifdef __cplusplus
extern "C" {
#endif

////* 定義m序(階)B 樹的最小度數BTree_D=ceil(m)*/
/// 在這裡定義每個節點中關鍵字的最大數目為:2 * BTree_D - 1,即序(階):2 * BTree_D.
#define BTree_D 2
#define ORDER (BTree_D * 2) //定義為4階B-tree,2-3-4樹。最簡單為3階B-tree,2-3樹。
//#define ORDER (BTree_T * 2-1) //最簡單為3階B-tree,2-3樹。

typedef int KeyType;
typedef struct BTNode{
int keynum; /// 結點中關鍵字的個數,keynum <= BTree_N
KeyType key[ORDER-1]; /// 關鍵字向量為key[0..keynum - 1]
struct BTNode* child[ORDER]; /// 孩子指針向量為child[0..keynum]
bool isLeaf; /// 是否是葉子節點的標志
}BTNode;

typedef BTNode* BTree; ///定義BTree

///給定數據集data,創建BTree。
void BTree_create(BTree* tree, const KeyType* data, int length);

///銷毀BTree,釋放內存空間。
void BTree_destroy(BTree* tree);

///在BTree中插入關鍵字key。
void BTree_insert(BTree* tree, KeyType key);

///在BTree中移除關鍵字key。
void BTree_remove(BTree* tree, KeyType key);

///深度遍歷BTree打印各層結點信息。
void BTree_print(const BTree tree, int layer=1);

/// 在BTree中查找關鍵字 key,
/// 成功時返回找到的節點的地址及 key 在其中的位置 *pos
/// 失敗時返回 NULL 及查找失敗時掃描到的節點位置 *pos
BTNode* BTree_search(const BTree tree, int key, int* pos);

#ifdef __cplusplus
}
#endif

#endif

btree.c


//代碼來自(該文章有細致講解):http://blog.csdn.net/v_july_v/article/details/6735293
//實現對order序(階)的B-TREE結構基本操作的封裝。
//查找:search,插入:insert,刪除:remove。
//創建:create,銷毀:destory,打印:print。
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "btree.h"

//#define max(a, b) (((a) > (b)) ? (a) : (b))
#define cmp(a, b) ( ( ((a)-(b)) >= (0) ) ? (1) : (0) ) //比較a,b大小
#define DEBUG_BTREE

// 模擬向磁盤寫入節點
void disk_write(BTNode* node)
{
//打印出結點中的全部元素,方便調試查看keynum之後的元素是否為0(即是否存在垃圾數據);而不是keynum個元素。
printf("向磁盤寫入節點");
for(int i=0;i<ORDER-1;i++){
printf("%c",node->key[i]);
}
printf("\n");
}

// 模擬從磁盤讀取節點
void disk_read(BTNode** node)
{
//打印出結點中的全部元素,方便調試查看keynum之後的元素是否為0(即是否存在垃圾數據);而不是keynum個元素。
printf("向磁盤讀取節點");
for(int i=0;i<ORDER-1;i++){
printf("%c",(*node)->key[i]);
}
printf("\n");
}

// 按層次打印 B 樹
void BTree_print(const BTree tree, int layer)
{
int i;
BTNode* node = tree;

if (node) {
printf("第 %d 層, %d node : ", layer, node->keynum);

//打印出結點中的全部元素,方便調試查看keynum之後的元素是否為0(即是否存在垃圾數據);而不是keynum個元素。
for (i = 0; i < ORDER-1; ++i) {
//for (i = 0; i < node->keynum; ++i) {
printf("%c ", node->key[i]);
}

printf("\n");

++layer;
for (i = 0 ; i <= node->keynum; i++) {
if (node->child[i]) {
BTree_print(node->child[i], layer);
}
}
}
else {
printf("樹為空。\n");
}
}

// 結點node內對關鍵字進行二分查找。
int binarySearch(BTNode* node, int low, int high, KeyType Fkey)
{
int mid;
while (low<=high)
{
mid = low + (high-low)/2;
if (Fkey<node->key[mid])
{
high = mid-1;
}
if (Fkey>node->key[mid])
{
low = mid+1;
}
if (Fkey==node->key[mid])
{
return mid;//返回下標。
}
}
return 0;//未找到返回0.
}

//insert
/***************************************************************************************
將分裂的結點中的一半元素給新建的結點,並且將分裂結點中的中間關鍵字元素上移至父節點中。
parent 是一個非滿的父節點
node 是 tree 孩子表中下標為 index 的孩子節點,且是滿的,需分裂。
*******************************************************************/
void BTree_split_child(BTNode* parent, int index, BTNode* node)
{
#ifdef DEBUG_BTREE
printf("BTree_split_child!\n");
#endif
assert(parent && node);
int i;

// 創建新節點,存儲 node 中後半部分的數據
BTNode* newNode = (BTNode*)calloc(sizeof(BTNode), 1);
if (!newNode) {
printf("Error! out of memory!\n");
return;
}

newNode->isLeaf = node->isLeaf;
newNode->keynum = BTree_D - 1;

// 拷貝 node 後半部分關鍵字,然後將node後半部分置為0。
for (i = 0; i < newNode->keynum; ++i){
newNode->key[i] = node->key[BTree_D + i];
node->key[BTree_D + i] = 0;
}

// 如果 node 不是葉子節點,拷貝 node 後半部分的指向孩子節點的指針,然後將node後半部分指向孩子節點的指針置為NULL。
if (!node->isLeaf) {
for (i = 0; i < BTree_D; i++) {
newNode->child[i] = node->child[BTree_D + i];
node->child[BTree_D + i] = NULL;
}
}

// 將 node 分裂出 newNode 之後,裡面的數據減半
node->keynum = BTree_D - 1;

// 調整父節點中的指向孩子的指針和關鍵字元素。分裂時父節點增加指向孩子的指針和關鍵元素。
for (i = parent->keynum; i > index; --i) {
parent->child[i + 1] = parent->child[i];
}

parent->child[index + 1] = newNode;

for (i = parent->keynum - 1; i >= index; --i) {
parent->key[i + 1] = parent->key[i];
}

parent->key[index] = node->key[BTree_D - 1];
++parent->keynum;

node->key[BTree_D - 1] = 0;

// 寫入磁盤
disk_write(parent);
disk_write(newNode);
disk_write(node);
}

void BTree_insert_nonfull(BTNode* node, KeyType key)
{
assert(node);

int i;

// 節點是葉子節點,直接插入
if (node->isLeaf) {
i = node->keynum - 1;
while (i >= 0 && key < node->key[i]) {
node->key[i + 1] = node->key[i];
--i;
}

node->key[i + 1] = key;
++node->keynum;

// 寫入磁盤
disk_write(node);
}

// 節點是內部節點
else {
/* 查找插入的位置*/
i = node->keynum - 1;
while (i >= 0 && key < node->key[i]) {
--i;
}

++i;

// 從磁盤讀取孩子節點
disk_read(&node->child[i]);

// 如果該孩子節點已滿,分裂調整值
if (node->child[i]->keynum == (ORDER-1)) {
BTree_split_child(node, i, node->child[i]);
// 如果待插入的關鍵字大於該分裂結點中上移到父節點的關鍵字,在該關鍵字的右孩子結點中進行插入操作。
if (key > node->key[i]) {
++i;
}
}
BTree_insert_nonfull(node->child[i], key);
}
}

void BTree_insert(BTree* tree, KeyType key)
{
#ifdef DEBUG_BTREE
printf("BTree_insert:\n");
#endif
BTNode* node;
BTNode* root = *tree;

// 樹為空
if (NULL == root) {
root = (BTNode*)calloc(sizeof(BTNode), 1);
if (!root) {
printf("Error! out of memory!\n");
return;
}
root->isLeaf = true;
root->keynum = 1;
root->key[0] = key;

*tree = root;

// 寫入磁盤
disk_write(root);

return;
}

// 根節點已滿,插入前需要進行分裂調整
if (root->keynum == (ORDER-1)) {
// 產生新節點當作根
node = (BTNode*)calloc(sizeof(BTNode), 1);
if (!node) {
printf("Error! out of memory!\n");
return;
}

*tree = node;
node->isLeaf = false;
node->keynum = 0;
node->child[0] = root;

BTree_split_child(node, 0, root);

BTree_insert_nonfull(node, key);
}

// 根節點未滿,在當前節點中插入 key
else {
BTree_insert_nonfull(root, key);
}
}
//remove
// 對 tree 中的節點 node 進行合並孩子節點處理.
// 註意:孩子節點的 keynum 必須均已達到下限,即均等於 BTree_D - 1
// 將 tree 中索引為 index 的 key 下移至左孩子結點中,
// 將 node 中索引為 index + 1 的孩子節點合並到索引為 index 的孩子節點中,右孩子合並到左孩子結點中。
// 並調相關的 key 和指針。</p>void BTree_merge_child(BTree* tree, BTNode* node, int index)
{
#ifdef DEBUG_BTREE
printf("BTree_merge_child!\n");
#endif
assert(tree && node && index >= 0 && index < node->keynum);

int i;

KeyType key = node->key[index];
BTNode* leftChild = node->child[index];
BTNode* rightChild = node->child[index + 1];

assert(leftChild && leftChild->keynum == BTree_D - 1
&& rightChild && rightChild->keynum == BTree_D - 1);

// 將 node中關鍵字下標為index 的 key 下移至左孩子結點中,該key所對應的右孩子結點指向node的右孩子結點中的第一個孩子。
leftChild->key[leftChild->keynum] = key;
leftChild->child[leftChild->keynum + 1] = rightChild->child[0];
++leftChild->keynum;

// 右孩子的元素合並到左孩子結點中。
for (i = 0; i < rightChild->keynum; ++i) {
leftChild->key[leftChild->keynum] = rightChild->key[i];
leftChild->child[leftChild->keynum + 1] = rightChild->child[i + 1];
++leftChild->keynum;
}

// 在 node 中下移的 key後面的元素前移
for (i = index; i < node->keynum - 1; ++i) {
node->key[i] = node->key[i + 1];
node->child[i + 1] = node->child[i + 2];
}
node->key[node->keynum - 1] = 0;
node->child[node->keynum] = NULL;
--node->keynum;

// 如果根節點沒有 key 瞭,並將根節點調整為合並後的左孩子節點;然後刪除釋放空間。
if (node->keynum == 0) {
if (*tree == node) {
*tree = leftChild;
}

free(node);
node = NULL;
}

free(rightChild);
rightChild = NULL;
}

void BTree_recursive_remove(BTree* tree, KeyType key)
{
// B-數的保持條件之一:
// 非根節點的內部節點的關鍵字數目不能少於 BTree_D - 1

int i, j, index;
BTNode *root = *tree;
BTNode *node = root;

if (!root) {
printf("Failed to remove %c, it is not in the tree!\n", key);
return;
}

// 結點中找key。
index = 0;
while (index < node->keynum && key > node->key[index]) {
++index;
}

/*======================含有key的當前結點時的情況====================
node:
index of Key: i-1 i i+1
+---+---+---+---+
* key *
+---+---+---+---+---+
/ \
index of Child: i i+1
/ \
+---+---+ +---+---+
* * * *
+---+---+---+ +---+---+---+
leftChild rightChild
============================================================*/
/*一、結點中找到瞭關鍵字key的情況.*/
BTNode *leftChild, *rightChild;
KeyType leftKey, rightKey;
if (index < node->keynum && node->key[index] == key) {
/* 1,所在節點是葉子節點,直接刪除*/
if (node->isLeaf) {
for (i = index; i < node->keynum-1; ++i) {
node->key[i] = node->key[i + 1];
//node->child[i + 1] = node->child[i + 2];葉子節點的孩子結點為空,無需移動處理。
}
node->key[node->keynum-1] = 0;
//node->child[node->keynum] = NULL;
--node->keynum;

if (node->keynum == 0) {
assert(node == *tree);
free(node);
*tree = NULL;
}

return;
}
/*2.選擇脫貧致富的孩子結點。*/
// 2a,選擇相對富有的左孩子結點。
// 如果位於 key 前的左孩子結點的 key 數目 >= BTree_D,
// 在其中找 key 的左孩子結點的最後一個元素上移至父節點key的位置。
// 然後在左孩子節點中遞歸刪除元素leftKey。
else if (node->child[index]->keynum >= BTree_D) {
leftChild = node->child[index];
leftKey = leftChild->key[leftChild->keynum - 1];
node->key[index] = leftKey;

BTree_recursive_remove(&leftChild, leftKey);
}
// 2b,選擇相對富有的右孩子結點。
// 如果位於 key 後的右孩子結點的 key 數目 >= BTree_D,
// 在其中找 key 的右孩子結點的第一個元素上移至父節點key的位置
// 然後在右孩子節點中遞歸刪除元素rightKey。
else if (node->child[index + 1]->keynum >= BTree_D) {
rightChild = node->child[index + 1];
rightKey = rightChild->key[0];
node->key[index] = rightKey;

BTree_recursive_remove(&rightChild, rightKey);
}
/*左右孩子結點都剛脫貧。刪除前需要孩子結點的合並操作*/
// 2c,左右孩子結點隻包含 BTree_D - 1 個節點,
// 合並是將 key 下移至左孩子節點,並將右孩子節點合並到左孩子節點中,
// 刪除右孩子節點,在父節點node中移除 key 和指向右孩子節點的指針,
// 然後在合並瞭的左孩子節點中遞歸刪除元素key。
else if (node->child[index]->keynum == BTree_D - 1
&& node->child[index + 1]->keynum == BTree_D - 1){
leftChild = node->child[index];

BTree_merge_child(tree, node, index);

// 在合並瞭的左孩子節點中遞歸刪除 key
BTree_recursive_remove(&leftChild, key);
}
}

/*======================未含有key的當前結點時的情況====================
node:
index of Key: i-1 i i+1
+---+---+---+---+
* keyi *
+---+---+---+---+---+
/ | \
index of Child: i-1 i i+1
/ | \
+---+---+ +---+---+ +---+---+
* * * * * *
+---+---+---+ +---+---+---+ +---+---+---+
leftSibling Child rightSibling
============================================================*/
/*二、結點中未找到瞭關鍵字key的情況.*/
else {
BTNode *leftSibling, *rightSibling, *child;
// 3. key 不在內節點 node 中,則應當在某個包含 key 的子節點中。
// key < node->key[index], 所以 key 應當在孩子節點 node->child[index] 中
child = node->child[index];
if (!child) {
printf("Failed to remove %c, it is not in the tree!\n", key);
return;
}
/*所需查找的該孩子結點剛脫貧的情況*/
if (child->keynum == BTree_D - 1) {
leftSibling = NULL;
rightSibling = NULL;

if (index - 1 >= 0) {
leftSibling = node->child[index - 1];
}

if (index + 1 <= node->keynum) {
rightSibling = node->child[index + 1];
}
/*選擇致富的相鄰兄弟結點。*/
// 3a,如果所在孩子節點相鄰的兄弟節點中有節點至少包含 BTree_D 個關鍵字
// 將 node 的一個關鍵字key[index]下移到 child 中,將相對富有的相鄰兄弟節點中一個關鍵字上移到
// node 中,然後在 child 孩子節點中遞歸刪除 key。
if ((leftSibling && leftSibling->keynum >= BTree_D)
|| (rightSibling && rightSibling->keynum >= BTree_D)) {
int richR = 0;
if(rightSibling) richR = 1;
if(leftSibling && rightSibling) {
richR = cmp(rightSibling->keynum,leftSibling->keynum);
}
if (rightSibling && rightSibling->keynum >= BTree_D && richR) {
//相鄰右兄弟相對富有,則該孩子先向父節點借一個元素,右兄弟中的第一個元素上移至父節點所借位置,並進行相應調整。
child->key[child->keynum] = node->key[index];
child->child[child->keynum + 1] = rightSibling->child[0];
++child->keynum;

node->key[index] = rightSibling->key[0];

for (j = 0; j < rightSibling->keynum - 1; ++j) {//元素前移
rightSibling->key[j] = rightSibling->key[j + 1];
rightSibling->child[j] = rightSibling->child[j + 1];
}
rightSibling->key[rightSibling->keynum-1] = 0;
rightSibling->child[rightSibling->keynum-1] = rightSibling->child[rightSibling->keynum];
rightSibling->child[rightSibling->keynum] = NULL;
--rightSibling->keynum;
}
else {//相鄰左兄弟相對富有,則該孩子向父節點借一個元素,左兄弟中的最後元素上移至父節點所借位置,並進行相應調整。
for (j = child->keynum; j > 0; --j) {//元素後移
child->key[j] = child->key[j - 1];
child->child[j + 1] = child->child[j];
}
child->child[1] = child->child[0];
child->child[0] = leftSibling->child[leftSibling->keynum];
child->key[0] = node->key[index - 1];
++child->keynum;

node->key[index - 1] = leftSibling->key[leftSibling->keynum - 1];

leftSibling->key[leftSibling->keynum - 1] = 0;
leftSibling->child[leftSibling->keynum] = NULL;

--leftSibling->keynum;
}
}
/*相鄰兄弟結點都剛脫貧。刪除前需要兄弟結點的合並操作,*/
// 3b, 如果所在孩子節點相鄰的兄弟節點都隻包含 BTree_D - 1 個關鍵字,
// 將 child 與其一相鄰節點合並,並將 node 中的一個關鍵字下降到合並節點中,
// 再在 node 中刪除那個關鍵字和相關指針,若 node 的 key 為空,刪之,並調整根為合並結點。
// 最後,在相關孩子節點child中遞歸刪除 key。
else if ((!leftSibling || (leftSibling && leftSibling->keynum == BTree_D - 1))
&& (!rightSibling || (rightSibling && rightSibling->keynum == BTree_D - 1))) {
if (leftSibling && leftSibling->keynum == BTree_D - 1) {

BTree_merge_child(tree, node, index - 1);//node中的右孩子元素合並到左孩子中。

child = leftSibling;
}

else if (rightSibling && rightSibling->keynum == BTree_D - 1) {

BTree_merge_child(tree, node, index);//node中的右孩子元素合並到左孩子中。
}
}
}

BTree_recursive_remove(&child, key);//調整後,在key所在孩子結點中繼續遞歸刪除key。
}
}

void BTree_remove(BTree* tree, KeyType key)
{
#ifdef DEBUG_BTREE
printf("BTree_remove:\n");
#endif
if (*tree==NULL)
{
printf("BTree is NULL!\n");
return;
}

BTree_recursive_remove(tree, key);
}

//=====================================search====================================

BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)
{
int i = 0;

while (i < tree->keynum && key > tree->key[i]) {
++i;
}

// Find the key.
if (i < tree->keynum && tree->key[i] == key) {
*pos = i;
return tree;
}

// tree 為葉子節點,找不到 key,查找失敗返回
if (tree->isLeaf) {
return NULL;
}

// 節點內查找失敗,但 tree->key[i - 1]< key < tree->key[i],
// 下一個查找的結點應為 child[i]

// 從磁盤讀取第 i 個孩子的數據
disk_read(&tree->child[i]);

// 遞歸地繼續查找於樹 tree->child[i]
return BTree_recursive_search(tree->child[i], key, pos);
}

BTNode* BTree_search(const BTree tree, KeyType key, int* pos)
{
#ifdef DEBUG_BTREE
printf("BTree_search:\n");
#endif
if (!tree) {
printf("BTree is NULL!\n");
return NULL;
}
*pos = -1;
return BTree_recursive_search(tree,key,pos);
}

//===============================create===============================
void BTree_create(BTree* tree, const KeyType* data, int length)
{
assert(tree);

int i;

#ifdef DEBUG_BTREE
printf("\n 開始創建 B-樹,關鍵字為:\n");
for (i = 0; i < length; i++) {
printf(" %c ", data[i]);
}
printf("\n");
#endif

for (i = 0; i < length; i++) {
#ifdef DEBUG_BTREE
printf("\n插入關鍵字 %c:\n", data[i]);
#endif
int pos = -1;
BTree_search(*tree,data[i],&pos);//樹的遞歸搜索。
if (pos!=-1)
{
printf("this key %c is in the B-tree,not to insert.\n",data[i]);
}else{
BTree_insert(tree, data[i]);//插入元素到BTree中。
}

#ifdef DEBUG_BTREE
BTree_print(*tree);//樹的深度遍歷。
#endif
}

printf("\n");
}
//===============================destroy===============================
void BTree_destroy(BTree* tree)
{
int i;
BTNode* node = *tree;

if (node) {
for (i = 0; i <= node->keynum; i++) {
BTree_destroy(&node->child[i]);
}

free(node);
}

*tree = NULL;
}

0 個評論

要回覆文章請先登錄註冊