【大话数据结构C语言】58 多路查找树（B树）之2-3树
【摘要】
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取精品学习资源 程序员技术交流①群：736386324 程序员技术交流②群：371394777
多路查找树
由于涉及到去内存读取数据的问题，此时内存存取外村次数成为实现效率上的瓶颈，这就迫使要打破每一个结...
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取精品学习资源
程序员技术交流①群：736386324
程序员技术交流②群：371394777
多路查找树
由于涉及到去内存读取数据的问题，此时内存存取外村次数成为实现效率上的瓶颈，这就迫使要打破每一个结点只存储一个元素的限制，为此引入了多路查找树的概念
多路查找树，其每一个结点的孩子树可以多于两个，且每一个结点处可以存储多个元素
2-3树
2-3树其中每一个结点都具有两个孩子（2结点），或者三个孩子（3结点）
一个2结点包含一个元素和两个孩子（或者没有孩子）
一个3结点包含一小一大两个元素和三个孩子（或者没有孩子）
2-3树的插入实现
2-3树插入分为三种情况
1.对于空树，插入一个2结点即可
2.插入结点到一个2结点的叶子上，如下图所示
3.要往3结点插入一个新元素
第一种情况
另一种情况
还有一个例子
上诉例子可以说明，如果使用2-3树插入的传播效应导致了根结点的拆分，则树的高度就会增加
2-3树的删除实现
删除也是分为三种情况，但是与插入相反，从3结点开始说起
因此对于删除叶子是2结点的情况，需要分成四种情况处理
1.此结点的双亲也是2结点，且拥有一个3结点的右孩子，如下图所示
删除结点1，只需要左旋，即6成为双亲，4成为6的左孩子，7是6的右孩子
文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。
原文链接：allen5g.blog.csdn.net/article/details/117048463
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）