B-Tree

前言

感觉严蔚敏的数据结构中关于BTree的操作过于理想。尤其是删除操作的判断兄弟节点。再把最大最小上移。感觉很啰嗦。于是自己抽象了几个元操作。插入删除都可以由此转换。有了down操作后其实都不用找最小叶节点再交换了。可以把要删除的值一路down到最底层。

元操作

• split 操作

• pull 操作

• down 操作

• check 操作 检查是否符合B-Tree树性质

删除和插入操作（递归）

• insert

  • 操作元素

    • 当前工作节点 n
    • 状态量 tag

  • 定义

    • n 为空：创建一个叶子节点,tag = 2
    • tag = 0 ： return
    • tag =1 ： 更新子节点，tag=0
    • tag = 2：pull 操作
      • check 为假：split 操作, tag = 2
      • check 为真：tag=1

• delete

  • 操作元素

    • 当前工作节点 n
    • 状态量 tag

  • 定义

    • 删除后check为真：tag=0, return
    • 删除后check为假：tag=1, return
    • tag=0: return
    • tag=1: 更新子节点
      • check 为真 tag=0 return
      • 兄弟节点为⌈m/2⌉：对n节点split,再down操作,tag=1
      • 兄弟节点子树>⌈m/2⌉：对n节点split,再down操作，再对子节点split, 再pull操作。tag=1