数据结构第九章 查找part5.ppt

二、二叉平衡树 何谓“二叉平衡树”？ * 二叉平衡树的查找性能分析 如何构造“二叉平衡树”? 二叉平衡树 又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树或右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。 平衡因子 二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。 二叉平衡树是二叉查找树的另一种形式，其特点为： 树中每个结点的左、右子树深度之差的绝对值不大于1，即 。 例如: 5 4 8 2 5 4 8 2 1 是平衡树 不是平衡树 1 1 0 0 -1 1 0 -1 0 1 0 2 -1 0 0 1 0 -1 0 0 -2 1 0 0 平衡二叉树 不平衡的二叉树 构造二叉平衡（查找）树的方法是： 在插入过程中，采用平衡旋转技术。 例如:依次插入的关键字为5, 4, 2, 8, 6, 9 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋转 一次 先向右旋转 再向左旋转 4 2 6 5 8 9 6 4 2 8 9 5 向左旋转一次 继续插入关键字 9 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。 平衡树的查找性能分析： 问：含 n 个关键字的二叉平衡树可能达到的最大深度是多少？ n = 0 空树 最大深度为 0 n = 1 最大深度为 1 n = 2 最大深度为 2 n = 4 最大深度为 3 n = 7 最大深度为 4 先看几个具体情况: 反过来问，深度为 h 的二叉平衡树中所含结点的最小值 Nh 是多少？ h = 0 N0 = 0 h = 1 h = 2 h = 3 一般情况下 N1 = 1 N2 = 2 N3 = 4 Nh = Nh-1 + Nh-2 + 1 利用归纳法可证得 Nh = Fh+2 - 1 而 Fh≈ ?h／?5 其中 ? =（1+ ?5 ）／2 因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的次数和 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 棵子树； ② 若根结点不是叶子结点，则至少有两棵子树； ③ 除根之外的所有非终端结点至少有?m/2?棵子树。 ④ 所有的非终端结点中包含下列信息数据 (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为子树个数)。 ⑤ 所有的叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。 如图所示为一棵3阶的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