寻找Nemo的乐趣：什么是二叉搜索树？

待我称王封你为后i 2022-12-13 12:58 144阅读 0赞

![format_png][]

全文共**2613**字，预计学习时长**7**分钟

![format_png 1][]

图源：unsplash

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

·        你的角色是男性还是女性？

·        男性。好，那他有胡子吗？

·        没有。好，他戴帽子吗？

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

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

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

![format_png 2][]

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

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

![format_png 3][]

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

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

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

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

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

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

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

![format_png 4][]

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

在字母表中，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了！

![format_png 5][]

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

什么是广度优先搜索？

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

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

![format_png 6][]

广度优先搜索

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

什么是深度优先搜索？

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

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

![format_png 7][]

深度优先搜索

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

![format_png 8][]

深度优先搜索顺序

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

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

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

![format_png 9][]

**推荐阅读专题**

[![format_png 10][]][format_png 10 1]

[![format_png 11][]][format_png 11 1]

[![format_png 12][]][format_png 12 1]

[![format_png 13][]][format_png 13 1]

![format_png 14][]

**留言点赞发个朋友圈**

**我们一起分享AI学习与发展的干货**

编译组：黄弈、苏韫琦

相关链接：

https://medium.com/swlh/data-structures-101-what-is-a-binary-search-tree-5514e08cc8f

如转载，请后台留言，遵守转载规范

**推荐文章阅读**

[ACL2018论文集50篇解读][ACL2018_50]

[EMNLP2017论文集28篇论文解读][EMNLP2017_28]

[2018年AI三大顶会中国学术成果全链接][2018_AI]

[ACL2017论文集：34篇解读干货全在这里][ACL2017_34]

[10篇AAAI2017经典论文回顾][10_AAAI2017]

**长按识别二维码可添加关注**

**读芯君爱你**

![format_png 15][]

[format_png]: /images/20221123/8712c82fc6504e9386b4c7ba0b328f57.png
[format_png 1]: /images/20221123/942af901f8774b6fbb80c66713b0bb1d.png
[format_png 2]: /images/20221123/01ea5df5c5014d67972367369135d130.png
[format_png 3]: /images/20221123/2552dd216119414a9f3961671f3bdfc9.png
[format_png 4]: /images/20221123/9f5f1537dd2e451698bb052ddd67dea8.png
[format_png 5]: /images/20221123/345859607f734bf599514f2b84f1706e.png
[format_png 6]: /images/20221123/cc7329d214ff41638895bf6d76e0c7da.png
[format_png 7]: /images/20221123/9723f07dbb234627b814fef277301683.png
[format_png 8]: /images/20221123/740e1778f3ae4e999b06588e378ccfb8.png
[format_png 9]: /images/20221123/bf2755812b9e4c849d38a2c0d75d2270.png
[format_png 10]: /images/20221123/46c6fb3617854cabb275e61248829547.png
[format_png 10 1]: http://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&chksm=ea841ec4ddf397d2bb194670056d7ed973cf4349656e20d98bd139d8a5d99526a799fb243f8d&idx=1&mid=2247493138&scene=21&sn=d2fa895e71260f2576fa952cf2487522#wechat_redirect
[format_png 11]: /images/20221123/dded7587054444a8a137a1b8dfb18d03.png
[format_png 11 1]: http://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&chksm=ea841ed9ddf397cf9a7136dfb1352cf9fb1127b3061293cf716f8ee95b4560e694fce20a1e24&idx=2&mid=2247493135&scene=21&sn=5711dc1074411b7e45b40eb34fecc648#wechat_redirect
[format_png 12]: /images/20221123/216a1e8a8c474fb6a3f5d07e2c0b4385.png
[format_png 12 1]: http://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&chksm=ea841ec4ddf397d28ed77a111732be52384c9be414e0aad59c570ada6b29278755d066ae2090&idx=2&mid=2247493138&scene=21&sn=e45fe93b00342ba9eac222f24369d036#wechat_redirect
[format_png 13]: /images/20221123/b61b7f47067d479c80bdab2a0fe3c063.png
[format_png 13 1]: http://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&chksm=ea841ed9ddf397cfbc27f47a160ee926a706f1b3151c53f707c8f221fde0ea51446aabe2148d&idx=1&mid=2247493135&scene=21&sn=cce4cc400933c960a3200fd0dfa4d0a7#wechat_redirect
[format_png 14]: /images/20221123/69fbd345d1c64e00967bfbbb3c913b93.png
[ACL2018_50]: https://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&chksm=ea87ee2addf0673cae27c598a097f5addad5d81b2ed766e570f20fc0fb12b77c5cf34098022e&idx=1&lang=zh_CN&mid=2247489276&scene=21&sn=98e22e2b69478303f1f1a0a51e712570&token=192322725#wechat_redirect
[EMNLP2017_28]: https://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&chksm=ea87eaadddf063bb3ab4ec5af616612a45f8d4fe9a5ad558f66278478296060253c1564bd05c&idx=1&lang=zh_CN&mid=2247488123&scene=21&sn=a55185f3a693f7a5d85b1abe3dd36177&token=140500370#wechat_redirect
[2018_AI]: https://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&chksm=ea87f6ebddf07ffd8e84bcc18d7122f894b6cf5dc967daad9c2e122edb22968fd6f589d6852f&idx=1&mid=2247487037&scene=21&sn=37cd38b305aa874c29d764361c88a202#wechat_redirect
[ACL2017_34]: https://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&chksm=ea87f59addf07c8c2480dd46784a431612d099d3d0531449aa8e64f68b3ba340363578d95659&idx=1&mid=2247486796&scene=21&sn=a8ae95efbf16985a259c4cd66bf919f2#wechat_redirect
[10_AAAI2017]: https://mp.weixin.qq.com/s?__biz=MzI2NjkyNDQ3Mw%3D%3D&idx=1&lang=zh_CN&mid=2247487100&scene=21&sn=3bd640ec4f00c5104664687194dd9a51&token=77118319#wechat_redirect
[format_png 15]: /images/20221123/ca53a3ed1fc444cab64795999b6b6e64.png