数据结构search.pptVIP

目录 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 1、静态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 2、动态查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 3、哈希查找表 5、平衡二叉分类树的查找分析： 定理：具有 N 个结点的平衡树，高度 h 满足：log2(N+1) = h = 1.44log2(N+1) - 0.328; 最大高度 为 loga(sgr(N+1)) - 2 ); 这里 α＝ (1＋sqr(5))/2; 证明：1、高度为 h 的二叉树最多有 2h - 1个结点，平衡树的结点个数不会超过 2h - 1 个。 即： N = 2h - 1 ；N + 1 = 2h ；N + 1 = 2h ， 所以： log2(N+1) = h 如：高度 2 的平衡树，丰满树结点个 数最多为 2h - 1 个。 2、为了证第二步，构造一系列平衡树， T1 、 T2 、 T3 、……. Th；这种树的高度分别为 1、2、3、 ……h。且是具有高度为1、2、3、……h的平衡树中结点个数最少的二叉树 T1 高度 h = 1 结点个 数最少 T2 高度 h = 2 结点个 数最少 对 照 5、平衡二叉分类树的查找分析: 2、为了证第二步，构造一系列平衡树， T1 、 T2 、 T3 、……. Th；这种树的高度分别为 1、2、3、 ……h。且是具有高度为1、2、3、……h的平衡树中结点个数最少的二叉树 T1 高度 h = 1 结点个 数最少 T2 高度 h = 2 结点个 数最少 对 照 T3 高度 h = 3 结点个 数最少 对 照 5、平衡二叉分类树的查找分析: T3 高度 h = 3 结点个 数最少 对 照 T4 高度 h = 4 结点个 数最少 对 照 Th-1 Th-2 Th 高度 h 结点个数最少的平衡树 左子树为 Th－1 右子树为Th－2 5、平衡二叉分类树的查找分析： 定理：具有 N 个结点的平衡树，高度 h 满足：log2(N+1) = h = 1.44log2(N+1) - 0.328; 最大高度 为 log2(sgr(N+1)) - 2 证明：2、设 t(h) 是高度 h 的平衡树 Th 的结点个数，可以得出： t(1) = 1; t(2) = 2; t(3) = 4; t(4) = 7; . . . . . t(h) = t(h-1) + t(h-2) + 1 for h = 3 该数的序列为 1、2、4、7、12、20、33、54、88 ...… 而 Fibonacc