了解二元搜尋樹 (BST)

我正在解決一些與二元搜尋樹相關的問題，並認為修改我的記憶並與我的追隨者分享我學到的東西可能會很有趣！那讓我們開始吧：

什麼是二元搜尋樹 (BST)

二元搜尋樹（BST）是電腦科學中的一種基礎資料結構，可以有效地搜尋、插入和刪除資料。它是一個基於樹的結構，每個節點最多有兩個子節點，左子節點總是小於父節點，而右子節點是更大。

BST 的主要特點

1。高效率搜尋： 平衡樹的時間複雜度為 O(log n)。

2。動態結構：可以動態新增或刪除節點。

3。分層表示： 在分層資料表示中很有用，例如檔案系統或家譜。

---

讓我們深入研究使用 TypeScript 的二元搜尋樹的實際實作。

class Node {
    value: number;
    left: Node | null;
    right: Node | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    root: Node | null;

    constructor() {
        this.root = null;
    }

    insert(value: number): void {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return;
        }

        let currentNode = this.root;
        while (true) {
            if (value < currentNode.value) {
                if (currentNode.left === null) {
                    currentNode.left = newNode;
                    return;
                }
                currentNode = currentNode.left;
            } else {
                if (currentNode.right === null) {
                    currentNode.right = newNode;
                    return;
                }
                currentNode = currentNode.right;
            }
        }
    }

    contains(value: number): boolean {
        let currentNode = this.root;

        while (currentNode !== null) {
            if (value === currentNode.value) return true;
            currentNode = value < currentNode.value ? currentNode.left : currentNode.right;
        }

        return false;
    }

    // In-order Traversal: Left -> Root -> Right
    inOrderTraversal(node: Node | null = this.root): void {
        if (node !== null) {
            this.inOrderTraversal(node.left);
            console.log(node.value);
            this.inOrderTraversal(node.right);
        }
    }
}

// Usage
const bst = new BinarySearchTree();
bst.insert(47);
bst.insert(21);
bst.insert(76);
bst.insert(18);
bst.insert(52);
bst.insert(82);

console.log("Contains 21:", bst.contains(21)); // true
console.log("Contains 99:", bst.contains(99)); // false

console.log("In-order Traversal:");
bst.inOrderTraversal();

---

BST 的圖表示

這是插入值 47, 21, 76, 18, 52, 82:

後二元搜尋樹的樣子

---

它是如何運作的

1. 插入： 依照比較放置新值。較小的值位於左側，較大的值位於右側。

2. 搜尋（包含）：根據值向左或向右遍歷，直到找到節點或遍歷到空節點為止。

3. 遍歷：中序遍歷依排序順序存取節點（左 -> 根 -> 右）。

---

為什麼要使用二元搜尋樹？

1. 有效率地尋找：當樹平衡時，在 BST 中搜尋會非常有效率。

2. 動態大小：您可以新增或刪除元素，而無需調整陣列大小或移動元素。

3. 排序資料： 遍歷以排序順序提供數據，在優先權佇列和記憶體資料庫等場景中很有用。

---

要記住的邊緣情況

1. 重複： 預設情況下，標準 BST 不處理重複值。您可能需要實作允許或拒絕重複的邏輯，例如在每個節點中儲存計數或跳過重複插入。

2. 不平衡樹：如果按排序順序插入值（例如，1, 2, 3, 4, ...），BST 就會傾斜並降級到一個操作時間複雜度為O(n) 的鍊錶。使用自平衡 BST（例如 AVL 樹、紅黑樹）有助於緩解此問題。

3. 空樹： 總是檢查樹是否為空（即 this.root === null），以防止在包含或遍歷等操作期間出現運行時錯誤。

4. 邊緣節點：在刪除節點等場景中，請考慮邊緣情況，例如只有一個子節點、沒有子節點或作為根節點的節點。

5. 效能：如果您的資料集很大或包含排序區塊​​，請考慮重新平衡或使用更合適的資料結構以實現高效查找。

為了確保效率，BST應該保持平衡。不平衡的樹會將效能降低至 O(n)。考慮使用 AVL 或紅黑樹等自平衡樹來持續優化效能。我將在稍後的帖子中討論其他樹。

---

BST 在軟體應用程式中的用例

二元搜尋樹 (BST) 不僅僅是您在教科書中遇到的資料結構，它們還有大量的實際應用！以下是 BST 在電腦科學中的一些實用方法：

• 資料庫和索引：平衡 BST（如 AVL 或紅黑樹）通常位於資料庫索引的幕後。它們使範圍查詢和查找變得超級有效率。

• 記憶體中排序資料： 需要在動態新增和搜尋時保持資料排序？ BST 是您的首選。考慮即時分析或監控系統。

• 編譯器中的符號表：編譯器依賴 BST 來實作符號表來儲存和快速存取標識符及其屬性。

• 自動完成和拼字檢查器： 有沒有想過自動完成是如何運作的？ BST 變體，如三元搜尋樹，用於有效地組織單字字典。

• 優先調度：雖然堆疊更常見，但 BST 也可以用於優先級不斷變化的動態調度系統。

• 地理資料 (GIS)： BST 透過儲存和擷取空間資料來幫助 GIS 系統，例如查找附近的位置或按範圍進行過濾。

• 資料壓縮：霍夫曼編碼是資料壓縮演算法的關鍵部分，它使用特殊的二元樹為資料符號分配可變長度的程式碼。

• 遊戲系統： BST 透過對分數進行排序並即時檢索排名，使動態排行榜和記分板成為可能。

• 網路和路由：路由表有時依賴類似 BST 的結構來決定資料傳輸的有效路徑。

• 版本控制系統：像 Git 這樣的系統使用樹狀結構（受 BST 啟發）在有向無環圖 (DAG) 中有效管理提交和版本。

BST 無所不在，從為我們日常使用的工具提供動力到解決複雜的計算問題。很酷吧？

但必須注意它們的限制和邊緣情況。了解這些細微差別可以幫助您設計更有效率、更可靠的系統。

您在與 BST 合作時遇到任何有趣的挑戰或解決方案嗎？下面就來討論一下吧！ ？

以上是了解二元搜尋樹 (BST)的詳細內容。更多資訊請關注PHP中文網其他相關文章！