正文

二叉树

由 n（ n > 0）个有限节点组成一个具有层次关系的集合，看起来就像一个倒挂的树，因此称这样的数据结构为树。

一个节点的子节点个数叫做度，通俗的讲就是树叉的个数。树中最大的度叫做树的度，也叫做阶。一个 2 阶树最多有 2 个子节点即最多有 2 叉，因此这样的树称为二叉树，二叉树是树家族中最简单的树。

两个叉的树就是二叉树，可这除了用来按一定结构存放数据外，跟查询性能好像也没关系，不会又是一个没用的噱头吧。

二分查找

听说二叉树的原始威力来源于一种叫做二分查找的算法。

相传在鹦鹉的原始社会，存在着森严的等级制度，每只鸟必须按高矮顺序分出等级和尊卑。

那么问题来了，如下图，怎样才能找出最高、最矮、中等高的那些鹦鹉呢、以及指定高度的那只呢?

第一种方法: 扫描法

一个一个依次测量，完毕后所有的问题都迎刃而解。

这种一个一个依次全部测量的方法叫做扫描，他的缺点很明显，最高和最矮，需要全部测量完毕才能知晓。

而对于指定高度，最好的情况是第一次就找到；最坏的情况是最后一次才找到，时间复杂度为 n，也就是说从 13 个鹦鹉中找到指定身高的那只，最坏的情况是查 13 次。

第二种方法：二分法

13 个鹦鹉全部听令，按从矮到高列队，向左看齐，报数。

报数字 1 的就是最矮的，报数字 13 的就是最高的，报数字 7 的就是中等身高的那只。

最好和最坏的情况都是一次找到。而查询性能一下子提高 13 倍，我的个乖乖，无论多个只鹦鹉，时间复杂度都是 1，好可怕。

问题：我不服，你这是偷换概念，有本事对比一个查找指定高度鹦鹉的性能。

因为鹦鹉们已经按高矮排好了队，所以指定高度的鹦鹉，要么是站中间那个只，要么就是在它的左边或右边的那群里。

如果是中间那个，一次就找到，如果不是只需要从中间左边或右边那一半中找，再在这一半中找中间那只，对比身高。

以此类推，每次都把查询的范围减半，时间复杂度log2(n)。那么 log2(13) 就是 4，最坏的情况也才 4 次，时间复杂度确实不是 1 了，但好像也不糟。

简化如下：

问题：如果按高矮排队，仍然需要一个一个比较，跟扫描有什么区别，那还不如直接扫描呢？

事实确实如此,单纯的一次查询，先排序，再二分查找，不见得比扫描快，甚至还不如。

但是，在数据的世界，大部分数据一生会被查询无数次，如果只在数据降生的时候排一次序，往后余生，是不是就可以直接用二分查找，这似乎就是传说的读多写少，以及对应的复用。

优点：

• 查找快

缺点:

• 必须有序，需要提前排序

• 每次查找都需要不断计算中间位置

二分查找树

如果一组数据不会或不常变更，那么他们的位置也基本不变。可是每次查询都需要重新计算中间位置是一种浪费，而浪费可耻。

我们能不能把所有中间节点组织起来，每次使用时，直接取中间节点?

请看下图，找到所有单次二分查找的中间节点，把他们连起来，并用手提起最中间的那个节点，就是一棵二分查找树。

优点：二分查找树就是通过数据结构的方式实现了二分查找算法，通过存储中间节点的数据，弥补了二分查找每次都要计算中间位置的缺点。

平衡二叉树:

如果二分查找树不断进行修改，比如删除某些节点，经过一段时间后，最早那个中间节点的数据（根），很可能就不在中间了。

中间位置就像一个天平的支点，如果他不在中间了，那么整个天平就会失衡，失衡的世界就会坍塌成不伦不类的瘸树，甚至是降维成一个链表或者数组。

二分查找算法的关键在于有序和中间节点，而二分查找树的关键是中间节点的维护，如果维护的节点已经不在中间了，那么它就失去了意义。

所以必须保证「二分查找树」是一个正确的树，一个根节点在中心的树，一个左右子树层级（高度）基本相等（高度相差不超过1）的树，一个平衡的树。

