定义

二叉搜索树，也叫二叉排序树、二叉查找树。它要么是一棵空树，要么是一棵满足如下性质的二叉树：

• 如果它的左子树不为空，那么左子树中所有节点的关键字都不大于根节点的关键字
• 如果它的右子树不为空，那么右子树中所有节点的关键字都不小于根节点的关键字
• 它的左右子树也分别是二叉搜索树

特性

• 中序遍历二叉搜索树可以得到一个关键字有序的节点序列
• 每次插入的新节点都是新的叶子节点
• 搜索、插入、删除的时间复杂度都等于树高，也就是 O(logn)

插入关键字的流程

• 如果二叉搜索树是空树，那么创建新节点，并使之成为根节点，插入结束
• 如果待插入关键字小于根节点的关键字
  • 如果根节点的左子树为空，那么创建新节点，并使之成为根节点的左孩子节点，插入结束
  • 否则，使用相同的方式，在左子树上进行插入
• 否则
  • 如果根节点的右子树为空，那么创建新节点，并使之成为根节点的右孩子节点，插入结束
  • 否则，使用相同的方式，在右子树上进行插入

搜索关键字的流程

• 如果根节点为空，那么搜索失败
• 如果待搜索关键字等于根节点的关键字，那么查询成功
• 如果待搜索关键字小于根节点的关键字，那么使用相同的方式在左子树上进行搜索
• 否则，使用相同的方式在右子树上进行搜索

删除关键字的流程

• 搜索待删除节点，如果搜索失败，则退出
• 如果待删除节点是叶子节点
  • 如果待删除节点是根节点，那么将树置空
  • 否则，将待删除节点的父节点的相应孩子节点置空
• 如果待删除节点的左子树和右子树都不为空
  • 找到左子树的最右节点（或者找到右子树的最左节点）temp
  • 将待删除节点的关键字置为 temp 的关键字，然后将 temp 删掉
    • 因为 temp 的右子树肯定为空，所以将其左子树接到其父节点
• 如果待删除节点的左子树为空
  • 如果待删除节点是根节点，则将根节点置为其右孩子节点
  • 否则，将待删除节点的右孩子节点接到其父节点上
• 如果待删除节点的右子树为空
  • 如果待删除节点是根节点，则将根节点职位其左孩子节点
  • 否则，将待删除节点的左孩子节点接到其父节点上

Python 实现

tim-chow 的 Github