二叉搜索树就是这么简单-基础篇

一、背景

之前写过《 数组 》、《 链表 》、《 队列与栈 》、《 哈希 》、《 二分查找 》，后面就开始写树相关的文章了。

这里先介绍最简单的二分搜索树。

二、概念

二叉搜索树（BST）是二叉树的一种特殊表示形式。

它满足如下特性：

1. 每个节点中的值必须大于或等于存储在其左侧子树中的任何值。
2. 每个节点中的值必须小于或等于存储在其右子树中的任何值。

二叉搜索树的概念了解了，就需要做一些练习题加深对这个概念的理解。

初级练习题：判断是不是二叉搜索树（题号 98）。

高级练习题：实现一个二叉搜索树迭代器，每次调用 next 时返回下一个最小值。

分析：找到最小值不难，关键是找到下一个最小值。

根据二叉搜索树的性质，下一个最小值有两种可能：一种是在右子树里面；如果没有右儿子则是父节点。

找到右子树的最小值不难，关键是怎么找到父节点。

如果你学过前面的《栈和队列》文章的话，应该可以发现，可以使用栈来储存父节点路径。

这样，下一个最小值就可以轻松实现了。

三、搜索

二叉搜索树主要支持三个操作：搜索、插入和删除。

这里我们先来看看搜索操作吧。

根据BST的特性，对于每个节点：

1. 如果目标值等于节点的值，则返回节点;
2. 如果目标值小于节点的值，则继续在左子树中搜索;
3. 如果目标值大于节点的值，则继续在右子树中搜索。

四、插入

二叉搜索树中的另一个常见操作是插入一个新节点。

有许多不同的方法去插入新节点。

这里我们只讨论一种最简单的方法。

它的主要思想是为目标节点找出合适的叶节点位置，然后将该节点作为叶节点插入。

与搜索操作类似，对于每个节点，我们将：

1. 根据节点值与目标节点值的关系，搜索左子树或右子树；
2. 重复步骤 1 直到到达外部节点；
3. 根据节点的值与目标节点的值的关系，将新节点添加为其左侧或右侧的子节点。

这样，我们就可以添加一个新的节点并依旧维持二叉搜索树的性质。

五、删除

删除要比我们前面提到过的两种操作复杂许多。

根据其子节点的个数，我们需考虑以下三种情况：

1. 如果目标节点没有子节点，我们可以直接移除该目标节点。
2. 如果目标节只有一个子节点，我们可以用其子节点作为替换。
3. 如果目标节点有两个子节点，我们需要用合并两个子树为一个树，再删除该目标节点。

这里合并两个子树为一个树就有点复杂了。

作为基础篇这里就不多介绍了。

六、总结

二叉搜索树的优点是，即便在最坏的情况下，也允许你在 O(h) 的时间复杂度内执行所有的搜索、插入、删除操作。

有心的你应该注意到了，某些时候，树可能退化为一条链，这时候树的高度就是树的节点个数，此时复杂度就是 O(n) 而不是 O(h) 。

所以，这里需要一种机制，来保证树的高度不会退化为 O(n) ，应该始终为 O(h=log(n)) 。

具体使用时，一般使用内置的数据结构 map 或 set 就够了。

如果涉及到较复杂的操作，那就需要采取实现一些机制，来保证树的高度不会退化。

常见的有平衡树、红黑树、AVL树、伸展树等等，后面到高阶部分了再给你们讲解。

-EOF-