🌳 二叉搜索树 BST 可视化

// 节点结构
class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() { this.root = null; }

    // 插入 - 平均 O(log n)，最坏 O(n)
    insert(val) {
        const node = new Node(val);
        if (!this.root) { this.root = node; return; }
        let cur = this.root;
        while (true) {
            if (val < cur.val) {
                if (!cur.left) { cur.left = node; break; }
                cur = cur.left;
            } else if (val > cur.val) {
                if (!cur.right) { cur.right = node; break; }
                cur = cur.right;
            } else { break; }  // 重复值不插入
        }
    }

    // 搜索 - 平均 O(log n)，最坏 O(n)
    search(val) {
        let cur = this.root;
        while (cur) {
            if (val === cur.val) return cur;
            cur = val < cur.val ? cur.left : cur.right;
        }
        return null;
    }

    // 删除 - 三种情况（叶子/单孩子/双孩子）
    remove(val) {
        this.root = this._remove(this.root, val);
    }

    _remove(node, val) {
        if (!node) return null;
        if (val < node.val) {
            node.left = this._remove(node.left, val);
        } else if (val > node.val) {
            node.right = this._remove(node.right, val);
        } else {
            // 情况1：叶子节点
            if (!node.left && !node.right) return null;
            // 情况2：只有一个孩子
            if (!node.left) return node.right;
            if (!node.right) return node.left;
            // 情况3：两个孩子 → 用中序后继替换
            let succ = node.right;
            while (succ.left) succ = succ.left;
            node.val = succ.val;
            node.right = this._remove(node.right, succ.val);
        }
        return node;
    }

    // 中序遍历 - O(n)，输出有序序列
    inorder(node, out = []) {
        if (!node) return out;
        this.inorder(node.left, out);
        out.push(node.val);
        this.inorder(node.right, out);
        return out;
    }
}