个人理解浅谈数据结构，应对八股文面试
目录
前言
因为博主将要实习，所以最近在备痛苦的八股文，因为涉及到了数据结构，所以在此总结一下。
一、二叉搜索树（二叉排序树、二叉查找树、AVL树）
相信我们大家学计算机相关专业的同学都上过数据结构课，所以都明白什么是树、二插树，因为要提高搜索效率，所以开发出了二叉树
（1）二叉树的特点：
1.非空左子树节点的键值大于根节点的键值
2.非空右子树节点的键值小于根节点的键值
3.左右子树均为二叉搜索树
（2）二叉树的优缺点
二叉树一定程度上增加了检索的效率，但是会存在一个致命的问题就是，当序列是1,2,3,4,5,6的时候，会发现他的结构是一个链表，所以为了应对这种问题，出现了红黑树跟平衡二叉树
二、平衡二叉树（高度平衡树，最早的自平衡二叉树）
（1）平衡二叉树的特点：
1.是二叉排序树
2.任意节点左右子树的高度差小于一
3.任意节点的左右子树都是平衡二叉树
（2）平衡二叉树的优缺点
1.查找、插入删除性能好，相对于二叉搜索树，树的高度可以保持较小，查找路径较短
2.实现复杂，通过左右旋转来调整平衡，会有时间的消耗，效率低于红黑树
三、红黑树
（1）红黑树的特点
1.根节点是黑色，所有节点只有红黑两种颜色
2.叶子节点是黑色
3.一个红色节点一定包含两个黑色节点
4.任意一节点到根节点的所有简单路径包含相同黑色节点的数目（黑高）
（2）红黑树的优缺点
跟平衡二叉树一样，提高了查找、插入和删除的性能，同时因为其特性需要时间的消耗
四、红黑树和平衡二叉树有啥不一样
个人觉得红黑树跟平衡二叉树是一样的，而且现在红黑树已经逐渐取代了平衡二叉树，如果非要说出个不一样：
1.红黑树因为规则更加严格全面性能略优
2.红黑树的实现比平衡二叉树复杂
3.红黑树的空间消耗比二叉树更多
4.红黑树的平衡性比二叉树更好
具体可以根据不同的应用场景选择使用
五、B树（多路平衡树）
之前介绍的结构存在一个问题，当我们需要存储大量的数据并使用的时候，不论是红黑树还是平衡二叉树都存在一个问题：深度问题，当其深度过于深，像是外部存储设备、磁盘这种应用场景会发现他的检索效率是要高于他的比较效率，占用cpu浪费了大量的资源，所以开发出了B树
（1）B树的特点
1.所有键值存在整棵树的每一个节点中
2.每个节点的关键字出现仅出现一次
3.关键字内做一次查找，他的性能是逼近二分查找的
4.左子树所有关键值大于他，右子树都小于他
（2）B树的优缺点
1.减少了磁盘的I/O操作，大型数据集的查找和访问是非常高效的
2.节点的分裂和合并的过程相对复杂，数据经常插入删除维护成本高
六、B+树
（1）B+树的特点
1.所有键值分布在叶子节点
2.在叶子节点之间增加了一个链指针
3.关键字出现仅出现一次
4.左子树所有关键值大于他，右子树都小于他
（3）B+树的优缺点
优缺点跟B树的优点一样，但是所有叶子结点链表链接，增加了区间的访问性和范围查询
七、B树跟B+树的区别
现在的大多数场景用的都是B+树，B+树是B树的变体，他两的关系本人觉得更像是平衡二叉树和红黑树的关系，像是mysql等，但是如果考虑到实现的复杂和空间的有限性，可以斟酌这两个的使用，B+树的缓存命中性是要高于B树的。
1.大量的范围查询适合B+树，如mysql
2.单个KEY的查询可以考虑B树，如NOSQL、MongoDB
总结
之前因为博主在这边培训，但是不知道大家有没有培训过，培训的内容真的是很简单，脱节跟现在，而且培训的环境真是是非常非常的差，很多人很嘈杂，老师教学生安装环境和软件就安装一上午，弄得我的状态很不好，很不适应，所以很长时间没有，更新。最近才调整过来，调整好心态，晚自习会自己找一个空教室学习，培训的教室很是乱，没人管都是打游戏的，真的拴扣。
这边建议宝子们学习的时候可以脱离本来的环境，像是我找了一个安静的地方就觉得心理宁静多了，同时希望大家可以跟我一样努力加油。在之后的日子里博主会持续更新，更新八股文等内容。
标签：优缺点,二叉,AVL,二叉树,红黑树,平衡,节点 From： https://blog.csdn.net/m0_64882384/article/details/137379401