数据结构 邓欣-ch9-查找a.pptVIP

二叉排序树 二叉排序树的特点 中序遍历二叉排序树可得到一个关键字的有序序列（即：可以通过输入一个无序序列，而通过构造二叉排序树后进行遍历的方法实现排序） 二叉排序树的插入过程不需要移动其他记录 具有相同n个结点的二叉排序树会因为构造的时候关键字插入的顺序不同而不同(下页说明) 二叉排序树的查找算法具有折半查找的特性，同时又采用了链式存储结构，因此是动态查找表的适宜表示 如：查找的关键序列分别为{27,32,16,14}、{16,14,27,32}和{14,16,27, 32}, 生成二叉排序树分别如下： 27 16 32 14 16 14 27 32 14 16 27 32 比较极端的例子还有 ?二叉排序树的查找分析 最差情况 (n+1)/2 最好情况 log2n 平均性能 在二叉排序树中删除一个节点 删除叶子节点 删除的结点只有左子树或者只有右子树 在二叉排序树中删除一个节点 p（P175） F P CL PR f p C c Q S QL SL q s (a) 删除*p之前 F CL PR f C c Q S QL SL q s (b) 删除*p之后，以PR作为*S的右子树 F S CL PR f p C c Q QL SL q (c)删除*p之后，以*S替代*p 若*p结点的左子树和右子树均不为空 平衡二叉树 AVL树  高度平衡的二叉有哪些信誉好的足球投注网站树 一棵AVL树或者是空树，或者是具有下列性质的二叉有哪些信誉好的足球投注网站树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。 高度不平衡的二叉有哪些信誉好的足球投注网站树 高度平衡的二叉有哪些信誉好的足球投注网站树 结点的平衡因子balance (balance factor) 每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子balance 。 根据AVL树的定义，任一结点的平衡因子只能取 -1，0和 1。 如果一个结点的平衡因子的绝对值大于1，则这棵二叉有哪些信誉好的足球投注网站树就失去了平衡，不再是AVL树。 如果一棵二叉有哪些信誉好的足球投注网站树是高度平衡的，它就成为 AVL树。如果它有 n 个结点，其高度可保持在O(log2n)，平均有哪些信誉好的足球投注网站长度也可保持在O(log2n)。 AVL树的高度 设在新结点插入前AVL树的高度为 h，结点个数为 n，则插入一个新结点的时间是O(h)。对于AVL树来说，h 多大？ 设 Nh 是高度为 h 的AVL树的最小结点数。根的一棵子树的高度为 h-1，另一棵子树的高度为 h-2，这两棵子树也是高度平衡的。因此有 N-1 = 0 (空树) N0 = 1 (仅有根结点) Nh = Nh-1 + Nh-2 +1 , h 0 可以证明，对于 h ? 0，有 Nh = Fh+3 -1 成立。 思考题 二叉排序树的高度与输入数据序列的关系 * 查找表： 是由同一类型的数据元素（或记录）构成的集合。 查找表的操作： 1、查询某个“特定的”数据元素是否在查找表中。2、检索某个“特定的”数据元素的各种属性。3、在查找表中插入一个数据元素；4、从查找表中刪去某个数据元素。 静态查找表 对查找表只作前两种操作 动态查找表 在查找过程中查找表元素集合动态改变 关键字 是数据元素（或记录）中某个数据项的值 主关键字 可以唯一的地标识一个记录 次关键字 用以识别若干记录 查找 根据给定的某个值，在查找表中确定一个其关键字等于给定的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功。 静态查找表 动态查找表 二叉有哪些信誉好的足球投注网站树 AVL树 哈希表 (Hash) 查找的基本概念 备注 概念 查找表 查找操作针对的数据集，由同一类型的数据元素组成 关键字(key) 数据元素中某个数据项的值，可唯一标识该数据元素 关键字和数据元素的类型说明，如 typedef float KeyType; //实型 typedef int KeyType; //整型 typedef char *KeyType; //字符串型 typedef struct { KeyType key; //关键字域 … //其它域 }ElemType; 概念 查找 在查找表中根据关键字找出特定的数据元素的操作 查找成功 关键字找到，返回对应数据元素在查询表中的位置 查找失败 关键字没有找到，返回空记录或空指针 概念 查找算法 取决于查找表的数据结构 静态查找表 查找表事先已确定 对查询表除了创建和销毁操作外，只有查找或遍历操作 动态查找表 查找表本身在查找过程中动态生成，即若没有