Binary Search Tree

定义

二叉排序树（Binary Search Tree, BST），也称二叉搜索树，是一种二叉树结构，满足：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左右子树又各是一棵二叉排序树。

操作

• 查找：从根开始，小于当前结点走左子树，大于走右子树
• 插入：查找失败的位置即为插入位置
• 删除
  • 叶子结点：直接删除
  • 只有一棵子树：用子树替代
  • 有两棵子树：用中序后继（或前驱）替代

查找效率

• 平均：$O(\log_2 n)$（树平衡时）
• 最坏：$O(n)$（退化为单支树）

与 AVL 树关系

BST 在最坏情况下性能退化为线性，AVL 树通过自平衡解决了这一问题。见 avl-tree。