理解二叉搜索树 (BST)

# Web 开发 # JavaScript # 编程 # 初学者

我正在解决一些与二叉搜索树相关的问题，我认为复习一下记忆并与我的粉丝分享我学到的东西会很有趣！所以我们开始吧：

什么是二叉搜索树（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 的图表表示

插入值后二叉搜索树的样子如下：

工作原理

插入：通过比较来放置新值。较小的值放在左边，较大的值放在右边。

搜索（包含）：根据值向左或向右遍历，直到找到节点或遍历在空节点处结束。

遍历：中序遍历按排序顺序访问节点（左 -> 根 -> 右）。

为什么使用二叉搜索树？

高效查找：当树平衡时，在 BST 中搜索会非常高效。

动态大小：您可以添加或删除元素，而无需调整数组大小或移动元素。

排序数据：遍历按排序顺序提供数据，这在优先级队列和内存数据库等场景中很有用。

需要牢记的极端情况

重复项：标准 BST 默认不处理重复值。您可能需要实现逻辑来允许或拒绝重复项，例如在每个节点中存储计数或跳过重复插入。

不平衡树：如果按排序顺序插入值（例如 1、2、3、4、...），BST 会变得倾斜，并退化为操作时间复杂度为 O(n) 的链接列表。使用自平衡 BST（例如 AVL 树、红黑树）有助于缓解此问题。

空树：始终检查树为空的情况（即，this.root === null）以防止在包含或遍历等操作期间出现运行时错误。

边缘节点：在删除节点等场景中，考虑边缘情况，例如只有一个子节点的节点、没有子节点的节点或作为根节点的节点。

性能：如果您的数据集很大或者以排序好的块形式出现，请考虑重新平衡或使用更合适的数据结构进行高效查找。

为了确保效率，BST 应该保持平衡。不平衡的树会将性能降低到 O(n)。考虑使用自平衡树（如 AVL 或红黑树）来持续优化性能。我将在稍后的帖子中讨论其他树。

BST 在软件应用程序中的用例

二叉搜索树 (BST) 不仅仅是教科书中的数据结构——它们在现实世界中有着大量的应用！以下是 BST 在计算机科学中的一些实际应用：

数据库和索引：平衡 BST（如 AVL 或红黑树）通常在数据库索引中处于幕后。它们使范围查询和查找变得非常高效。

内存排序数据：需要在动态添加和搜索时保持数据排序？BST 是您的首选。想想实时分析或监控系统。

编译器中的符号表：编译器依靠 BST 来实现符号表，用于存储和快速访问标识符及其属性。

自动完成和拼写检查器：有没有想过自动完成是如何工作的？ BST 变体（如三元搜索树）可用于有效地组织词典。

优先级调度：虽然堆更常见，但 BST 也可以用于优先级不断变化的动态调度系统。

地理数据 (GIS)：BST 通过存储和检索空间数据（例如查找附近的位置或按范围过滤）来帮助 GIS 系统。

数据压缩：哈夫曼编码是数据压缩算法的关键部分，它使用一种特殊的二叉树为数据符号分配可变长度的代码。

游戏系统：BST 通过保持分数排序并实时检索排名，实现动态排行榜和记分牌。

网络和路由：路由表有时依赖于类似 BST 的结构来确定数据传输的有效路径。

版本控制系统：Git 等系统使用树状结构（受 BST 启发）在有向无环图 (DAG) 中有效地管理提交和版本。

BST 无处不在，从为我们日常使用的工具提供动力到解决复杂的计算问题。很酷，对吧？

但必须注意它们的局限性和极端情况。了解这些细微差别可以帮助您设计更高效、更可靠的系统。

CLIS.CC