数据结构第九章详解.ppt

ADT Definition (c++) Class Definition (c++) Search Function (c++) 3．二叉排序树的插入算法 根据动态查找表的定义，“插入”操作在查找不成功时才进行； Insert example Insert Function (c++) Insert Function (c++)(continue) Delete example Delete Function (c++) Delete Function (c++)(continue) Delete Function (c++)(continue) Delete Function (c++)(continue) 二、二叉平衡树 1、何谓“二叉平衡树”？ B-tree example B-tree example B-tree example B-tree example Inserting into a B-tree Deleting from a B-tree Deleting from B-tree Deleting from B-tree 因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的次数和 log(n) 相当。 由此推得，深度为 h 的二叉平衡树中所含结点的最小值 Nh = ?h+2/ ? 5 - 1。 反之，含有 n 个结点的二叉平衡树能达到的最大深度 hn = log?(?5 (n+1)) - 2。 三、 B - 树 1．定义 2．查找过程 3．插入操作 4．删除操作 5．查找性能的分析 1．B-树的定义 B-树是一种平衡的多路查找树，它在文件系统中很有用。 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树： ① 树中每个结点至多有m 棵子树； ② 若根结点不是叶子结点，则至少有两棵子树；（至少含1个关键字） ③ 除根之外的所有非终端结点至少有?m/2?棵子树。（至少含 ?m/2?-1个关键字） ④ 所有的非终端结点中包含下列信息数据 (n, A0, K1, A1, K2, A2, …, Kn, An) 其中：Ki(i=1,2,…,n)为关键字，且KiKi+1(i=1,…,n- 1); Ai(i=0,…,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1,…,n), An所指子树中所有结点的关键字均大于Kn, n ( ?m/2?-1≤n≤m-1)为关键字的个数(或n+1为子树个数)。 ⑤ 所有的叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。 B-Trees 【Definition】A B-tree of order M is a tree with the following structural properties: (1) The root is either a leaf or has between 2 and M children. (2) All nonleaf nodes (except the root) have between ?M/2? and M children. (3) All leaves are at the same depth. Assume each nonroot leaf also has between ?M/2? and M children. 9/12 如图所示为一棵4阶的B-树，其深度为3。 在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字 Ki（1≤ i≤n） nm n 个指向记录的指针 Di（1≤i≤n） n+1 个指向子树的指针 Ai（0≤i≤n） 多叉树的特性 typedef struct BTNode { int keynum; // 结点中关键字个数，结点大小 struct BTNode *parent; // 指向双亲结点的指针 KeyType key[m+1]; // 关键字向量（0号单元不用） struct BTNode *ptr[m+1]; // 子树指针向量 Record *recptr[m+1]; // 记录指