数据结构·树型查找与B树

树型查找

二叉排序树（BST）

• 定义
• 查找
• 插入
• 构造
• 删除
• 查找效率分析

平衡二叉树（AVL）

• 定义
• 插入
• 删除
• 查找

红黑树

• 定义
• 插入
  • 看叔叔脸色
    • 黑叔叔
    • 红叔叔

B树和B+树

B树及其基本操作

• 定义(5)
• 重要结论
  • 包含$n$个关键字的B树，必有$n+1$个叶子结点（终端结点）
  • 包含$n$个关键字的$m$阶B树，树高$h$满足
    • $\log_m(n+1)\leqslant h\leqslant\log_{ceil(m/2)}[(n+1)/2]+1$
• 查找
• 插入
• 删除
  • 非终端结点->转化为终端结点的删除操作
  • 终端结点
    • 够删
    • 兄弟够借
    • 兄弟不够借

B+树的基本概念

• 关键字和子树1:1
• 叶结点包含全部关键字
• 非叶结点只是索引
• 两种查找方式
  • 顺序
  • 多路