数据结构中常见的树

朴灿烈づ我的快乐病毒、 2023-10-12 23:18 79阅读 0赞

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

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

# 二叉树 #

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

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

# 二叉搜索树 #

二叉树的左子树的所有节点都会小于根节点，右子树的所有节点值都大于根节点。

利用这个性质，我们就无需遍历整个二叉树，就能快速定位到我们想要找的节点。

但是人们又发现如果我们存储的数据刚好是有序的，比如是1，2，3，4。那么你就会发现二叉树就逐渐退化成了链表的形态。

最坏的情况还是需要遍历所有的节点。于是平衡二叉树就应运而生了。  
![在这里插入图片描述][bb0030199c954b50ae62db988c69cf54.png]

# 二叉平衡树 #

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

但是他实在过于严格，一旦出现不平衡的情况，便会进行旋转调整。但这操作却有相当的耗时且复杂。因此，为了解决这个问题，红黑树便出现了。  
![在这里插入图片描述][fe09fd34f1d6484cb96b2b213dc70212.png]

# 红黑树 #

他规定了每个节点要么是黑色，要么是红色。

其次根节点必须是黑色的，每个叶子节点是黑色的。每个红色节点的两个子节点一定都是黑色的。

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

红黑树相比于平衡二叉树来说，它是一种弱平衡二叉树。高度一般要高于平衡二叉树。

同时对于红黑树来说，他的旋转次数通常要小于平衡二叉树，因此平衡二叉树查找快，删除和插入较慢。而红黑树则相反，红黑树查找慢，插入、删除快。  
![在这里插入图片描述][013b153a29ee4d68be6aa112ed8b914d.png]

# b树 #

b树出现是因为磁盘io操作的效率问题。由于io效率非常低，当我们有大量的数据时，我们无法将所有的数据一次性全部加载到内存当中。

只能逐一加载磁盘页，每个磁盘页对应树中的一个节点。  
![在这里插入图片描述][1fcfb5353cf845d78efa24554aca9e8d.png]  
mysql当中默认是16k，最坏的情况下树的高度就决定磁盘的io次数。

平衡二叉树由于树的深度过大而造成磁盘io次数可能会较多，进而导致效率低下。  
![在这里插入图片描述][c7a9322b4f6f41dcaf463f6e0d273a2b.png]  
而我们的目标就是要将高瘦的树转变成矮胖的树。因此b树不再是二叉树，而是一个平衡的多叉树。  
![在这里插入图片描述][957b054562ff4d8889bda25f5f41e1f9.png]  
相同节点个数的情况下，b树最坏情况下是三次io，而平衡二叉树是4次。

# b+树 #

因为b树适用于磁盘存储，因此mysql的索引数据结构使用的就是加强版b+树。

相对于b树而言，b+树将所有的数据全部放在了叶子节点。非叶子节点只存储索引值。这意味着每一个节点可以存储更多的索引值。

同时b+树的叶子节点通过链表相连，更适合范围查找。

**参考资料**：[花两分钟盘点数据结构中常见的树 | 假期轻松学习][Link 1]

[d9d4330309404f1cb88a6f422445661b.png]: https://img-blog.csdnimg.cn/d9d4330309404f1cb88a6f422445661b.png
[bb0030199c954b50ae62db988c69cf54.png]: https://img-blog.csdnimg.cn/bb0030199c954b50ae62db988c69cf54.png
[ee6029721c614a08ae3c08e325dc5fb7.png]: https://img-blog.csdnimg.cn/ee6029721c614a08ae3c08e325dc5fb7.png
[fe09fd34f1d6484cb96b2b213dc70212.png]: https://img-blog.csdnimg.cn/fe09fd34f1d6484cb96b2b213dc70212.png
[013b153a29ee4d68be6aa112ed8b914d.png]: https://img-blog.csdnimg.cn/013b153a29ee4d68be6aa112ed8b914d.png
[1fcfb5353cf845d78efa24554aca9e8d.png]: https://img-blog.csdnimg.cn/1fcfb5353cf845d78efa24554aca9e8d.png
[c7a9322b4f6f41dcaf463f6e0d273a2b.png]: https://img-blog.csdnimg.cn/c7a9322b4f6f41dcaf463f6e0d273a2b.png
[957b054562ff4d8889bda25f5f41e1f9.png]: https://img-blog.csdnimg.cn/957b054562ff4d8889bda25f5f41e1f9.png
[Link 1]: https://www.bilibili.com/video/BV1ph41197mx/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb