B树
平衡的m阶查找树,其中:
1. 树中的每个节点至多含有m棵子树
2. 根节点若不是叶子节点,则其含有至少两棵子树
3. 除根节点以外的非叶子节点,其至少含有[m/2]棵子树
4. 所有的非叶子节点,含有以下的数据域:
(n,A1,K1,R1,...,An,Kn,Rn,A[n+1])
n是节点里含有的关键字个数,n+1为子树个数
An是指向子树根节点的指针,其中A[n]所指向子树的所有关键字都小于Kn,
A[n+1]所指向子树的所有关键字都大于Kn
Kn是关键字
Rn是指向Kn关键字对应的记录
其中关键字是有序的。
B树的一种变体B+树是流行的数据库文件结构。
B树的查找和插入删除算法，实现如下，其中查找和插入算法在严蔚敏的C语言数据结构书中有介绍，而删除算法不论在严蔚敏的书中，还是在MIT的算法导论中，均只有概念性的描述，而没有具体的实现参考。
以下程序随机产生100个0-100之间的整数，然后用这些数构造一棵5阶的B树，最后依次从树中删除各个数，直至树为空。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define m 5 // 5阶B树
typedef unsigned int key_t;
typedef unsigned long val_t; // B树作为索引,节点里的记录作为一个数据文件的偏移
struct __btree_node
{
int n;
struct __btree_node *parent;
key_t key ­ // 实际包含n-1个key,最多m-1个key
struct __btree_node *A[m + 1]; // 实际包含n个A*,最多m个A*
val_t R ­
};
typedef struct __btree_node bt_node, *bt_node_ptr, *bt_ptr;
bt_ptr bt_root;
bt_node_ptr bt_search(bt_node_ptr p, key_t k, int deep, int *which, int *got)
{
bt_node_ptr cur = p, ancestor = p;
int n, i;
if (got)
*got = 0;
while (cur)
{
n = cur->n;
for (i = 0; i < n; i++)
{
*which = i;
if (k < cur->key)
{
ancestor = cur;
if (deep)
cur = cur->A;
else
cur = NULL;
break;
}
else if (k == cur->key)
{
if (got)
*got = 1;
else
(*which)++;
return cur;
}
}
if (i >= n)
{
*which = n;
ancestor = cur;
if (deep)
cur = cur->A[n];
else
cur = NULL;
}
}
// 当查找失败,返回父节点,为了插入方便
return ancestor;
}
int bt_insert(bt_node_ptr *p, key_t k)
{
int which, got = 1, over = 0;
int n, i;
key_t k0 = k;
bt_node_ptr a = *p, t, a0 = NULL;
while (!over)
{
t = bt_search(a, k0, got, &which, &got);
if (got)
return !got; // 已有相同节点,不必插入
if (t == NULL) // 树为空
{
bt_node_ptr parent = (bt_node_ptr) malloc(sizeof(bt_node));
// 新建一个树根节点
parent->n = 1;
parent->parent = NULL;
parent->key[0] = k0;
parent->A[0] = *p;
parent->A[1] = a0;
if (a0)
a0->parent = parent;
if (*p)
(*p)->parent = parent;
*p = parent;
over = 1;
}
else // 查找失败,返回应插入位置的父节点
{
n = t->n;
// 直接插入
for (i = n; i > which; i--)
{
t->key = t->key[i - 1];
t->A[i + 1] = t->A;
}
t->key[which] = k0;
t->A[which + 1] = a0;
if (a0)
a0->parent = t;
++(t->n);
if (n + 1 > m - 1) // 需要分裂节点
{
// a指向的节点已经含有了m-1个key
// 如果继续插入key,则节点将变为:
// m,A0,K0,A1,K1,...,K[m-1],A ­
//
// 为此,分裂a指向的节点为a和a':
// a: [m/2]-1,A0,K0,...,K[m/2-2],A[m/2-1]
// a': m-[m/2],A[m/2],K[m/2],...,K[m-1],A ­
//
// 当m=4时,如下:
// a: 1,A0,K0,A1
// a': 2,A2,K2,A3,K3,A4
//
// 而K[m/2-1]和指向a'的指针插入到父节点中
// 另外,这个分裂节点的过程显然也适合父节点
int d = (m + 1) / 2, c = d - 1;
// 当m=4时,d=2,c=1
a0 = (bt_node_ptr) malloc(sizeof(bt_node));
k0 = t->key[c];
// a节点
t->n = c;
// a'节点
a0->n = m - d;
for (i = d; i < m; i++)
{
a0->A[i - d] = t->A;
if (a0->A[i - d])
a0->A[i - d]->parent = a0;
a0->key[i - d] = t->key;
}
a0->A[m - d] = t->A ­
if (a0->A[m - d])
a0->A[m - d]->parent = a0;
// 插入父节点
// 需要判断父节点是否为空
// 即,当前节点是否为根节点
// 当根节点需要分裂时,查找根节点的父节点的结果也是返回空
a = t->parent;
}
else
over = 1;
}
}
return !got;
}
int bt_delete(bt_node_ptr *p, key_t k)
{
int w, q, over = 0;
int n, d, c, i;
key_t k0 = k;
bt_node_ptr a = *p, t;
// 先搜索这个给定的key
t = bt_search(a, k0, 1, &w, &q);
if (!q)
return q;
// 如果找到,则将这个key对应的节点删除
// 1.非叶子节点
if (t->A[w] || t->A[w + 1])
{
// 找出待删节点右子树的最小节点
// (因为B树是平衡树,假设不会出现有左子树而无右子树的情况)
bt_node_ptr child = t->A[w + 1];
while (child->A[0])
child = child->A[0];
t->key[w] = child->key[0];
// 接下来要删去右子树的最小节点
t = child;
w = 0;
}
d = (m + 1) / 2; // d=[m/2],当m=5时,d=3
c = d - 1;
if (w)
w++;
// 2.叶子节点,分为3种情况
do
{
// 先删去待删节点
n = t->n;
q = n - 1;
if (w == 0)
{
for (i = 0; i < q; i++)
{
t->key = t->key[i + 1];
t->A = t->A[i + 1];
}
t->A = t->A[i + 1];
}
else
{
for (i = w - 1; i < q; i++)
{
t->key = t->key[i + 1];
t->A[i + 1] = t->A[i + 2];
}
}
// 如果回溯到根节点
if (!(t->parent))
{
if (n < d)
{
*p = t->A[0];
free(t);
if (*p)
(*p)->parent = NULL;
}
else
--(t->n);
break;
}
if (n < d) // 待删节点的关键字个数小于d,需要合并节点
{
bt_node_ptr bro;
bt_search(t->parent, t->key[0], 0, &w, NULL);
// b).待删节点的关键字个数小于d,而相邻节点不小于d
if (w == 0)
{
bro = t->parent->A[w + 1];
if (bro->n >= d)
{
k0 = t->parent->key[0];
t->parent->key[0] = bro->key[0];
t->key[t->n - 1] = k0;
t->A[t->n] = bro->A[0];
if (t->A[t->n])
t->A[t->n]->parent = t;
n = --(bro->n);
for (i = 0; i < n; i++)
{
bro->key = bro->key[i + 1];
bro->A = bro->A[i + 1];
}
bro->A = bro->A[i + 1];
break;
}
}
else
{
bro = t->parent->A[w - 1];
if (bro->n >= d)
{
k0 = t->parent->key[w - 1];
t->parent->key[w - 1] = bro->key[bro->n - 1];
for (i = q; i > 0; i--)
{
t->key = t->key[i - 1];
t->A[i + 1] = t->A;
}
t->A[1] = t->A[0];
t->key[0] = k0;
t->A[0] = bro->A[bro->n];
if (t->A[0])
t->A[0]->parent = t;
--(bro->n);
break;
}
}
// c).待删节点里的关键字个数小于d,并且相邻节点也小于d
if (w == 0)
{
for (i = 0; i < c; i++)
{
bro->key[i + c] = bro->key;
bro->A[i + c + 1] = bro->A[i + 1];
}
bro->A[c] = bro->A[0];
bro->key[c - 1] = t->parent->key[0];
for (i = 0; i < c - 1; i++)
{
bro->key = t->key;
bro->A = t->A;
if (bro->A)
bro->A->parent = bro;
}
bro->A = t->A;
if (bro->A)
bro->A->parent = bro;
free(t);
bro->n <<= 1;
}
else
{
bro->key[c] = t->parent->key[w - 1];
for (i = 0; i < c - 1; i++)
{
bro->A[i + c + 1] = t->A;
bro->key[i + c + 1] = t->key;
if (bro->A[i + c + 1])
bro->A[i + c + 1]->parent = bro;
}
bro->A[i + c + 1] = t->A;
if (bro->A[i + c + 1])
bro->A[i + c + 1]->parent = bro;
free(t);
bro->n <<= 1;
}
t = bro->parent;
}
else
{
--(t->n);
over = 1;
}
} while (!over);
return q;
}
void bt_destroy()
{
if (bt_root)
{
bt_node_ptr cur = bt_root, sav_cur;
int n, i;
while (cur)
{
n = cur->n;
for (i = 0; i <= n; i++)
{
if (cur->A)
{
cur = cur->A;
cur->parent->A = NULL;
break;
}
}
if (i > n)
{
sav_cur = cur->parent;
free(cur);
cur = sav_cur;
}
}
}
}
//===========================================================================================
#define RECORD_CNT 100
int main()
{
int i;
int seq[RECORD_CNT];
// B树
bt_root = NULL;
srand(time(NULL));
for (i = 0; i < RECORD_CNT; i++)
seq = rand() % RECORD_CNT;
for (i = 0; i < RECORD_CNT; i++)
bt_insert(&bt_root, seq);
for (i = 0; i < RECORD_CNT; i++)
bt_delete(&bt_root, seq);
bt_destroy();
return 0;
} |
IP卡
狗仔卡
发表于 2010-9-22 00:35
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2010-9-22 01:03
发表于 2010-9-22 01:08
|小黑屋|《唐诗宋词》网站
( 苏ICP备2021032776号 )
楼主