Folders and files Name Name Last commit message
Last commit date
parent directory
View all files
树中每个结点最多含有m个孩子(m >= 2)
除根结点和叶子结点外，其他每个结点至少有[ceil(m / 2)] 个孩子（其中ceil(x) 是一个向上取整的函数）
若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根结点）
所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息
每个非终端结点包含有n个关键字信息：（P1，K1，P2，K2，P3, ....... , Kn, Pn + 1）
Ki(i = 1 …. n) 为关键字，且关键字按顺序升序排序K(i - 1) < Ki
Pi为指向子树根的接点，且指针P(i)指向子树中所有结点的关键字均小于Ki，但都大于K(i - 1)
关键字的个数n必须满足：[ceil(m / 2) - 1] <= n <= m - 1
判断叶子结点的结点个数是在 [ceil(m / 2) - 1] <= n <= m - 1
叶子未满写入
页外结点
页内结点
找到需要插入的中间结点i, 然后判断子结点child[i]
判断子结点child[i]的值长度是否 >= m -1，是，则需要叶分裂
叶子结点 >= m - 1, 叶分裂
前提
创建一个新的结点 n1
当前结点为 n2
父结点为 p
富裕结点 ceil(m / 2) 为 m1
把 n2 数量大于 m1 的结点的值移动 n1上
如果是中间结点进行叶分裂，则需要把n2数量大于 m1 的子结点移动到 n1的子结点上
把p上的子结点往后移动1位，n1填充到p的子结点的第一位
把p上的值往后移动1位，把 n2 的 m1 -1 位移动到 p的值列表的第一位
p的值数量+1
直接找到值，就返回
如果没有直接找到值，且是叶外结点，就返回NULL
没有直接找到值，需要到子结点查找
删除
直接找到值
页外结点
页内结点
选择富有的左孩子结点（>= m1）
查找左孩子结点的最后一个元素移至父节点的位置
然后删除左孩子结点的最后一个元素
选择富有的右孩子结点(>= m1)
查找右孩子结点的第一个元素移至父节点的位置
然后删除右孩子结点的第一个元素
左右孩子刚脱贫
没有直接找到值
查找当前的值的子结点 c1
c1为刚脱贫的情况
获取当前值的左兄弟结点（ls），获取当前值的右兄弟结点(rs)
rs 比较富有
则该孩子结点先向父结点借一个元素
右兄弟中的第一个元素上移至父结点所借的位置，并进行相应调整
ls比较富有
则该孩子向父结点借一个元素
左兄弟中最后元素上移至父结点所借位置，并进行相应的调整
rs或ls刚脱贫
c1比较富有的情况
获取当前的结点 n 的左子结点(lc)和右子结点(rc)
把n的值移动lc的最后一位上
并把rc上的值和子结点合并到lc
n中下移结点后元素进行前移。n的结点长度-1
You can’t perform that action at this time.