面试

BST , Binary Search Tree

补充

补充：常见树结构及优缺点对比：

  • 数组：随机访问 O(1)，插入/删除 O(n)，适合频繁查找、很少增删的场景。
  • 链表：插入/删除 O(1)，查找 O(n)，适合频繁增删、不需要按索引访问的场景。
  • 二叉搜索树（BST）：平均查找/插入/删除 O(log n)，但当数据有序插入时会退化成链表，复杂度退化为 O(n)。
  • 平衡二叉树（AVL / 红黑树）：通过旋转操作保持树高 O(log n)，保证最坏情况也是 O(log n)；红黑树牺牲严格平衡换取更少的旋转次数，工业界更常用（Java TreeMap、HashMap 桶内链表转树、C++ STL map）。
  • B / B+ 树：多路平衡查找树，常用于磁盘数据库索引（B+ 树叶子节点串成链表便于范围查询）。
  • 堆：完全二叉树，父节点 ≥（或 ≤）子节点，用于优先队列、堆排序，插入/删除 O(log n)，取顶 O(1)。

来源整理自：我的有道云笔记