算法设计与分析 (2).ppt

文档介绍：算法设计与分析
第一部分:高级数据结构
第二部分:快速排序和顺序统计量
第三部分:动态规划
第四部分:贪心算法
平衡搜索树
B-树和B+树
红黑树
平衡二叉树
第一部分高级数据结构
B-树和B+树
1. 问题的提出
二叉排序树
12
12
24
37
45
53
93
45
24
12
37
53
93
最好:O(log2n)
最坏:O(n)
h
h
平衡二叉树
45
24
12
37
53
93
最坏: O(log2n)
h
多路平衡查找树
37
12 24 37
45 53 93
最坏: O(logxn)
h
B-树和B+树
2. B-树的定义。
B-树(B树)是一种平衡的多路查找树。
一棵m阶的B-树,或是空树,或是满足以下条件的m叉树:
(1)树中每个结点至多有m棵子树;
(2)若根结点不是叶子结点,则至少有二棵子树;
(3)除根结点外的所有非终端结点至少有┌m/2┐棵子树;
(4)所有结点包含信息(n,A0,K1,A1,…Kn,An)其中Ki为关键字且有序,Ai为指向子树根结点的指针,Ai所指子树中所有结点的关键字均小于Ki+1,An所指子树中所有结点的关键字均大于Kn;
(5)所有叶子结点都出现在同一层次上,并且不带信息(为空)。
B-树和B+树
B+树是B-树的变形。
一棵m阶的B+树,或为空树,或是满足下列条件的m叉树:
(1)树中每个结点至多有m棵子树;
(2) 除根之外的所有分支结点至少有m/2棵子树;
(3)若根结点不是叶子结点,则至少有两棵子树;
(4) 有n棵子树的结点有n个关键码;
n
A0
K1
A1
…
…
Kn
An
n+1个分支
1
35
1
18
1
11
1
27
1
39
3
47
53
64
1
99
2
43
78
一棵4阶的B-树
B-树和B+树
3. B-树的查找及分析。
例:。
B-树和B+树
3. B-树的查找及分析。
性能分析:
在B-树是进行查找包含两种基本操作:
(1)在B-树中找结点:通常在磁盘上进行;
(2)在结点中找关键字:在内存中进行。
因此在磁盘上进行查找的次数(即待查关键字所在结点在B-树是的层次数),是决定B-树查找效率的关键因素。
含n个关键字的m阶B-树的最大深度为logm/2((n+1)/2) + 1
最坏的情况: O (logm/2n)
B-树和B+树
4. B-树的插入。
深度为h的m阶B树,首先检索到第h层,确定插入结点位置。
(1)若被插入结点中关键码个数小于m-1,则插入。
(2)若被插入结点中关键码个数等于m-1,则引起
结点“分裂”。