什么是二叉搜索树，如何通过代码实现它们？

生活中，我们经常需要找东西或做决定，一个简单的方法就是将选择一分为二。假设你在玩“猜猜我是谁”的游戏，目标是猜测你的对手所选择的角色。你就可以问他们这样的问题，比如：

• 你的角色是男性还是女性?
• 男性。好，那他有胡子吗?
• 没有。好，他戴帽子吗?

我们在每一步都继续推断我们的选择。同理，二叉搜索树通过在每一步都减少选项来帮助找到想要的东西。

[[345440]]

首先，二叉搜索树到底是什么?

二叉搜索树(BST)是一种特殊类型的树形数据结构，由节点及其子节点组成，子节点也被视作“后代”，可以把它想象成一棵倒置的树或者是树的根部。

每个节点最多只能有2个子节点：左节点和右节点。为了使它成为一个有效的二叉搜索树，左节点的值必须总是小于母节点，而右节点的值必须总是大于母节点。没有任何间隙的BST，即每个节点都有一个左节点和一个右节点的二叉搜索树，被称为“完美”树。

在完美树中，当遍历树时，每个级别中的节点数会翻倍，将前面的所有节点相加并在该数字上再添加“1”可以得出底层的节点总数。

当在平衡二叉搜索树中搜索一个元素时，平均需要花费额的时间为O(log n)，在最坏的情况下，需要O(n)。你可以把在二叉搜索树中的搜索看作是“选择你自己的冒险”模型，从顶部节点开始，然后沿着树向下，在到达的每个节点问同样的2个问题。

• 我要找的值是否小于当前节点?如果是，向左走。
• 我要找的值是否大于当前节点?如果是，向右走。

插入和删除也非常快，平均花费O(log n)的时间。但有一个缺点就是不能像数组那样获得随机元素。

什么时候可以使用二叉搜索树?

假设你需要为Facebook这样的社交媒体应用程序设计一个数据库。该数据库需要处理数百万个用户名，并且需要在登录期间快速检索到其中一个用户名。由于每天都有新注册或删除的账户，你也需要方便进行插入和删除的操作。

通过一个排序过的数组进行二分搜索会非常快(需要花费O(log n)时间)，但是插入或删除一个用户名会导致整个数组重新排序，需要花费O(n)时间，这取决于数组的大小，可能会相对慢一些。如果我们使用二叉搜索树，插入或删除的时间会快得多(花费O(log n)时间)。

如果有一个带有名字的二叉搜索树(比如这个《海底总动员》的树)，就可以按字母顺序排列。

在字母表中，Dory在Marlin之前，所以它是左边的节点，而Moonfish在Marlin之后，所以它是右边的节点。同样地，在下一层搜索也遵循这个规律。Bruce在Crush之前，也在Dory和Marlin之前。Darla在Crush之后，但在Dory和Marlin之前。

现在准备好，是时候寻找Nemo了!

寻找Nemo!

假设已经有一个有效的二叉搜索树，并且需要找到Nemo。因为我们知道树中的节点是按字母顺序排序的，所以这应该相当简单。

从Marlin开始，左边是Dory，右边是Moonfish。我们知道Nemo在字母表中位于Marlin之后，所以我们将遍历到正确的节点(Moonfish)。Nemo按字母顺序是排在Moonfish之后的，所以继续往下看Moonfish的右子节点。很幸运，那是…Nemo!找到Nemo了!

效率很高。二叉搜索树减少了整个搜索过程的时间复杂性!如果树没有分类，只是一个普通的树形结构呢?或者要证实这是个二叉搜索树呢?目前有两种不同的搜索技术可以实现这一点。

什么是广度优先搜索?

广度优先搜索是一种在树(或图形)中一次遍历一级的方法，每次都从左到右在节点之间移动。

在《海底总动员》的例子中，Marlin首先会问Dory，“你知道我儿子Nemo在哪里吗?”如果它说不，Marlin就会问Moonfish同样的问题。如果它也说不，Marlin会再下一层，问Crush、Gill和Mr. Ray，然后Marlin就找到Nemo了!

广度优先搜索

如果在Mr. Ray之后没有找到Nemo，Marlin会到下一级询问Bruce和Darla等等。使用广度优先搜索可以找到起始节点(Marlin)和目标节点(Nemo)之间的最短距离。时间复杂度是O(n)，因为在最坏的情况下，需要检查每个节点才能找到Nemo。

什么是深度优先搜索?

深度优先搜索(Depth first search)是一种从顶部节点一直向下遍历到其最远子节点的树(或图形)的方法，然后在未找到目标节点时再回去并尝试其他路径。

在《海底总动员》的例子中，Marlin首先会问Dory “你知道Nemo在哪里吗?” 如果她不知道，他就会问Crush同样的问题，因为Crush是Dory最左边的子节点。如果Crush也说没有，Marlin将移动到下一级去问Bruce，尽管他害怕成为鲨鱼的点心，但也会问问他有没有见到自己的儿子。

深度优先搜索

如果Bruce说没看到Nemo，并向Marlin保证“鱼是朋友，不是食物”，Marlin就需要回到上级，寻找另一个他还没有问到的节点。回到Crush那里，他会发现下一步应该问Darla。由于Crush的所有后代现在都被审问过了，Marlin会回到Dory那里，检查她其余的“后代”。Marlin需要把每个角色询问一遍后才能找到Nemo。

深度优先搜索顺序

与广度优先搜索一样，深度优先搜索也包括时间复杂度O(n)，但空间复杂度可能有所不同。深度优先搜索通常占用较少的内存或空间，假设可以在遍历整个树之前找到目标节点。

由于二叉搜索树中的每增加一级节点会加倍(至少对于平衡树而言)，如果丢失的节点(Nemo)位于树的较低位置，则可以使用深度优先搜索来节省内存。在最坏的情况下，两种方法的空间复杂度都是O(n)。

关于二叉搜索树以及如何通过代码实现它们还有很多需要学习，但这个有趣的案例会成为你了解数据结构的起点。