12. 二叉搜索树

二叉搜索树支持许多动态集合的操作，包括Search，Insert，Delete，Minimum，Maximum，Successor，Predecessor。所有操作的时间复杂度为$\Omicron(h)$，h为树的高度。

二叉搜索树

二叉搜索树是一个链式存储的二叉树，且具有如下特性：
设x为二叉搜索树中的一个结点。

• 如果y是x左子树中的一个结点，那么y.key<=x.key。
• 如果y是x右子树中的一个结点，那么y.key>=x.key。

Search

从根节点开始查找，如果查询的k小于根节点的key，则递归查找左子树；如果查询的k大于根节点的key，则递归查找右子树；如果查询的k等于根节点的key，done。

Minimum

从根节点开始沿着left child方向一直找到低。

Maximum

从根节点开始沿着right child方向一直找到低。

Successor & Predecessor

查询x的下一个节点：

• 如果x有右孩子，那么x的下一个节点就是右子树的最小值。

  1 2 3 4 5 6 7

  ○ / \ ● / \ ○ / \ [○]

• 若果x没有右孩子，那么x的下一个节点是x的第n个parent，这个parent是第一个符合下图的情况，第n-1个parent 是第n个parent得 left child。

  1 2 3 4 5 6

  [○] / \ ○ / \ ● /

• 如果没有符合这样情况的parent，那么说明x是最大数，没有下一个节点。

Insert

上图描述了插入key为13的数据。
从根节点x开始查找。如果待插入数据小于该节点数据，到左子树继续查找，否则到右子树查找，直到找到一个空位置，将数据放入。

Delete

删除操作的情况较为复杂，有如下几种情况

1. 待删除节点没有孩子
2. 待删除节点只有一个孩子，如下图(a) (b)情况
3. 待删除节点有两个孩子，并且右孩子没有左孩子时，如下图©情况
4. 待删除节点有两个孩子，并且右孩子有左孩子时，如下图(d)情况

1. 当待删除节点没有孩子时：
   • 可以直接删除该节点，并且修改他的父节点，用nil代替他
2. 当待删除节点只有一个孩子时，如图中 (a) (b) 情况：
   • 可以直接用子节点替换该节点
3. 当待删除节点有两个孩子时，如图中 © (d) 情况：
   • 思路：用待删除节点z的Successor节点y替代它的位置
   • 情况c，右孩子没有左孩子（y是z的子节点）
     • y替换z，并且接管z的左孩子
   • 情况d，右孩子有左孩子
     • y的右孩子x替换y，并且y接管z的右孩子
     • y替换z，并且接管z的左孩子

Tips：当待删除节点有两个孩子时，用待删除节点的Predecessor节点替代它也可以。

涉及数据结构

点击查看实现

• 二叉搜索树