您当前的位置: 首页 >  b树
  • 2浏览

    0关注

    880博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【大话数据结构C语言】58 多路查找树(B树)之2-3树

CodeAllen嵌入式编程 发布时间:2021-05-19 22:35:13 ,浏览量:2

欢迎关注我的公众号是【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的右孩子
 
 
 
 
 
 
 
 
 
 
 
 
 
关注
打赏
1665938897
查看更多评论
立即登录/注册

微信扫码登录

0.0957s