工業(yè)894專(zhuān)業(yè)課輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)講義四

數(shù)據(jù)結(jié)構(gòu)講義（第四講內(nèi)容：查值K找失敗，返回特定的值，該值表示查找失敗0缺點(diǎn)：平均查找長(zhǎng)度較大，特別是當(dāng)順序表的長(zhǎng)度很大時(shí)，查找效率較低時(shí)間復(fù)雜度為2、二分查找（又稱(chēng)折半查找算法的基本思想（key1/2keyintBiSearch(DataTypea[],intn,KeyTypea[0]--a[n-1]key//查找成功時(shí)返回該元素的下標(biāo)序號(hào)；失敗時(shí)返回-{intlow=0,high=n- intwhile(low<={mid=(low+high)/2; if(a[mid].key==key)returnmid; elseif(a[mid].key<key)low=mid+1;elsehigh=mid-}return- }時(shí)間復(fù)雜度為折半查找要求表是順序的，為保持表的有序性，在進(jìn)行插入和刪除操作時(shí)，索引表中的數(shù)據(jù)元素由兩個(gè)域key域的最大值link域第一個(gè)數(shù)據(jù)元素的位置編號(hào)。分塊查找過(guò)程分兩步進(jìn)行：首先查找索引表，確定待查記錄所在塊（子表（可用折半查找法或順序查找法在相應(yīng)塊（子表）錄。分塊查找的主要代價(jià)是：需要增加一個(gè)輔助數(shù)組的空間和將初始表分衡二叉樹(shù)等。樹(shù)結(jié)構(gòu)有B-樹(shù)、B+樹(shù)等。左的所有結(jié)點(diǎn)均小于根的值右的所有結(jié)點(diǎn)均大于根的值它的左右也分別為二叉排序樹(shù)intSearch(BiTreeNode*root,DataType{BiTreeNode*p;if(root!={p=root;while(p!=NULL){if(p->data.keyitem.key)return1;//查找成功if(item.key>p->data.key)p=p-> //在右繼p=p-> //在左繼}}return }插入算法設(shè)計(jì)如intInsert(BiTreeNode**root,DataTyperootitemitem{BiTreeNode*current,*parent=NULL,*p;current=*root;while(current!={if(current->data.key==item.key)return0;parent=current;if(current->data.key<item.key)current=current->elsecurrent=current-}P=(BiTreeNode*)malloc(sizeof(BiTreeNode));if(p==NULL){}P->data=P->leftChild=P->rightChild=if(parent==NULL)*root=p; elseif(item.key<parent->data.key)parent->leftChild=p; parent->rightChild= return}值大于要?jiǎng)h除結(jié)點(diǎn)數(shù)據(jù)元素關(guān)鍵字的最小值即尋找要?jiǎng)h除結(jié)點(diǎn)右的最左結(jié)在情況下，二叉排序樹(shù)的平均查找長(zhǎng)度為O(n)。在一般情況下，二叉排序樹(shù)的平均查找長(zhǎng)度為O(log2n)。2（AVL樹(shù)高度相差不到1。所以此樹(shù)總是平衡的。平衡二叉樹(shù)(BalancedbinarytreeAVL左右深度之差的絕對(duì)值不超過(guò)左右仍然為平衡二叉樹(shù)平衡因子BF=左深度－右深度平衡二叉樹(shù)每個(gè)結(jié)點(diǎn)的平衡因子只能是1，0，-1。若其絕對(duì)值超過(guò)1，則找出插入新結(jié)點(diǎn)后失去平衡的最小根結(jié)點(diǎn)的指針。然后再調(diào)整這個(gè)中有關(guān)結(jié)點(diǎn)之間的關(guān)系，使之成為新的平衡。當(dāng)失去平衡的最小被調(diào)整為平衡后，原有其他所有不平衡無(wú)需調(diào)整，整個(gè)二叉排序樹(shù)就又失去平衡的最小是指以離插入結(jié)點(diǎn)最近，且平衡因子絕對(duì)值大于1的結(jié)點(diǎn)作為根的。假設(shè)用A表示失去平衡的最小的根結(jié)點(diǎn)，則調(diào)整該子1）LL由于在A的左孩子B的左上插入結(jié)點(diǎn)F，使A的平衡因子由1增至2 即將A的左孩子B向右上旋轉(zhuǎn)代替A作為根結(jié)點(diǎn)，A向右下旋轉(zhuǎn)成為B的右的根結(jié)點(diǎn)。而原來(lái)B的右子樹(shù)則變成A的左。RR由于在A的右孩子C的右上插入結(jié)點(diǎn)F，使A的平衡因子由-1減至-2AC代替A作為根結(jié)點(diǎn)，A向左下旋轉(zhuǎn)成為C的左的根結(jié)點(diǎn)。而原來(lái)C的左子樹(shù)則變成A的右。LR由于在ABF，使A12而失去平衡。故需進(jìn)行兩次旋轉(zhuǎn)操作（先逆時(shí)針，后順時(shí)針）。即先將A的左孩子B的右的根結(jié)點(diǎn)D向左上旋轉(zhuǎn)提升到B結(jié)點(diǎn)的位置，然后再把該DALL型，再按LL的左上，此時(shí)成為L(zhǎng)L型，再按LL型處理成平衡型RL由于在A的右孩子C的左上插入結(jié)點(diǎn)F，使A的平衡因子由-1減至-2而失去平衡。故需進(jìn)行兩次旋轉(zhuǎn)操作（先順時(shí)針，后逆時(shí)針），即先將A的右孩子C的左的根結(jié)點(diǎn)D向右上旋轉(zhuǎn)提升到C結(jié)點(diǎn)的位置，然后再把該DARR型，再按RRA的左上，此時(shí)成為RR型，再按RR型處理成平衡型B_二叉排序樹(shù)那樣的分支現(xiàn)象。因此B_樹(shù)的動(dòng)態(tài)查找效率更高。B_B_mB_樹(shù)或者是一棵空樹(shù)，或者是滿足下列要求的m樹(shù)：樹(shù)中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子結(jié)點(diǎn)（至多含有m-1個(gè)關(guān)鍵字除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)至少有m/2個(gè)孩子結(jié)點(diǎn)（符號(hào)“”表示上取整若根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則根結(jié)點(diǎn)至少有結(jié)點(diǎn)查找算B_xx.keyKi若x.key=Ki則查找成功若key<K1則沿著指針P0所指的繼續(xù)查找若Ki<key<Ki+1則沿著指