数据结构查找

《数据结构查找》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、8查找二分查找及算法设计二叉排序树及构造平衡二叉树的查找、插入及旋转hash表的构造及查找8.1二分(折半）查找一、二分查找的先决条件表中结点按关键字有序，且顺序（一维数组）存储。二、二分法思想：取中，比较（1）求有序表的中间位置mid（2）若r[mid].key==k，查找成功；若r[mid].key>k，在左子表中继续进行二分查找；若r[mid].key

2、1）k=35Kr[m]:在右半部分继续查找。i=m+1=4,j=5m=(i+j)/2=4。r[m]==k:查找成功。m=(i+j)/2=6。1221303538404855566064i=1,j=11,m=(i+j)/2=6。r[m]k:在左半部分继续查找。i=7,j=m-1=8,m=(i+j)/2=7。

3、r[m]k:在左半部分继续查找。i=8,j=m-1=7,i>j:查找失败二分法查找示例（2）k=501234567891011三、存储结构keyinfotypedefstruct{keytypekey;………….}elemtype;k1k2k3…………kn0123n四、算法描述intSearch_bin(elemtyper[],intn,keytypek){//r[1]..r[n]是按key排序的n个元素，在表中

4、查找ki=1;j=n;while(i<=j){mid=(i+j)/2;//取中if(k==r[mid].key)return(mid);//查找成功elseif(k

5、*3+4*4）/11=3二分查找算法的时间复杂度T(n)=O(log2n)455310061123907837248.2二叉排序树一、二叉排序树的定义二叉排序树或空，或对于二叉树中的每一个结点，若它的左子树非空，则左子树上所有结点的关键字值均小于该结点的值。若根的右子树非空，则右子树上的所有结点的关键字值均大于该结点的值。二、二叉排序树的特点中序遍历得一有（升）序序列。查找方法：若根结点的关键字值等于查找的关键字，查找成功。否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字的值，则查

6、其右子树。在左右子树上的操作类似。45531006112390783724三、二叉排序树的查找例8.1:查找k=2445531006112390783724四、二叉排序树的插入若二叉树为空。则生成根结点。若二叉树非空（1）首先进行查找，找出被插结点的父结点。（2）判断被插结点是其父结点的左、右儿子，将其作为叶子结点插入。60例8.2:在二叉排序树中插入6045531006112390783724五、二叉排序树的构造若二叉树为空。则生成根结点。若二叉树非空（1）首先执行查找，找到被插结点的父亲结点

7、。（2）判断被插结点是其父亲结点的左、右儿子，将其结点插入。例8.3：以{45,53,12,37,24,100,3,61,90,78}构造二叉排序树。539337244512一、什么是平衡二叉树或空树，或是具有下列性质的二叉排序树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。８.３平衡二叉树(AVL树)二、平衡因子（BalanceFactor)左子树的深度-右子树的深度即平衡二叉树中每一结点的平衡因子为：0，1，-1。0-10000三、平衡二叉树的查找——即二叉

8、排序树查找4590100781236137240100001-1-1插入154590100781236137240100011-20152（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。四、平衡的二叉树的插入4590100781236137240100110LL旋转4590100781236124370-100001-2050015201500（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。四、平衡的二叉树的插入一、hash函数&hash表设计1个