了解二叉搜索树 (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），以防止在包含或遍历等操作期间出现运行时错误。
边缘节点：在删除节点等场景中，请考虑边缘情况，例如只有一个子节点、没有子节点或作为根节点的节点。
性能：如果您的数据集很大或包含排序块，请考虑重新平衡或使用更合适的数据结构以实现高效查找。