6. 二叉搜索树（Binary Search Tree）

6. 二叉搜索树（Binary Search Tree）

问题：需要有序的数据集合，支持快速查找、插入、删除。

核心：每个节点的左子树所有值 < 节点值 < 右子树所有值。查找时每次比较可排除一半，类似二分查找。

特点

  • 左子树 < 根 < 右子树（BST 性质）
  • 中序遍历得到有序序列
  • 查找/插入/删除平均 O(log n)

优点

  • 平均 O(log n) 查找、插入、删除
  • 中序遍历天然有序
  • 动态维护有序集合，不需要排序

缺点

  • 最坏情况退化为链表，O(n)（如顺序插入）
  • 需要平衡化处理（AVL、红黑树）来保证性能
  • 实现比数组和哈希表复杂
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  root = null;

  insert(val) {
    const node = new TreeNode(val);
    if (!this.root) { this.root = node; return; }
    let cur = this.root;
    while (true) {
      if (val < cur.val) {
        if (!cur.left) { cur.left = node; return; }
        cur = cur.left;
      } else {
        if (!cur.right) { cur.right = node; return; }
        cur = cur.right;
      }
    }
  }

  search(val) {
    let cur = this.root;
    while (cur) {
      if (val === cur.val) return cur;
      cur = val < cur.val ? cur.left : cur.right;
    }
    return null;
  }

  // 中序遍历 → 有序数组
  inOrder(node = this.root, res = []) {
    if (!node) return res;
    this.inOrder(node.left, res);
    res.push(node.val);
    this.inOrder(node.right, res);
    return res;
  }
}

const bst = new BST();
[5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
console.log(bst.inOrder());           // [1, 3, 4, 5, 6, 7, 8]
console.log(bst.search(4)?.val);      // 4
console.log(bst.search(9));           // null
package bst

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type BST struct {
    Root *TreeNode
}

func (b *BST) Insert(val int) {
    b.Root = insert(b.Root, val)
}

func insert(node *TreeNode, val int) *TreeNode {
    if node == nil {
        return &TreeNode{Val: val}
    }
    if val < node.Val {
        node.Left = insert(node.Left, val)
    } else {
        node.Right = insert(node.Right, val)
    }
    return node
}

func (b *BST) Search(val int) *TreeNode {
    cur := b.Root
    for cur != nil {
        if val == cur.Val {
            return cur
        }
        if val < cur.Val {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    return nil
}

// 中序遍历 → 有序切片
func InOrder(node *TreeNode, res *[]int) {
    if node == nil {
        return
    }
    InOrder(node.Left, res)
    *res = append(*res, node.Val)
    InOrder(node.Right, res)
}

数据库索引（B/B+ 树）、std::map（红黑树）、文件系统目录结构都是 BST 思想的延伸。平衡 BST（AVL、红黑树）保证最坏 O(log n)。