1回答

liuyubobobo

2021-11-03

树这种数据结构出现的原因，就在于顺序存储数据（数组，链表，等）会使得很多操作的复杂度是 O(n) 级别的。而树让增添改查的操作都降到了 O(logn) 级别。通过这个课程排序部分的介绍，你应该已经看到了，O(n) 和 O(logn) 是差别巨大的。（对应到排序算法中，O(n^2) 的排序算法和 O(nlogn) 的排序算法，是差别巨大的。）

当然了，单纯的二分搜索树是有局限性的，核心局限性是，二分搜索树是可能退化的。因此有了 AVL 树，有了红黑树，他们本质都是二分搜索树，在这个基础上，加入了自平衡的机制。（在我的算法体系课程中，我带领大家实现了基础的 AVL 树和红黑树，只需要在二分搜索树的代码的基础上修改就好了。有兴趣可以参考：https://class.imooc.com/sale/datastructure  ）

当然更进一步，考虑到比如磁盘读写访问扇区的限制，就又有了 B 树或者 B+ 树，他们在名称上已经和二分搜索树没有关系了，但其实背后的思想是一致的（或者说是一脉相承的）。

当然，二分搜索树并不是唯一一个可以快速做增删改查的数据结构，（另外一个经典的数据结构是哈希表），但二分搜索树的另一个主要特性是：有序。既可以快速访问其中每一个元素的前一个元素，后一个元素，快速查找比某一个值大的最小元素，或者比每一个值小的最大元素，以及访问整个数据集中的最大值和最小值。

==========

一两次面试失败是很正常的。整理心情，继续加油！：）

0

4

liuyubobobo

回复

gotodream

没有办法。面试不是考试，不是都答对了就一定能过。很多时候面试看的是眼缘，也看你的精气神，表达，自信，等等这些看起很“虚”的东西。打起精神，自信一点。参加十几场面试才拿到 offer 是正常的。加油！：）

2021-11-18

共4条回复