了解二叉搜索树 (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中文网其他相关文章！