3动在查传表 AVL树、B树和B+树都是常用的动态查找 表 (1)B树(B树 的定义:一梯m或称mB树,或者是空树,或者是满足下 面特性的m又排序树ch= parenteral) ①每个结点至多有m棵子树, ②如根结点不是叶,至少有两棵子树, ③除根之外,所有拍终端结点至少有「m1m2向上取整棵 子树,以后记为m2 ④所有的非终端结点含有信息 最m/21个关键字 n所 K k结点3、动态查找表 (1)B树(B-树) I. B树的定义：一棵m叉(或称m阶)B树，或者是空树，或者是满足下 面特性的m叉排序树(lchild<parent<rchild)： ①每个结点至多有m棵子树， ②如根结点不是叶，至少有两棵子树， ③除根之外，所有非终端结点至少有┌m/2 ┐(m/2向上取整)棵 子树 ,以后记为[m/2] ④所有的非终端结点含有信息 最多[m/2]-1个关键字 Ai是子树指针，Ki是关键字，结点内部关键字有序 ⑤所有叶结点都在同一层次，叫做失败结点。 AVL树、B树和B+树都是常用的动态查找 表 ····· Kn An · n A0 K1 A1 K2