★分块查找方法评价 ASL。=L+L 其中:L—一査找索引表确定所在块的平均查找长度 在块中查找元素的平均查找长度 若将表长为n的表平均分成b块,每块含s个记录,并设表中每个记录的 查找概率相等,则: (1)用顺序查找确定所在块:AS1 b+1s+11n b心+ +s)+1 J=I 22s (2)用折半查找确定所在块:ASLh≈g2("+1)+ S 2
分块查找方法评价 2 (2) log ( 1) ( ) 1 2 1 2 1 2 1 1 1 (1) 2 1 1 s s n ASL s s b s n i s j b ASL n b s L L ASL L L b s s i b j b s w b b s b w + + = + + + + + = + = = + = = 用折半查找确定所在块： 用顺序查找确定所在块： 查找概率相等，则： 若将表长为 的表平均分成 块，每块含 个记录，并设表中每个记录的 — —在块中查找元素的平均查找长度 其中： — —查找索引表确定所在块的平均查找长度
查找方法比较 顺序查找 折半查找 分块查找 ASL 最大 最小 两者之间 表结构有序表、无序表有序表 分块有序表 存储结构顺序存储结构顺序存储结构顺序存储结构 线性链表 线性链表
ASL 最大 最小 两者之间 表结构 有序表、无序表 有序表 分块有序表 存储结构 顺序存储结构 线性链表 顺序存储结构 顺序存储结构 线性链表 查找方法比较 顺序查找 折半查找 分块查找
★二叉排序树 心定义:二叉排序树或是一棵空树,或是具有下列性质 的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根 结点的值 ●若它的子树不空,则右子树上所有结点的值均大于或等于 它的根结点的值 ●它的左、右子树也分别为二叉排序树 今二叉排序树的插入 ●插入原则:若二叉排序树为空,则插入结点应为新的根结点; 否则,继续在其左、右子树上查找,直至某个叶子结点的左 子树或右子树为空为止.则插入结点应为该叶子结点的左孩 子或右孩子 ●二叉排序树生成:从空树出发,经过一系列的查找、插入操 作之后,可生成一棵二叉排序树
二叉排序树 ❖定义：二叉排序树或是一棵空树，或是具有下列性质 的二叉树： ⚫若它的左子树不空，则左子树上所有结点的值均小于它的根 结点的值 ⚫若它的右子树不空，则右子树上所有结点的值均大于或等于 它的根结点的值 ⚫它的左、右子树也分别为二叉排序树 ❖二叉排序树的插入 ⚫插入原则：若二叉排序树为空，则插入结点应为新的根结点； 否则，继续在其左、右子树上查找，直至某个叶子结点的左 子树或右子树为空为止，则插入结点应为该叶子结点的左孩 子或右孩子 ⚫二叉排序树生成：从空树出发，经过一系列的查找、插入操 作之后，可生成一棵二叉排序树