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

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