B树
- n节点的B树高度为O(lgn)
- 每个节点:n[x]当前节点内关键字数，
- n[x]个关键字本身，非降序排列；
- leaf[x],x为叶子则为true；
- n[x]+1个子女指针，叶节点指针域为空
- 关键字对子树进行划分分割
- 叶节点具有相同深度，即树高
- 每个节点包含关键字字数有上界，即B树的最小度数t
- 非根节点至少t-1个节点，t个子女
- 每个节点至多2t-1关键字，内街店至多2t个节点
- n个关键字，高度为h，最小度数为t》=2的B树有：h <= lgt((n+1)/2)
- B树操作
- 二项树
- 二项树B0只包含一个节点，二项树Bk由2两颗二项树Bk-1连接而成，其中一棵树根是另一棵树根的最左孩子
- 二项树性质
- 共有2^k个节点
- 树高k
- 深度i处有Cki个节点
- 根的度数为k，根的子女从左到右编号k-1到0，子女i是子树Bi的根
- n个节点的二项树，任意节点的最大度数lgn
- 二项堆
- 堆中每个二项树都遵循最小堆性质
- 对任意非负整数k，堆中之多有一颗二项树度数为k
- 创建二项堆：根表头置空
- 寻找最小关键字：在根表中寻找最小值
- 根表度数严格递增
- 合并两个二项堆
- 插入：直接插入根表中
- 抽取最小关键字：将最小关键字子树构建成一个新的二项堆，与原二项堆合并
- 减小关键字：递归向上调整至根表
- 删除关键字：将关键字降值为最小，然后抽取最小值，复杂度O(lgn)
斐波那契堆
- 结构：最小堆有序树构成，不一定是二项树
- 根表由双链表构成，且无序；min[h]指向根表中最小值
- 可合并堆操作
- 合并策略：
- 按秩合并（节点少的树根合并到节点多大的树根） - 路径压缩（查找路径上的每个节点都指向根节点）
