關鍵碼：可以標識一個記錄的某個數據項。
鍵值：關鍵碼的值。
主關鍵碼：可以唯一地標識一個記錄的關鍵碼。
次關鍵碼：不能唯一地標識一個記錄的關鍵碼。
查找 ：在具有相同類型的記錄構成的集合中找出滿足給定條件的記錄。
查找的結果 ：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗。
靜態查找 ：不涉及插入和刪除操作的查找 。
靜態查找適用于：查找集合一經生成，便只對其進行查找，而不進行插入和刪除操作，或經過一段時間的查找之后，集中地進行插入和刪除等修改操作。
動態查找 ：涉及插入和刪除操作的查找。
動態查找適用于：查找與插入和刪除操作在同一個階段進行，例如當查找成功時，要刪除查找到的記錄，當查找不成功時，要插入被查找的記錄。
查找結構 ：面向查找操作的數據結構 ，即查找基于的數據結構。
線性表：適用于靜態查找，主要采用順序查找技術、折半查找技術。
樹表：適用于動態查找，主要采用二叉排序樹的查找技術。
散列表：靜態查找和動態查找均適用，主要采用散列技術。
查找算法時間性能通過關鍵碼的比較次數來度量。
關鍵碼的比較次數與哪些因素有關呢？
⑴算法；
⑵問題規模；
⑶待查關鍵碼在查找集合中的位置；
⑷查找頻率。
查找算法的時間復雜度是問題規模n和待查關鍵碼在查找集合中的位置k的函數，記為T(n，k)。
平均查找長度：將查找算法進行的關鍵碼的比較次數的數學期望值定義為平均查找長度。

順序查找的缺點：平均查找長度較大，特別是當待查找集合中元素較多時，查找效率較低。
順序查找的優點
算法簡單而且使用面廣。
1.對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可；
2.對表中記錄的有序性也沒有要求，無論記錄是否按關鍵碼有序均可。

折半查找
使用條件：
1.線性表中的記錄必須按關鍵碼有序；
2.必須采用順序存儲。

折半查找判定樹
判定樹：折半查找的過程可以用二叉樹來描述，樹中的每個結點對應有序表中的一個記錄，結點的值為該記錄在表中的位置。通常稱這個描述折半查找過程的二叉樹為折半查找判定樹，簡稱判定樹。
判定樹的構造方法
⑴ 當n=0時，折半查找判定樹為空；
⑵ 當n＞0時，折半查找判定樹的根結點是有序表中序號為mid=(n+1)/2的記錄，根結點的左子樹是與有序表r[1] ~ r[mid-1]相對應的折半查找判定樹，根結點的右子樹是與r[mid+1] ~ r[n]相對應的折半查找判定樹。
折半查找性能分析
具有n個結點的折半查找判定樹的深度為[log2 n] +1 。
查找成功：在表中查找任一記錄的過程，即是折半查找判定樹中從根結點到該記錄結點的路徑，和給定值的比較次數等于該記錄結點在樹中的層數。
查找不成功：查找失敗的過程就是走了一條從根結點到外部結點的路徑，和給定值進行的關鍵碼的比較次數等于該路徑上內部結點的個數。

二叉排序樹（也稱二叉查找樹）：或者是一棵空的二叉樹，或者是具有下列性質的二叉樹：
⑴ 若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；
⑵ 若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；
⑶ 它的左右子樹也都是二叉排序樹。
二叉排序樹的定義采用的是遞歸方法。

中序遍歷二叉排序樹可以得到一個按關鍵碼有序的序列。
二叉排序樹的構造從空的二叉排序樹開始，依次插入一個個結點 。

一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列;
每次插入的新結點都是二叉排序樹上新的葉子結點;
找到插入位置后，不必移動其它結點，僅需修改某個結點的指針；
在左子樹/右子樹的查找過程與在整棵樹上查找過程相同；
新插入的結點沒有破壞原有結點之間的關系。

二叉排序樹的刪除
在二叉排序樹上刪除某個結點之后，仍然保持二叉排序樹的特性。
分三種情況討論：
1.被刪除的結點是葉子；
操作：將雙親結點中相應指針域的值改為空。
2.被刪除的結點只有左子樹或者只有右子樹；
操作：將雙親結點的相應指針域的值指向被刪除結點的左子樹（或右子樹）。
3.被刪除的結點既有左子樹，也有右子樹。
操作：以其前驅（無右子樹）（左子樹中的最大值）替代之，然后再刪除該前驅結點。
操作：以其后繼（無左子樹）（右子樹中的最小值）替代之，然后再刪除該后繼結點。

二叉排序樹的查找
在二叉排序樹中查找給定值k的過程是：
⑴ 若root是空樹，則查找失敗；
⑵ 若k＝root->data，則查找成功；否則
⑶ 若k＜root->data，則在root的左子樹上查找；否則
⑷ 在root的右子樹上查找。
上述過程一直持續到k被找到或者待查找的子樹為空，如果待查找的子樹為空，則查找失敗。
二叉排序樹的查找效率在于只需查找二個子樹之一。

平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質的二叉排序樹：
⑴ 根結點的左子樹和右子樹的深度最多相差1;
⑵ 根結點的左子樹和右子樹也都是平衡二叉樹。
最小不平衡子樹：在平衡二叉樹的構造過程中，以距離插入結點最近的、且平衡因子的絕對值大于1的結點為根的子樹。

平衡因子：結點的平衡因子是該結點的左子樹的深度與右子樹的深度之差。

順序查找、折半查找、二叉排序樹查找等。
這些查找技術都是通過一系列的給定值與關鍵碼的比較，查找效率依賴于查找過程中進行的給定值與關鍵碼的比較次數。

散列的基本思想：在記錄的存儲地址和它的關鍵碼之間建立一個確定的對應關系。這樣，不經過比較，一次讀取就能得到所查元素的查找方法。
散列表：采用散列技術將記錄存儲在一塊連續的存儲空間中，這塊連續的存儲空間稱為散列表。
散列函數：將關鍵碼映射為散列表中適當存儲位置的函數。
散列地址：由散列函數所得的存儲位置址 。
散列既是一種查找技術，也是一種存儲技術。
散列只是通過記錄的關鍵碼定位該記錄，沒有完整地表達記錄之間的邏輯關系，所以，散列主要是面向查找的存儲結構。
散列技術最適合回答的問題是：如果有的話，哪個記錄的關鍵碼等于待查值。
散列技術的關鍵問題：
⑴ 散列函數的設計。如何設計一個簡單、均勻、存儲利用率高的散列函數。
⑵ 沖突的處理。如何采取合適的處理沖突方法來解決沖突。

沖突：對于兩個不同關鍵碼ki≠kj，有H(ki)＝H(kj)，
即兩個不同的記錄需要存放在同一個存儲位置,ki和kj相對于H稱做同義詞。
設計散列函數一般應遵循以下原則：
⑴ 計算簡單。散列函數不應該有很大的計算量，否則會降低查找效率。
⑵ 函數值即散列地址分布均勻。函數值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。

總結

以上是生活随笔為你收集整理的20176408李俊 查找技术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。