09年自考《数据结构》各章要点二[9]

第九章 查找

查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表否则称之为静态查找表

衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL)

线性表查找的方法

·顺序查找逐个查找ASL=(n+)/

·二分查找取中点int(n/)比较若小就比左区间大就比右区间用二叉判定树表示ASL=(∑(每层结点数*层数))/N

·分块查找要求分块有序将表分成若干块内部不一定有序并抽取各块中的最大关键字及其位置建立有序索引表

二叉排序树(BST)定义是二叉排序树是空树或者满足如下性质的二叉树

·若它的左子树非空则左子树上所有结点的值均小于根结点的值

·若它的右子树非空则右子树上所有结点的值均大于根结点的值

·左右子树本身又是一棵二叉排序树

二叉排序树的插入建立删除的算法平均时间性能是O(nlogn)

二叉排序树的删除操作可分三种情况进行处理

·*P是叶子则直接删除*P即将*P的双亲*parent中指向*P的指针域置空即可

·*P只有一个孩子*child此时只需将*child和*p的双亲直接连接就可删去*p

·*p有两个孩子则先将*p结点的中序后继结点的数据到*p删除中序后继结点

关于B树(多路平衡查找树)它适合在磁盘等直接存取设备上组织动态的查找表是一种外查找算法建立的方式是从下向上拱起

[] [] [] [] [] [] [] [] [] [] [] []