第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