java做gui界面，看完这篇彻底明白了

柔光的暖阳◎ 2022-10-19 15:49 218阅读 0赞

## 正文 ##

### 二叉树 ###

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

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

![image.png][]

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

### 二分查找 ###

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

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

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

![image][]

### 第一种方法: 扫描法 ###

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

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

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

### 第二种方法：二分法 ###

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

![image.png][image.png 1]

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

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

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

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

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

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

简化如下：

![image.png][image.png 2]

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

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

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

优点：

*  查找快

缺点:

*  必须有序，需要提前排序
 *  每次查找都需要不断计算中间位置

### 二分查找树 ###

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

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

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

![image.png][image.png 3]

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

平衡二叉树:

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

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

![image.png][image.png 4]

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

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

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

![image.png][image.png 5]

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

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

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

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

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

### 多叉树之 B-tree ###

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

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

![image.png][image.png 6]

每个节点维护两个数据，并指向最多 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 阶树，存储了一批用户信息，如下图：

![image][image 1]

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

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

# 总结 #

我个人认为，如果你想靠着背面试题来获得心仪的offer，用癞蛤蟆想吃天鹅肉形容完全不过分。想必大家能感受到面试越来越难，想找到心仪的工作也是越来越难，高薪工作羡慕不来，却又对自己目前的薪资不太满意，工作几年甚至连一个应届生的薪资都比不上，终究是错付了，错付了自己没有去提升技术。

这些面试题分享给大家的目的，其实是希望大家通过大厂面试题分析自己的技术栈，给自己梳理一个更加明确的学习方向，当你准备好去面试大厂，你心里有底，大概知道面试官会问多广，多深，避免面试的时候一问三不知。

大家可以把Java基础，JVM，并发编程，MySQL，Redis，Spring，Spring cloud等等做一个知识总结以及延伸，再去进行操作，不然光记是学不会的，这里我也提供一些脑图分享给大家：

![ead1da67855c73a39d6c8854b1f05e9f.png][]

![f9f27195533ce3dbcb0820c50edbb37c.png][]

![9c5ec7e096c6baf0e39b1fb6e0fd96f1.png][]

希望你看完这篇文章后，不要犹豫，抓紧学习，复习知识，准备在明年的金三银四拿到心仪的offer，加油，打工人！

pqKi-1626014646737)\]

\[外链图片转存中…(img-eiRKdesr-1626014646737)\]

\[外链图片转存中…(img-8AMGyKNO-1626014646738)\]

希望你看完这篇文章后，不要犹豫，抓紧学习，复习知识，准备在明年的金三银四拿到心仪的offer，加油，打工人！

**[领取资料只需要点击这里即可免费获取全部资料！][Link 1]**

[image.png]: /images/20221004/f8751dabc5c645e98323ad91c57d4638.png
[image]: /images/20221004/53da802bfd0446ecb20f473f935b8355.png
[image.png 1]: /images/20221004/41a006cf343c4198bb2aa8a957401b69.png
[image.png 2]: /images/20221004/3ccc60b55a494811844db70f82447d6c.png
[image.png 3]: /images/20221004/38f1781ef7a24e93918f3f1f329065b7.png
[image.png 4]: /images/20221004/bcf29e5d0b7d4a5585a559e327a7d30b.png
[image.png 5]: /images/20221004/62ac9a6a7fa9413ba81df612466a6c3e.png
[image.png 6]: /images/20221004/c65908882d5349499db68148848c3bf1.png
[image 1]: /images/20221004/c2e3b101110649edb9ecb11e118b4295.png
[ead1da67855c73a39d6c8854b1f05e9f.png]: /images/20221004/aa733734646649c582d048fe8c504880.png
[f9f27195533ce3dbcb0820c50edbb37c.png]: /images/20221004/7c2e421e42e54f63a8a1469eae7aeba2.png
[9c5ec7e096c6baf0e39b1fb6e0fd96f1.png]: /images/20221004/b5e4de2aedcd402685c1056855a683c1.png
[Link 1]: https://gitee.com/vip204888/java-p7