平衡二叉树中最常见的就是红黑树：

红黑树规定了一系列节点颜色规则，以及对应的左旋和右旋操作来保证颜色规则，从而达到树的平衡性。

看到这花里胡哨的颜色以及复杂的规则，让人第一眼就望而却步，但所有的这些，也不过是为了保证二叉树的平衡性，由于维持平衡的操作太过麻烦，无法用一句话简单概括，只好用一堆人鬼难分的规则和步骤来实现，只要按着这些步骤就一定能实现二叉树的平衡。

平衡二叉树 = 二分查找树 + 平衡（左右高度相差不超过 1 ）

平衡二叉树并未提高二分查找树的性能，它只是保正树不会被二向箔（多次增删改）打击降维成链表或不对称的残缺树，永远维持平衡。

另外，不仅仅是二叉树，其他种类的树，也是需要有序和平衡，才能发挥最大的威力。

多叉树之 B-tree

两个叉的树就能折半查询，理论可以提高一倍性能，那么多个叉是不是能提高更多倍性能？

如下图的 3 阶（叉）树（所有数据仅用于演示，非真实分布）

每个节点维护两个数据，并指向最多 3 个子节点。如图 3 个子节点的数据分别为：小于 17， 17 ~ 35 ，大于 35。

假设，从上图中查找 10 这个数，步骤如下：

1. 找到根节点，对比 10 与 17 和 35 的大小，发现 10 < 17 在左子节点，也就是第 2 层节点；

2. 从根节点的指针，找到左子节点，对比 10 与 8 和 12 的大小，发现 8 < 10 < 12，数据在当前节点的中间子节点，也就是第 3 层节点；

3. 通过上步节点的指针，找到中间子节点（第 3 层节点），对比 10 与 9 和 10 的大小，发现 9 < 10 == 10，因此找到当前节点的第二数即为结果。

加上忽略的 12 个数据，从 26 个数据中查找一个数字 10，仅仅用了 log ? 3 26 \log_3 26log326 ≈ \approx≈ 3 次，而如果用平衡二叉树,则需要 log ? 2 26 \log _2{26}log226 ≈ \approx≈ 5 次。事实证明，多叉树确实可以再次提高查找性能。

多叉树是在二分查找树的基础上，增加单个节点的数据存储数量，同时增加了树的子节点数，一次计算可以把查找范围缩小更多。

优点：二叉平衡树的基础上，使加载一次节点，可以加载更多路径数据，同时把查询范围缩减到更小。

复杂节点: 至此，我们列举的数据都是孤零零的单个数字。试想，你手里已经有一个数据 10，为什么还要费力吧唧的再从一堆数据中找到这个 10，自己找自己？这不是有病吗？

单个数字只能活在演示中，现实的世界要复杂的多，我们来看一个接近真实场景的案例。

现有一个以年龄为索引的 3 阶树，存储了一批用户信息，如下图：

数字为用户的年龄，其它为与树排序查找无关的业务数据，像这种索引数据与树排序查找无关的业务一起维护在节点的平衡多叉（阶）树称为 B- 树（ B 树）。

缺点：业务数据的大小可能远远超过了索引数据的大小，每次为了查找对比计算，需要把数据加载到内存以及 CPU 高速缓存中时，都要把索引数据和无关的业务数据全部查出来。本来一次就可以把所有索引数据加载进来，现在却要多次才能加载完。如果所对比的节点不是所查的数据，那么这些加载进内存的业务数据就毫无用处，全部抛弃。

总结

谈到面试，其实说白了就是刷题刷题刷题，天天作死的刷。。。。。

为了准备这个“金三银四”的春招，狂刷一个月的题，狂补超多的漏洞知识，像这次美团面试问的算法、数据库、Redis、设计模式等这些题目都是我刷到过的

并且我也将自己刷的题全部整理成了PDF或者Word文档（含详细答案解析），有需要的朋友可以戳这里即可免费领取

66个Java面试知识点

架构专题（MySQL，Java，Redis，线程，并发，设计模式，Nginx，Linux，框架，微服务等）+大厂面试题详解（百度，阿里，腾讯，华为，迅雷，网易，中兴，北京中软等）

算法刷题（PDF）