本文转载自公众号《核心阅读》（ID：AI_Discovery）。在生活中，我们经常需要寻找一些东西或做出决定。一个简单的方法是将选择一分为二。假设您正在玩“猜猜我是谁”的游戏，目标是猜测您的对手选择了哪个角色。然后你可以问他们这样的问题：你的角色是男性还是女性？男性。好的，他有胡子吗？不，嗯，他戴帽子吗？我们继续在每一步推断我们的选择。同样，二叉搜索树通过减少每一步的选项来帮助找到你想要的东西。首先，二叉搜索树到底是什么？二叉搜索树(BST)是一种特殊类型的树数据结构，由节点及其子节点组成。子节点也被认为是“后代”，可以想象成一棵倒立的树或树的根。每个节点最多可以有2个子节点：左节点和右节点。为了使其成为有效的二叉搜索树，左节点的值必须始终小于父节点，而右节点的值必须始终大于父节点。没有任何间隙的BST，即每个节点都有一个左节点和一个右节点的二叉搜索树，称为“完美”树。在一棵完美的树中，随着树的遍历，每一层的节点数都会翻倍，将所有先前的节点相加，然后在该数字上加“1”，得出底层节点的总数。在平衡二叉搜索树中搜索元素时，平均需要O(logn)时间，或在最坏情况下为O(n)。您可以将二叉搜索树中的搜索视为“选择您自己的冒险”模型，从顶部节点开始，沿着树向下，在到达的每个节点处询问相同的2个问题。我要查找的值是否小于当前节点？如果是这样，请向左走。我要查找的值是否大于当前节点？如果是这样，请向右走。插入和删除也非常快，平均花费O(logn)时间。但是有一个缺点就是不能像数组那样获取随机元素。你什么时候会使用二叉搜索树？假设您需要为Facebook这样的社交媒体应用程序设计一个数据库。数据库需要处理数百万个用户名，其中一个需要在登录时快速检索。由于每天都有新的账号注册或删除，所以你还需要方便插入和删除操作。通过排序数组进行二分查找会非常快（需要O(logn)时间），但是插入或删除用户名将导致整个数组重新排序，需要O(n)时间，具体取决于数组大小，它可能相对缓慢。如果我们使用二叉搜索树，插入或删除会快得多（需要O(logn)时间）。如果你有一个带名称的二叉搜索树（比如这个《海底总动员》树），你可以按字母顺序对它进行排序。在字母表中，Dory在Marlin之前，所以它是左节点，而Moonfish在Marlin之后，所以它是右节点。同样，下一层的搜索也遵循这个规则。Bruce在Crush之前，在Dory和Marlin之前。Darla在Crush之后但在Dory和Marlin之前出现。现在准备好了，是时候去找尼莫了！寻找尼莫！假设您已经有了一个有效的二叉搜索树并且需要找到Nemo。因为我们知道树中的节点是按字母顺序排序的，所以这应该相当简单。从Marlin开始，左边是Dory，右边是Moonfish。我们知道Nemo在字母表中排在Marlin之后，因此我们将遍历到正确的节点（Moonfish）。Nemo按字母顺序排在Moonfish之后，因此继续向下到Moonfish的右子节点。幸运的是，它是……尼莫！找到尼莫！非常有效率。二叉搜索树降低了整个搜索过程的时间复杂度！如果树没有分类，只是一个普通的树结构呢？或者证明这是一个二叉搜索树？目前有两种不同的搜索技术来实现这一点。什么是广度优先搜索？广度优先搜索是一种一次遍历树（或图）一层的方法，每次都在节点之间从左到右移动。在《海底总动员》的例子中，马林会先问多莉，“你知道我儿子尼莫在哪里吗？”如果它拒绝，Marlin会问Moonfish同样的问题。如果它也说不行，马林会进入下一层，询问Crush、Gill和Mr.Ray，然后马林会找到尼莫！广度优先搜索如果在Mr.Ray之后没有找到Nemo，Marlin将进入下一级别询问Bruce和Darla等等。使用广度优先搜索找到起始节点(Marlin)和目标节点(Nemo)之间的最短距离。时间复杂度是O(n)，因为在最坏的情况下，需要检查每个节点才能找到Nemo。什么是深度优先搜索？深度优先搜索是一种从顶部节点一直向下遍历树（或图）到其最远子节点的方法，然后返回并尝试其他路径。在《海底总动员》的例子中，马林首先问多莉“你知道尼莫在哪里吗？”如果她不同意，他会向Crush提出同样的问题，因为Crush是Dory最左边的孩子。如果Crush也拒绝了，Marlin会更上一层楼问Bruce，尽管他害怕成为鲨鱼的零食，但他是否见过他的儿子。深度优先搜索如果Bruce说他没有看到Nemo，并向Marlin保证“鱼是朋友，而不是食物”，Marlin需要返回并寻找他尚未询问的另一个节点。回到Crush那里，他会发现接下来他应该问Darla。由于Crush的所有后代现在都已被审问，Marlin将回到Dory那里检查她其余的“后代”。Marlin需要要求每个角色找到Nemo。深度优先搜索顺序与广度优先搜索一样，深度优先搜索也包括时间复杂度O(n)，但空间复杂度可能会有所不同。深度优先搜索通常需要较少的内存或空间，假设可以在遍历整个树之前找到目标节点。由于二叉搜索树中每增加一级节点都会加倍（至少对于平衡树而言），如果缺失节点(Nemo)在树中较低，则可以使用深度优先搜索来节省内存。在最坏的情况下，两种方法的空间复杂度都是O(n)。关于二叉搜索树以及如何在代码中实现它们，还有很多东西需要学习，但这个有趣的示例将作为您理解数据结构的起点。
