B 树 – 高效的多路平衡搜索树

2017年9月2日11:13:45 发表评论 30

一棵M阶(M>2)的B树,是一棵M路平衡搜索树,可以是空树或者满足以下性质:

  1. 根节点至少有两个孩子
  2. 每个非根节点有 [ ⌈M/2⌉, M] 个孩子
  3. 每个非根节点有 [ ⌈M/2⌉-1, M-1] 个关键字,并且以升序排列
  4. key[i] 和 key[i+1] 之间的孩子节点的值介于 key[i]、key[i+1] 之间
  5. 所有的叶子节点都在同一层

ps: ⌈x⌉ 是向上取整

下图是一颗 M 阶B树

B 树 - 高效的多路平衡搜索树

为了便于理解B 树,这里只实现了Find、Insert、InOrder

 

  • A+
所属分类:

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: