完整教程：数据结构——四十九、B树的删除与插入

文章目录

• 前言
• 一.B树的插入
• • 1.思路
  • 1.从0开始建立5阶B树
  • • 1.插入元素为超过结点容纳上限
    • 2.插入元素超出结点容纳上限且分裂后没有父结点没有超出上限
    • 3.插入结点且分裂后其父结点也超出上限
• 二.B树的删除
• • 1.思路
  • 2.具体例子
  • • 1.删除终端结点的关键字且删除后当前结点所含元素未低于下限
    • 2.删除非终端结点的关键字且删除后当前结点所含元素未低于下限
    • 3.删除终端结点的关键字且删除后当前结点所含元素低于下限且有兄弟大于下限
    • 4.删除终端结点的关键字且删除后当前结点所含元素低于下限且所有兄弟都等于下限
• 三.知识回顾与重要考点
• 结语

前言

保持节点关键字数量的平衡。当插入导致节点关键字超过上限时，会进行分裂：中间关键字提升到父节点，左右部分形成新节点。若父节点也超限，则继续向上分裂，可能导致树高增加。以5阶B树为例，演示了从初始插入到节点分裂的全过程，包括如何确定插入位置、处理节点分裂以及关键字提升等关键步骤。所有插入操作都在最底层终端节点进行，确保B树特性得以维持。就是B树插入处理的核心

一.B树的插入

1.思路

• 在插入key后，若导致原结点关键字数超过上限，则从中间位置($\lceil m/2\rceil$)将其中的关键字分为两部分，左部分涵盖的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置($\lceil m/2\rceil$)的结点插入原结点的父结点, 若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致M树高度增1。
• 如果一个关键字它源于分裂需要把它提到父节点当,那么我们应该把这个关键字放到它所属的节点的这条指针,所对应的这个点右边的位置
  
• 插入到最底层“终端节点”，用“查找”来确定插入位置,这样才能满足B树的失败结点只出现在最下面一层就是新元素一定

1.从0开始建立5阶B树

• 5阶B树——结点关键字个数$[m/2]-1\le n\le m-1$
  即：$2\le n\le 4$（注：此处省略失败结点）

1.插入元素为超过结点容纳上限

1. 插入第一个元素25,直接放在根节点中
   
2. 接下来插入第二个元素38,那38要比25更大,所以我们放在25后面
   
3. 再往后插入元素49放到38的后面
   
4. 通过接下来要插入的元素是60,60比49更大所以大家把它放在49的后面,此时根节点能够存放的元素已经到达了上限
   

2.插入元素超出结点容纳上限且分裂后没有父结点没有超出上限

1. 插入80,则会超出最大个数限制
   
2. 此时应该将该结点分裂为两个结点
   
3. 90肯定要插入到49,右边的指针所指的这个节点当中就是接下来我们要插入90这个元素,那从根节点出发,90要大于49,而49的右边已经没有别的关键字了于
   
4. 接下来检查这个节点中的关键字,60要小于90,80也要小于90,所以90应该插入到80的后面
   
5. 接下来我们插入99,和之前一样的操作
   
6. 再往后大家要插入88这个元素,和之前一样的操作,本来应该插入到80的后面
   
7. 此时该节点已经超出上限,则得分裂该结点,将中间元素88提到根节点中,然后把左右两个部分的元素分为两个新结点
   
8. 接下来插入83和87
   
9. 接下来要插入的节点是70,应该插入的位置是60和80的中间
   
10. 此时发现已经超出上限,则分裂它,由于需要保证其父节点当中的这些各个元素是有序的,因此插入到49和88中间
    
11. 接下来我们再插入三个元素,92,93,94
    
12. 很显然,又要分裂
    

3.插入结点且分裂后其父结点也超出上限

1. 继续插入73,74,75
   
2. 很显然,又要分裂
   
3. 这就导致了父结点需要分裂
   

二.B树的删除

1.思路

• 若被删除关键字在终端节点，则直接删除该关键字（要注意节点关键字个数是否低于下限$\lceil m/2\rceil -1$）

• 若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字
  直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
  直接后继：当前关键字右侧指针所指子树中“最左下”的元素

• 对非终端结点关键字的删除，必然可以转化为对终端结点的删除操作

• 兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法）
  当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺
  当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺

  

• 兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=「m/2」-1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

2.具体例子

1.删除终端结点的关键字且删除后当前结点所含元素未低于下限

1. 第一个要删除的元素是60该元素,由于60这个元素是在终端节点当中,并且删除60之后,当前被删除的这个节点,它的关键字个数并没有低于2
   

2.删除非终端结点的关键字且删除后当前结点所含元素未低于下限

1. 删除80,找出80这个元素的直接前驱或者直接后继来顶替80的位置
   1. 如果用直接前驱(当前关键字左侧指针所指子树中“最右下”的元素)77来顶替,然后将原本的77删除
      
   2. 要是用直接后继(当前关键字右侧指针所指子树中“最左下”的元素)82来顶替,继而将原本的82删除
      

3.删除终端结点的关键字且删除后当前结点所含元素低于下限且有兄弟大于下限

1. 删除38
   
2. 当前节点已经低于下限,观察其右兄弟里边关键字的数量还够,因此让他的父结点第一个的元素49进入到当前结点
   
3. 然后让兄弟中第一个的元素70去顶替父节点中空缺的位置
   
4. 删除90
   
5. 发现其已经低于下限且右兄弟节点元素不足以借给它(借给它就会低于下限),因此看它的左兄弟,发现其节点元素充足,因此因此将其父结点的第一个元素给当前节点
   
6. 再用左兄弟节点的最后一个元素顶替父节点空缺的位置
   

4.删除终端结点的关键字且删除后当前结点所含元素低于下限且所有兄弟都等于下限

1. 删除49
   
2. 所有兄弟拥有的元素个数都等于下限,此时将当前结点和兄弟结点进行一个合体,除了这两个节点之外大家还要求把这两个节点它们中间的这个关键字(两个指针中间夹着的关键字)给一起合并到一个节点当中
   
3. 发现其父节点又低于下限了,按照之前的情况分类,接下来大家还需要把这个节点还有他的右兄弟进行一个合并
   
4. 此时根节点没有任何关键字,因此将其删除
   

三.知识回顾与重要考点

非终端节点被删除都是被直接前驱或直接后继替代(转化为了对终端节点的删除),因此不可能出现低于下限的情况

结语

五更

假设想查看更多章节,请点击:一、数据结构专栏导航页