了解二元搜尋樹 (BST)-js教程-PHP中文網

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

什麼是二元搜尋樹 (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:

後二元搜尋樹的樣子

Understanding Binary Search Trees (BST)

它是如何運作的

插入： 依照比較放置新值。較小的值位於左側，較大的值位於右側。
搜尋（包含）：根據值向左或向右遍歷，直到找到節點或遍歷到空節點為止。
遍歷：中序遍歷依排序順序存取節點（左 -> 根 -> 右）。

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

有效率地尋找：當樹平衡時，在 BST 中搜尋會非常有效率。
動態大小：您可以新增或刪除元素，而無需調整陣列大小或移動元素。
排序資料： 遍歷以排序順序提供數據，在優先權佇列和記憶體資料庫等場景中很有用。

要記住的邊緣情況

重複： 預設情況下，標準 BST 不處理重複值。您可能需要實作允許或拒絕重複的邏輯，例如在每個節點中儲存計數或跳過重複插入。
不平衡樹：如果按排序順序插入值（例如，1, 2, 3, 4, ...），BST 就會傾斜並降級到一個操作時間複雜度為O(n) 的鍊錶。使用自平衡 BST（例如 AVL 樹、紅黑樹）有助於緩解此問題。
空樹： 總是檢查樹是否為空（即 this.root === null），以防止在包含或遍歷等操作期間出現運行時錯誤。
邊緣節點：在刪除節點等場景中，請考慮邊緣情況，例如只有一個子節點、沒有子節點或作為根節點的節點。
效能：如果您的資料集很大或包含排序區塊，請考慮重新平衡或使用更合適的資料結構以實現高效查找。