数据结构中常见的树

男娘i 2024-03-17 12:17 11阅读 0赞

#### 数据结构中常见的树 ####

*  二叉树
 *  二叉搜索树
 *  平衡二叉树
 *  红黑树
 *  b树
 *  b+树

## 二叉树 ##

由一个根节点和两个左右子树组成，实现树形结构的存储。

但是人们逐渐发现二叉树查找起来效率不是很高。想要查找一个10元素，可能需要遍历整个二叉树才能找到。  
![在这里插入图片描述][d9d4330309404f1cb88a6f422445661b.png]  
于是就出现了二叉搜索树。

## 二叉搜索树 ##

二叉树的左子树的所有节点都会小于根节点，右子树的所有节点值都大于根节点。利用这一性质，我们就可以不用遍历整个二叉树就可以快速定位到我们想要找的节点。  
![在这里插入图片描述][afac9ae380d24718b901d8abb4660660.png]  
如果我们存储的数据刚好是有序的，比如1234你就会发现二叉树就逐渐退化成了链表的形态。最坏的情况下还是需要遍历所有的节点。  
![在这里插入图片描述][4ed65e9c4686411b9cd885b33e118e98.png]  
于是平衡二叉树就应运而生了。

## 平衡二叉树 ##

他规定树的左右两个子树的高度差的绝对值不超过1。  
![在这里插入图片描述][7e644189fb5443ebb3397371bb73b4dc.png]  
由于这一规定，我们就可以很好地避免二叉树退化为链表的情况。一旦出现不平衡的状态，平衡二叉树就会进行旋转来调节左右子树的平衡，使之达到平衡。

平衡二叉树固然好，但是他实在过于严格，一旦出现不平衡的情况，便会进行旋转调整，但这操作却又相当的耗时和复杂。

因此为了解决这一问题，红黑树便出现了。

## 红黑树 ##

![在这里插入图片描述][e3c3f8af65bc4eec92edbd77699400db.png]  
他规定了每个节点要么是红色，要么是黑色。其次根节点必须是黑色，每个叶子节点是黑色的。每个红色节点的两个子节点一定都是黑色的。

任意节点到每个叶子节点的路径都包含数量相同的黑节点。

红黑树相比于平衡二叉树来说，它是一种弱平衡二叉树，高度一般要高于平衡二叉树。同时，对于红黑树来说，它的旋转次数通常要小于平衡二叉树，因此平衡二叉树查找快，插入和删除较慢，而红黑树则相反。  
![在这里插入图片描述][7c8aaf94a35040b2b7d0d30e5a8ff52f.png]

## b树 ##

既然平衡二叉树已经如此优秀了，为什么还会出现b树呢，b树出现是因为磁盘IO操作的效率问题。由于磁盘IO效率非常低，当我们有大量的数据时，我们无法将所有的数据一次性全部加载到内存当中，只能逐一加载磁盘页，每个磁盘页对应树中的一个节点。mysql当中默认是16k，最坏的情况下树的高度就决定磁盘的io次数。  
![在这里插入图片描述][077a1e5ae2374768867dc73e7b53924a.png]  
平衡二叉树由于树的深度过大而造成磁盘io次数可能会较多，最终导致效率低下。而我们的目标就是要将高瘦的树转变成矮胖的树。  
![在这里插入图片描述][0e67543cf7a94caa918dd9e3f9c8af1b.png]  
因此，b树不再是二叉树，而是一个平衡的多叉树，相同节点个数的情况下，b树最坏情况下是三次io，而平衡二叉树是4次。

## b+树 ##

因为b树更适用于磁盘存储，因此mysql的索引数据结构使用的就是加强版b+树。相对于b树而言，b+树所有的数据全部放在了叶子节点，非叶子节点只存储索引值。这意味着每一个节点可以存储更多的索引值，同时b+树的叶子节点通过链表相连，更适合范围查找。  
![在这里插入图片描述][48f6d1a880bd40249b0142b695e721ea.png]  
**参考资料**：[花两分钟盘点数据结构中常见的树 | 假期轻松学习][Link 1]

[d9d4330309404f1cb88a6f422445661b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ddb48280cb2f4364b01d1c4e96b67b51.png
[afac9ae380d24718b901d8abb4660660.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4058f9fa4931453c81583fc64885c4f5.png
[4ed65e9c4686411b9cd885b33e118e98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f50ce02242ce4f4aa0b0dc6b2eb3274b.png
[7e644189fb5443ebb3397371bb73b4dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/be11893c1b584edeaca1a0c5c9c24450.png
[e3c3f8af65bc4eec92edbd77699400db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cd67bef2e48e482ca9529feb927d1dd1.png
[7c8aaf94a35040b2b7d0d30e5a8ff52f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/97fb58ae374d4539a6c28fb1116a13d3.png
[077a1e5ae2374768867dc73e7b53924a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ab76f06a62864759b9837bf2bb479114.png
[0e67543cf7a94caa918dd9e3f9c8af1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0dca3a5d4f41482d91b676e509078f23.png
[48f6d1a880bd40249b0142b695e721ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d4da19c4224946a2a337878245dc3ac0.png
[Link 1]: https://www.bilibili.com/video/BV1ph41197mx/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb