鱼C论坛

 找回密码
 立即注册
查看: 2703|回复: 0

[学习笔记] 《数据结构和算法》——多路查找树

[复制链接]
发表于 2017-8-26 16:45:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
2-3 树:
2-3树的节点可以储存两个或三个数据,但是必须保证的是,左侧的数据总比右侧的小,即一个数据左子树的数据总比其小,右子树的数据则相反。我们会使所有的叶子都在同一层,当增加数据时,可以将二节点变为三节点,从而尽可能的提高空间的利用率,当数据超过该深度可存储的数据个数时(即大部分都为三节点时),我们就将三节点拆成二节点,增加树的深度
删除2-3树中的元素是创建的逆过程,我们需要保证所有叶子在同一层,所有当删除的节点在一个三节点中时,我们只需要将三节点变为二节点;当删除的节点在一个二节点叶子上,我们从该节点的兄弟开始向根节点遍历,找到一个三节点,把他拆成两个二节点替代原来节点的位置;当2-3树是一个满二叉树的状态时,我们则将2-3树变成深度减1的新2-3树,来保证每个叶子在同一层

B树:一个m阶的多路查找树
1)若根节点不是叶子,则其至少有两个子树
2)若每一个节点都具有k-1个元素和k个孩子,其中k满足:[m/2]<=k<=m
3)所以叶子节点都位于同一层
4)每个节点都包涵关键字Ki和指向孩子节点的指针Ai

评分

参与人数 1鱼币 +2 收起 理由
小甲鱼 + 2

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 21:34

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表