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樹(多路平衡查找樹)它適合在磁盤等直接存取設備上組織動態的查找表是一種外查找算法建立的方式是從下向上拱起

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/22730.html