[理学]数据结构 第8章.ppt

2. 二叉排序树的删除 在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。 要删除二叉排序树中的p指向的结点，分三种情况： p为叶子结点，只需修改p双亲f的指针f-lchild=NULL f-rchild=NULL * p只有左 子树或右子树 p只有左子树，用p的左孩子代替p (1)(2) p只有右子树，用p的右孩子代替p (3)(4) * p左、右子树均非空 沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5) 若C无右子树，用C代替p (6) 例题： 选取哈希函数h(k)=(3K)%11；用线性探测再散列的方法处理冲突，在0-10的散列地址空间中，对关键字序列（22，41，53，46，30，13，1，67）构造哈希表，并求等概率情况下查找成功的平均查找长度。 例题： 选取哈希函数h(k)=(3K)%11；用线性探测再散列的方法处理冲突，在0-10的散列地址空间中，对关键字序列（22，41，53，46，30，13，1，67）构造哈希表，并求等概率情况下查找成功的平均查找长度。 哈希查找过程及分析 哈希查找过程 哈希查找分析 哈希查找过程仍是一个给定值与关键字进行比较的过程 评价哈希查找效率仍要用ASL 哈希查找过程与给定值进行比较的关键字的个数取决于： 哈希函数 处理冲突的方法 哈希表的填满因子?=表中填入的记录数/哈希表长度 假设哈希表长为m， p为小于等于m的最大素数， 则哈希函数为 H（k）=k%p， 其中%为模p取余运算。  例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10， p=7， 则有 H(18)=18 % 7=4 H(75)=75 % 7=5 H(60)=60 % 7=4 H(43)=43 % 7=1 H(54)=54 % 7=5 H(90)=90 % 7=6 H(46)=46 % 7=4  图8.24 除留余数法求哈希地址 此时冲突较多。 为减少冲突， 可取较大的m值和p值， 如m=p=13， 结果如下：  H(18)=18 % 13=5 H(75)=75 % 13=10 H(60)=60 % 13=8 H(43)=43 % 13=4 H(54)=54 % 13=2 H(90)=90 % 13=12 H(46)=46 % 13=7 90 75 60 46 18 43 54 0 1 2 3 4 5 6 7 8 9 10 11 12 5. 伪随机数法 采用一个伪随机函数作哈希函数， 即 H(key)=random(key)。 在实际应用中， 应根据具体情况， 灵活采用不同的方法， 并用实际数据测试它的性能，以便做出正确判定。 通常应考虑以下五个因素：  · 计算哈希函数所需的时间； · 关键字的长度；  · 哈希表的大小；  · 关键字的分布情况；  · 记录查找的频率。 H(22)=(3*22)%11=0 H(41)=(3*41)%11=2 H(53)=(3*53)%11=5 H(46)=(3*46)%11=6 H(30)=(3*30)%11=2 H(13)=(3*13)%11=6 H( 1 )=(3* 1 )%11=3 H(67)=(3*67)%11=3 8.4.2 处理冲突的方法 1. 开放定址法 这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p= H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，……，直到找出一个不冲突的哈希地址pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：  i=1， 2， …， n 表长 其中H（key）为哈希函数， m 为