第8章搜索 8-1设有序顺序表中的元素依次为017, 170,275,503,509,512553,612,677,765,897,908。试 画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长 【解答】 094)(170 =u42C=1(1+2*2+3*4+4*7=45 14 ASL C;=,(3*1+4*14) 5 15 15 8-2若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜 索概率时的平均搜索长度是否相同? (1)搜索失败 (2)搜索成功,且表中只有一个关键码等于给定值k的对象; (3)搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象 【解答】 (1)不同。因为有序顺序表搜索到其关键码比要査找值大的对象时就停止搜索,报告失败信息,不 必搜索到表尾:而无序顺序表必须搜索到表尾才能断定搜索失败 (2)相同。搜索到表中对象的关键码等于给定值时就停止搜索,报告成功信息 (3)不同。有序顺序表中关键码相等的对象相继排列在一起,只要搜索到第一个就可以连续搜索到 其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来, 所需时间就不相同了 前两问可做定量分析。第三问推导出的公式比较复杂,不再进一步讨论。 8-3假定用一个循环链表来实现一个有序表,并让指针head指向具有最小关键码的结点。指针 current 初始时等于head,每次搜索后指向当前检索的结点,但如果搜索不成功则 current重置为head。试编写 个函数 search(head, current key)实现这种搜索。当搜索成功时函数返回被检索的结点地址,若搜索不 成功则函数返回空指针0。请说明如何保持指针 current以减少搜索时的平均搜索长度。 【解答】 curven 相应的搜索函数可以定义为链表及链表结点类的友元函数,直接使用链表及链表结点类的私有数据
第 8 章 搜索 80 8-1 设有序顺序表中的元素依次为 017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试 画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长 度。 【解答】 8-2 若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜 索概率时的平均搜索长度是否相同? (1) 搜索失败; (2) 搜索成功, 且表中只有一个关键码等于给定值 k 的对象; (3) 搜索成功, 且表中有若干个关键码等于给定值 k 的对象, 要求一次搜索找出所有对象。 【解答】 (1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不 必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。 (2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。 (3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到 其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来， 所需时间就不相同了。 前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。 8-3 假定用一个循环链表来实现一个有序表，并让指针 head 指向具有最小关键码的结点。指针 current 初始时等于 head，每次搜索后指向当前检索的结点，但如果搜索不成功则 current 重置为 head。试编写 一个函数 search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不 成功则函数返回空指针 0。请说明如何保持指针 current 以减少搜索时的平均搜索长度。 【解答】 相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据 成员。 509 154 677 017 275 553 897 094 170 503 512 612 765 908 14 45 (1 2*2 3*4 4*7) 14 1 C 14 1 ASL 1 4 i 1 succ = i = + + + = = 15 59 (3*1 4*14) 15 1 C 15 1 ASL 15 i 0 ' unsucc = i = + = = head current 10 20 30 40 50 60
第8章搜索 template ListNode * Search( ListNode*head, ListNode*& current, Type key )4 ListNode *p, 'q: if( key data key )p=p->ink; ∥循链搜索其值等于key的结点 if p->data = key)i current=p: return p: ∥找到,返回结点地址 lse current= head; return NULL; ∥未找到,返回空指针 8-4考虑用双向链表来实现一个有序表,使得能在这个表中进行正向和反向搜索。若指针p总是指向最 后成功搜索到的结点,搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数 search(head,p,kesy),检索具有关键码key的结点,并相应地修改p。最后请给出搜索成功和搜索不成功 时的平均搜索长度 【解答】 hd囚卡20-列上4日5上卡日刘 template DblListNode*Search( DblListNode.head, DblListNode*&p, Type key)( ∥在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点类的友元 函数。若给定值key大于结点p中的数据,从p向右正向搜索,否则,从p向左反向搜索 DblListNode*q= p if( key data while( q l= nUll & q->data >key )q=q-> ILink: 1 反向搜索 else while(q= NULL&& q->data key )q=q->rLink; j ∥正向搜索 if (ql= null & q->data =key )(p=g: return p; j 搜索成功 else return NULL 如果指针p处于第i个结点(i=1,2,…,n),它左边有i-1个结点,右边有ni个结点。找到左边第 i-1号结点比较2次,找到第i-2号结点比较3次,…,找到第1号结点比较i次,一般地,找到左边第 k个结点比较i-k+1次(k=1,2,…,i-1)。找到右边第计1号结点比较2次,找到第计2号结点比较3次,…, 找到第n号结点比较ni计+1次,一般地,找到右边第k个结点比较k-计+1次(k=计+1,i+2,…;n)。因此, 1+∑(-k+1)+∑(k-i+1) 3) 3 当指针处于第i个结点时的搜索成功的平均数据比较次数为 般地,搜索成功的平均数据比较次数为 ASL n+3 i*n)n2+3n-1 succ 如果指针p处于第i个结点(i=1,2,…,n),它左边有i个不成功的位置,右边有ni+1个不成功的位置 ∑-k)+∑(k-i+1)/(mn+1) *(n+y+2-i-i*n+1/(mn+1) k=0
第 8 章 搜索 81 template ListNode * Search ( ListNode * head, ListNode *& current, Type key ) { ListNode * p, * q; if ( key data link; //循链搜索其值等于 key 的结点 if ( p->data == key ) { current = p; return p; } //找到, 返回结点地址 else { current = head; return NULL; } //未找到, 返回空指针 } 8-4 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针 p 总是指向最 后成功搜索到的结点，搜索可以从 p 指示的结点出发沿任一方向进行。试根据这种情况编写一个函数 search(head, p, key)，检索具有关键码 key 的结点，并相应地修改 p。最后请给出搜索成功和搜索不成功 时的平均搜索长度。 【解答】 template DblListNode * Search ( DblListNode * head, DblListNode *& p, Type key ) { //在以 head 为表头的双向有序链表中搜索具有值 key 的结点。算法可视为双向链表类和双向链表结点类的友元 //函数。若给定值 key 大于结点 p 中的数据, 从 p 向右正向搜索, 否则, 从 p 向左反向搜索。 DblListNode * q = p; if ( key data ){ while ( q != NULL && q->data > key ) q = q-> lLink; } //反向搜索 else { while ( q != NULL && q->data rLink; } //正向搜索 if ( q != NULL && q->data == key ) { p = q; return p; } //搜索成功 else return NULL; } 如果指针 p 处于第 i 个结点(i = 1, 2, …, n)，它左边有 i-1 个结点，右边有 n-i 个结点。找到左边第 i-1 号结点比较 2 次，找到第 i-2 号结点比较 3 次，…，找到第 1 号结点比较 i 次，一般地，找到左边第 k个结点比较i-k+1次(k = 1, 2, …, i-1)。找到右边第i+1号结点比较2次，找到第i+2号结点比较3次，…， 找到第 n 号结点比较 n-i+1 次，一般地，找到右边第 k 个结点比较 k-i+1 次(k = i+1, i+2, …, n)。因此， 当指针处于第 i 个结点时的搜索成功的平均数据比较次数为 一般地，搜索成功的平均数据比较次数为 如果指针 p 处于第 i 个结点(i = 1, 2, …, n)，它左边有 i 个不成功的位置，右边有 n-i+1 个不成功的位置。 head p ∧ 10 20 30 40 50 60 70 ∧ n i i i*n 2 n 3 i i i*n n 2 n *(n 3) 1 (i k 1) (k i 1) n 2 2 n k i 1 i 1 k 1 − − + + = + − − + = + − + + − + = + − = 3n n 3n 1 n i i i*n 2 n 3 n 1 ASL n 2 i 1 2 succ + − = − − + + = = i i i*n 1 (n 1) 2 n *(n 3) (i k) (k i 1) (n 1) 2 n k i i 1 k 0 + + − − + + + = − + − + = − =
第8章搜索 般地,搜索不成功的平均数据比较次数为 AL=1S(m+32+2-1-tm+1)=2n+7m+6 (n+1 8-5在一棵表示有序集S的二叉搜索树中,任意一条从根到叶结点的路径将S分为3部分:在该路径左 边结点中的元素组成的集合S1;在该路径上的结点中的元素组成的集合S2;在该路径右边结点中的元素 组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1,b∈S2,c∈S3,是否总有a≤b≤c?为什么? 【解答】 答案是否定的。举个反例:看下图粗线所示的路径 Sl={15},S2={25,30,35,45},S3={40,50,65,70} c=40∈S3,b=45∈S2,b≤c不成立。 8-6设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起,逐个输入各个数据而 生成的二叉搜索树。 【解答】 空树加46 加25 加78 加12 加70 8-7在二叉搜索树上删除一个有两个子女的结点时,可以采用以下三种方 (1)用左子树T上具有最大关键码的结点X顶替,再递归地删除X (2)交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替,再递 归地删除适当的结点 3)用左子树T上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替,再递归 地删除适当的结点。可随机选择其中一个方案
第 8 章 搜索 82 40 一般地，搜索不成功的平均数据比较次数为 8-5 在一棵表示有序集 S 的二叉搜索树中，任意一条从根到叶结点的路径将 S 分为 3 部分：在该路径左 边结点中的元素组成的集合 S1；在该路径上的结点中的元素组成的集合 S2；在该路径右边结点中的元素 组成的集合 S3。S = S1 S2 S3。若对于任意的 a S1, b S2, c S3， 是否总有 a b c？为什么？ 【解答】 答案是否定的。举个反例：看下图粗线所示的路径 S1 = { 15 }, S2 = { 25, 30, 35, 45 }, S3 = { 40, 50, 65, 70 } c = 40 S3，b = 45 S2，b c 不成立。 8-6 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而 生成的二叉搜索树。 【解答】 8-7 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法： (1) 用左子树 TL 上具有最大关键码的结点 X 顶替，再递归地删除 X。 (2) 交替地用左子树 TL 上具有最大关键码的结点和右子树 TR 上具有最小关键码的结点顶替，再递 归地删除适当的结点。 (3) 用左子树 TL 上具有最大关键码的结点或者用右子树 TR 上具有最小关键码的结点顶替，再递归 地删除适当的结点。可随机选择其中一个方案。 45 30 15 25 70 65 35 50 = + + + = + − − + + + = n i 0 2 2 unsucc 2 n 1 2n 7n 6 i i i*n 1 2 n*(n 3) (n 1) 1 ASL 46 46 25 46 25 78 46 25 78 62 46 25 78 12 62 46 25 78 12 37 62 46 25 78 12 37 62 70 46 25 78 12 37 62 29 70 空树 加46 加25 加 78 加 62 加 12 加 37 加 70 加 29
第8章搜索 试编写程序实现这三个删除方法,并用实例说明哪一个方法最易于达到平衡化。 【解答】 ①在被删结点有两个子女时用左子树T中具最大关键码的结点顶替的算法 template BstNode*BST: leftReplace( BstNode*ptr )i BstNode*temp=ptr->leftChild; ∥进到p的左子树 while(temp-> rightchild=NULL)temp=temp-> rightchild;搜寻中序下最后一个结点 ∥用该结点数据代替根结点数据 ②在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法: template BstNode* BST: rightReplace( BstNode*ptr )t BstNoderigh(Child; /进到p的右子树 while(temp-> leftchild i=NULL)temp=temp-> leftchild;W搜寻中序下最后一个结点 mp->data; ∥用该结点数据代替根结点数据 return temp; (1)用左子树TL上具有最大关键码的结点X顶替,再递归地删除X template void BST: Remove( Type&x, BstNode*& ptr)( ∥私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过pt返回 BstNode *temp: if( ptr I=NULL if (xdata)Remove(x, ptr->leftChild ) ∥在左子树中执行删除 else if(x> ptr->data )Remove(x, ptr->rightChild ) ∥在右子树中执行删除 else if ptr->left Child I= nULL & ptr->right Child 1= NULL)( ∥p指示关键码为x的结点,它有两个子女 mp=leftReplace( ptr ) ∥在ptr的左子树中搜寻中序下最后一个结点顶替x Remove(ptr-> data, temp);在temp为根的子树中删除该结 else t ∥pr指示关键码为x的结点,它只有一个或零个子女 if( ptr->leftChild==nULL ptr= ptr->rightChild; ∥只有右子女 else if( ptr->rightChild ==NULL ptr=ptr->leftChild; ∥只有左子女 delete temp: (2)交替地用左子树上具有最大关键码的结点和右子树IR上具有最小关键码的结点顶替,再递 归地删除适当的结点。 template void BST: Remove(Type& x, BstNode*& ptr, int& dir)t ∥私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过pt返回。在参数表中有一个 ∥引用变量dir,作为调整方向的标记。若dir=0,用左子树上具有最大关键码的结点顶替被删关键码;若dir=1 用右子树上具有最小关键码的结点顶替被删关键码结点,在调用它的程序中设定它的初始值为0。 BstNode*temp
第 8 章 搜索 83 试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。 【解答】 ① 在被删结点有两个子女时用左子树 TL 中具最大关键码的结点顶替的算法： template BstNode * BST :: leftReplace ( BstNode * ptr ) { BstNode * temp = ptr->leftChild; //进到 ptr 的左子树 while ( temp->rightChild != NULL ) temp = temp->rightChild; //搜寻中序下最后一个结点 ptr->data = temp->data; //用该结点数据代替根结点数据 return temp; } ② 在被删结点有两个子女时用右子树 TR中具最小关键码的结点顶替的算法： template BstNode * BST :: rightReplace ( BstNode * ptr ) { BstNode * temp = ptr->rightChild; //进到 ptr 的右子树 while ( temp->leftChild != NULL ) temp = temp->leftChild; //搜寻中序下最后一个结点 ptr->data = temp->data; //用该结点数据代替根结点数据 return temp; } (1) 用左子树 TL 上具有最大关键码的结点 X 顶替，再递归地删除 X。 template void BST :: Remove ( Type& x, BstNode *& ptr ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。 BstNode * temp; if ( ptr != NULL ) if ( x data ) Remove ( x, ptr->leftChild ); //在左子树中执行删除 else if ( x > ptr->data ) Remove ( x, ptr->rightChild ); //在右子树中执行删除 else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) { // ptr 指示关键码为 x 的结点，它有两个子女 temp = leftReplace ( ptr ); //在 ptr 的左子树中搜寻中序下最后一个结点顶替 x Remove ( ptr->data, temp ); //在 temp 为根的子树中删除该结点 } else { // ptr 指示关键码为 x 的结点，它只有一个或零个子女 temp = ptr; if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女 else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女 delete temp; } } (2) 交替地用左子树 TL 上具有最大关键码的结点和右子树 TR 上具有最小关键码的结点顶替，再递 归地删除适当的结点。 template void BST :: Remove ( Type& x, BstNode *& ptr, int& dir ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。在参数表中有一个 //引用变量 dir, 作为调整方向的标记。若 dir = 0, 用左子树上具有最大关键码的结点顶替被删关键码; 若 dir = 1, //用右子树上具有最小关键码的结点顶替被删关键码结点, 在调用它的程序中设定它的初始值为 0。 BstNode * temp;
第8章搜索 if ptr I=NULL ata)Remove(x, ptr->left Child, dir ) ∥在左子树中执行删除 else if(x> ptr->data)Remove(x, ptr->rightChild, dir ) ∥在右子树中执行删除 else if( ptr-> leftChild I= nULL & ptr->rightChild I= NULL)& ∥p指示关键码为x的结 有两个子女 mp= leftReplace(p);dr=1;在pt的左子树中搜寻中序下最后一个结点顶替 i else i temp= rightReplace(ptr;dir=0;∥在ptr的右子树中搜寻中序下第一个结点顶替 Remove( ptr->data, temp, dir ) 在temp为根的子树中删除该结点 ∥p指示关键码为x的结点,它只有一个或零个子女 if( ptr->leftChild = NULL )ptr=ptr->rightchild: ∥只有右子女 else if( ptr->rightChild ==nULL ptr= ptr->leftChild ∥只有左子女 delete temp: (3)用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替,再递归 地删除适当的结点。可随机选择其中一个方案 #include template void BST: Remove(Type& x, BstNode*& ptr)i 私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过pr返回。在程序中用到一个 随机数发生器rand(),产生0-32767之间的随机数,将它除以16384,得到0-2之间的浮点数。若其大于1,用左 ∥子树上具有最大关键码的结点顶替被删关键码;若其小于或等于1,用右子树上具有最小关键码的结点顶替被删 ∥关键码结点,在调用它的程序中设定它的初始值为0。 BstNode*temp if(xdata)Remove(x, ptr->left Child ) ∥在左子树中执行删除 else if (x> ptr->data )Remove(x, ptr->rightChild ) ∥在右子树中执行删除 else if ptr-> leftChild null & ptr->right Child I=NULL) ∥pr指示关键码为x的结点,它有两个子女 f(noat)(rand()/16384)>1){ temp= left Replace(ptr);dir=1;∥在pt的左子树中搜寻中序下最后一个结点顶替x i else i temp= rightReplace(p);dir=0;在p的右子树中搜寻中序下第一个结点顶替x Remove( ptr->data, temp ) ∥在temp为根的子树中删除该结点 ∥p指示关键码为x的结点,它只有一个或零个子女 mp= pur
第 8 章 搜索 84 if ( ptr != NULL ) if ( x data ) Remove ( x, ptr->leftChild, dir ); //在左子树中执行删除 else if ( x > ptr->data ) Remove ( x, ptr->rightChild, dir ); //在右子树中执行删除 else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) { // ptr 指示关键码为 x 的结点，它有两个子女 if ( dir == 0 ) { temp = leftReplace ( ptr ); dir = 1; //在 ptr 的左子树中搜寻中序下最后一个结点顶替 x } else { temp = rightReplace ( ptr ); dir = 0; //在 ptr 的右子树中搜寻中序下第一个结点顶替 x } Remove ( ptr->data, temp, dir ); //在 temp 为根的子树中删除该结点 } else { // ptr 指示关键码为 x 的结点，它只有一个或零个子女 temp = ptr; if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女 else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女 delete temp; } } (3) 用左子树 TL 上具有最大关键码的结点或者用右子树 TR 上具有最小关键码的结点顶替，再递归 地删除适当的结点。可随机选择其中一个方案。 #include template void BST :: Remove ( Type& x, BstNode *& ptr ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。在程序中用到一个 //随机数发生器 rand( ), 产生 032767 之间的随机数, 将它除以 16384, 得到 02 之间的浮点数。若其大于 1, 用左 //子树上具有最大关键码的结点顶替被删关键码; 若其小于或等于 1, 用右子树上具有最小关键码的结点顶替被删 //关键码结点, 在调用它的程序中设定它的初始值为 0。 BstNode * temp; if ( ptr != NULL ) if ( x data ) Remove ( x, ptr->leftChild ); //在左子树中执行删除 else if ( x > ptr->data ) Remove ( x, ptr->rightChild ); //在右子树中执行删除 else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) { // ptr 指示关键码为 x 的结点，它有两个子女 if ( (float) ( rand ( ) / 16384 ) > 1 ) { temp = leftReplace ( ptr ); dir = 1; //在 ptr 的左子树中搜寻中序下最后一个结点顶替 x } else { temp = rightReplace ( ptr ); dir = 0; //在 ptr 的右子树中搜寻中序下第一个结点顶替 x } Remove ( ptr->data, temp ); //在 temp 为根的子树中删除该结点 } else { // ptr 指示关键码为 x 的结点，它只有一个或零个子女 temp = ptr;
第8章搜索 if( ptr->leftChild = NULL )ptr=ptr->rightchild: ∥只有右子女 else if(pt-> rightchild=NULL)p=pr-> leftchild;m只有左子女 delete temp: 8-8将关键码DEC,FEB, NOV OCT,JUL,SEP, AUG APR,MAR,MAY,JUN,JAN依次插入到一棵初始为 空的AVL树中,画出每插入一个关键码后的AVL树,并标明平衡旋转的类型 【解答】 加DEC加FEB加NOV 加OCT 加JUL DEC DEC DEC)+2 左单旋 FEB FEB (FEB)+2 加AUG 左单旋 COCT DEC JUL SEP DEC JUL SEP 加APR 加MAR OCT 右单旋 -2(DE UL) (SEP UG (JUD (SE AUG NOV (NO AY OCT FEB OCT (APR (DEC MAR) APR(DEC ( JUD (MAY 加JUN CEED 左右双旋 (AUG D 加JAN
第 8 章 搜索 85 if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女 else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女 delete temp; } } 8-8 将关键码 DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始为 空的 AVL 树中，画出每插入一个关键码后的 AVL 树，并标明平衡旋转的类型。 【解答】 DEC DEC FEB DEC FEB NOV 左单旋 FEB DEC NOV FEB DEC NOV OCT FEB DEC NOV JUL OCT FEB DEC NOV JUL OCT SEP 左单旋 NOV OCT DEC JUL SEP FEB NOV OCT DEC JUL SEP FEB AUG NOV OCT DEC JUL SEP FEB AUG APR 右单旋 NOV OCT JUL SEP FEB AUG APR DEC NOV OCT JUL SEP FEB AUG APR DEC MAR NOV OCT JUL SEP FEB AUG APR DEC MAR MAY 左单旋 NOV OCT SEP FEB AUG APR DEC MAR JUL MAY NOV OCT SEP FEB AUG APR DEC MAR JUL MAY JUN 左右双旋 NOV OCT FEB AUG APR DEC MAR JUL MAY JUN SEP NOV OCT FEB AUG MAR JUL MAY 加 JAN 加 JUN 加 MAY 加 APR 加 MAR 加 AUG 加 SEP 加 DEC 加 FEB 加 NOV 加 OCT 加 JUL +2 +2 -2 +2 -2
第8章搜索 DEC(JA 8-9将关键码1,2,3,…,22-1依次插入到一棵初始为空的AVL树中。试证明结果树是完全平衡的。 【解答】 所谓“完全平衡”是指所有叶结点处于树的同一层次上,并在该层是满的。此题可用数学归纳法证 明。 当k=1时,21-1=1,AVL树只有一个结点,它既是根又是叶并处在第0层,根据二叉树性质,应 具有20=1个结点。因此,满足完全平衡的要求 设k=n时,插入关键码1,2,3,…,2-1到AVL树中,恰好每一层(层次号码i=0,1,…,n1)有2 个结点,根据二叉树性质,每一层达到最多结点个数,满足完全平衡要求。则当k=n+1时,插入关键 码为1,2.3,…,2"-1,2n,…,2+-1,总共增加了从2到2叶+1-1的2n-1-21+1=2个关键码,使得AVL 树在新增的第n层具有2n个结点,达到该层最多结点个数,因此,满足完全平衡要求。 8-10设散列表为HI13]散列函数为H(key)=key%13。用闭散列法解决冲突,对下列关键码序列12 23,45,57,20,03,78,31,15,36造表。采用线性探查査法寻找下一个空位,画出相应的散列表并计算等概 率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度 (2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7*kegy)%10+1,寻找下一个空位的 公式为H=(H1+RlH(kegy)%13,H=H(kegy)。画出相应的散列表,并计算等概率下搜索成功的平均搜 索长度。 【解答】 使用散列函数Hkey)= key mod 13,有 1(45)=6, H(20)=7 H(03)=3, H(78)=0, H(31)=5, H(15)=2, H(36)=10 (1)利用线性探查法造表 1503 57|452031 23|3612 搜索成功的平均搜索长度为 ASLS=1(1+1+1+1+1+1+4+1+2+1)=14 搜索不成功的平均搜索长度为 ASLu=1(2+1+3+2+1+5+43+2+1+5+4+3)=36 (2)利用双散列法造表 Hi=(Hi-1+ RH (key))%13, HI=H(key) 01 3456 101112 3T0T57T5203T3623丁7 (1) (1)(1) (1)(1)(1)(3)(5)(1) (1) 搜索成功的平均搜索长度为
第 8 章 搜索 86 8-9 将关键码 1, 2, 3, …, 2 k -1 依次插入到一棵初始为空的 AVL 树中。试证明结果树是完全平衡的。 【解答】 所谓“完全平衡”是指所有叶结点处于树的同一层次上，并在该层是满的。此题可用数学归纳法证 明。 当 k = 1 时，2 1-1 = 1，AVL 树只有一个结点，它既是根又是叶并处在第 0 层，根据二叉树性质，应 具有 2 0 = 1 个结点。因此，满足完全平衡的要求。 设 k = n 时，插入关键码 1, 2, 3, …, 2n-1 到 AVL 树中，恰好每一层(层次号码 i = 0, 1, …, n-1)有 2 i 个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当 k = n+1 时，插入关键 码为 1, 2, 3, …, 2n-1, 2n , …, 2n+1-1，总共增加了从 2 n到 2 n+1-1 的 2 n+1-1-2 n +1 = 2 n 个关键码，使得 AVL 树在新增的第 n 层具有 2 n 个结点，达到该层最多结点个数，因此，满足完全平衡要求。 8-10 设散列表为 HT[13], 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概 率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 (2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的 公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜 索长度。 【解答】 使用散列函数 H(key) = key mod 13，有 H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5, H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5, H(15) = 2, H(36) = 10. (1) 利用线性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1) 搜索成功的平均搜索长度为 ASLsucc = 1 10 (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14 10 搜索不成功的平均搜索长度为 ASLunsucc = 1 13 (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 36 13 (2) 利用双散列法造表： Hi = (Hi-1 + RH (key)) % 13, H1 = H (key) 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 36 23 12 (1) (1) (1) (1) (1) (1) (3) (5) (1) (1) 搜索成功的平均搜索长度为 APR DEC JAN JUN SEP
第8章搜索 Alsace +1+1+1+1+1+3+5+1+1)=
第 8 章 搜索 87 ASLsucc = 1 10 (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 16 10
