二叉排序树查找算法 基本概念顺序查找二分查找分块索引查找二叉排序树的查找.ppt(2)

借助于判定树很容易求得二分查找的平均查找长度。查找数据的比较次数最多为该判定树的树高 二分查找的算法复杂度为:Olog n即在最坏情况下,二分查找方法查找成功的比较次数不超过判定树的高度。虽然二分查找的效率较高,但它要求被查找序列事先按关键字排好序,而排序本身是一种很费时的运算;另外,二分查找只适用于顺序存储结构,因此,二分查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。平均长度的计算平均长度的计算例如:例如:长度为13的有序表进行折半查找的平均查找长度长度为13的有序表进行折半查找的平均查找长度ASL1×1+2×2+3×4+4×6/1341/13。ASL1×1+2×2+3×4+4×6/1341/13。9.4 分块查找9.4 分块查找分块查找又称为索引查找,它是一种性能介于顺 序查找和二分查找之间的查找算法。分块查找要求将被查找表分成块,建立块索引。每一块中的关键字不一定有序,但前一块中的最 大关键字必须小于后一块中的最小关键字,即要 “分块有序”。抽取各块中的最大关键字及其起始位置构成一个 索引表。由于被查找表是分块有序的,所以索引表是一个递增有序表。例如:0 12345678910 11 12 13 14 15 16 1722 12 13 3 9 20 33 42 44 38 24 48 60 80 74 49 86 530 6 1222 48 86分块查找的基本思想:首先,查找索引表,因为索引表是有序表,故可采用二分查找,也可以采用顺序查找,以确定待查的结点在哪一块;然后在以确定的那一块中顺序查找。

算法分析算法分析由于分块查找实际上是两次查找过程,故整个算法的平均查找长度应该是两次查找的平均查找长度之和。若以二分查找来确定块,则分块查找的平均查找长度约为:log n / ss / 22若以顺序查找来确定块,则分块查找的平均查找长度约为:2b ?1 / 2 s ?1 / 2 s2 sn /2 ssn对于后一种情况,当 时,平均查找长度为极小值。在实用中,可根据表的具体情况进行分块。 分块查找的性能介于顺序查找和二分查找之间的,例如,对长度为10000的线性表,它们的平均查找长度分别是:顺序查找:约5000分块查找:约100二分查找:约149.5二叉排序树的查找1.二叉排序树的概念2.二叉排序树的建立3.二叉排序树的插入4.二叉排序树的删除5.二叉排序树的查找6.查找性能分析1二叉排序树的概念也称为二叉查找树.1左子树的所有结点的值根结点的值2右子树的所有结点的值根结点的值3左子树、右子树都是二叉排序树。举例:性质:中序遍历二叉排序树得到的是有序序列。? class BiSortTreeBiNode *root;void InsertBiNode *&ptr, int k; //供插入函数调用BiNode* SearchBiNode *ptr, int k; //供查找函数调用void Delete BiNode *&ptr, int k; //供删除函数调用void FreeBiNode *ptr; //供析构函数调用public:BiSortTreeint a[ ], int n; //建立二叉排序树~BiSortTree; //析构函数void Insertint k; //插入bool Searchint k;//查找void Delete int k;//删除;2.二叉排序树的插入和建立在一棵二叉排序树中插入值为k的结点,步骤如下:① 若二叉排序树为空,则生成值为k的新结点s,同时将新结点s作为根结点插入。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26491-2.html