資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究編譯器設計中的搜尋樹和雜湊表是什麼？
搜尋樹
一種更有效的符號表組織技術是在每個記錄中新增兩個連結欄位 LEFT 和 RIGHT。我們使用這些欄位將記錄連結到二叉搜尋樹中。
這棵樹具有以下屬性：透過跟隨連結 LEFT (i)，然後跟隨任何連結序列，從 NAME (i) 可訪問的所有名稱 NAME (j) 在字母順序中都位於 NAME (i) 之前（符號表示，NAME (j) < NAME (i)）。
類似地，從 RIGHT (i) 開始訪問的所有名稱 NAME (k) 都將具有 NAME (i) < NAME (k) 的屬性。因此，如果我們正在搜尋 NAME 並找到了 NAME (i) 的記錄，我們只需要在 NAME < NAME (i) 時跟隨 LEFT (i)，並且只需要在 NAME (i) < NAME 時跟隨 RIGHT (i)，當然，如果 NAME = NAME(i)，我們就找到了我們正在尋找的內容。
二叉搜尋樹演算法
- 最初，Ptr 將指向樹的根節點。
- 當 Ptr ≠ NULL 時執行以下操作
- 如果 NAME = NAME (Ptr)
- 則返回 true
- 否則如果 NAME<NAME (Ptr) 則
- Ptr−= LEFT(Ptr)
- 否則 Ptr−= RIGHT (Ptr)
- 迴圈結束
複雜度
如果以隨機順序遇到名稱，則樹中路徑的平均長度將與 log n 成正比，其中 n 是名稱的數量。因此，每次搜尋都遵循從根節點開始的一條路徑，輸入 n 個名稱並進行 m 次查詢所需的時間預計與 (n + m) log n 成正比。如果 n 大於約 50，則二叉搜尋樹相對於連結列表以及可能相對於連結自組織列表具有明顯的優勢。
雜湊表
雜湊是一種用於搜尋符號表記錄的重要過程。此方法優於列表組織。
在雜湊方案中，維護兩個表
- 雜湊表
- 符號表
雜湊表包含從 0 到 K − 1 的 K 個條目。這些條目是指向符號表的指標，指向符號表的名稱。它可以確定“名稱”是否在符號表中，我們使用一個雜湊函式'h'，包括 h (Name) 將導致一個介於 0 到 K − 1 之間的整數。我們可以透過 position = h(Name) 搜尋任何名稱。
使用此位置，我們可以訪問符號表中名稱的確切位置。
雜湊函式應導致名稱在符號表中的分佈。雜湊函式應確保碰撞次數最少。碰撞是指雜湊函式導致儲存名稱的相同位置的情況。有多種碰撞解決技術，例如開放定址、連結和重新雜湊。
複雜度
此方案能夠在與 n(n + m)/k 成正比的時間內對 n 個名稱執行 m 次訪問，其中 k 是我們選擇的任何常數。由於 k 可以根據需要設定得足夠大。這種方法通常優於線性列表或搜尋樹，並且在大多數情況下是符號表的首選技術，尤其是在儲存空間不是特別昂貴的情況下。
2K+ 次瀏覽
