4、堆

5、哈夫曼树HT/最优二叉树

二、多路查找树：多叉树——二叉到多叉的思考

1、多叉树

一个节点存一个值，则有2个孩子：W

一个节点存两个值，则有3个孩子：MO

一个节点存三个值，则有4个孩子：MO

1、多叉树的查找与插入

2、B树及其变种——分裂节点、合并节点

1、B树的定义——m阶B树需要满足的条件

(1)、每个结点至多有m个孩子；

(2)、除根结点外，其他结点至少有m/2个孩子；

(3)、根结点至少有2个孩子；

(4)、所有叶结点在同一层；

(5)、有α个孩子的非叶结点有α-1个关键字；结点内部，关键字递增排列。