其中B树部分参考的是这篇文章： 从B树、B 树、B*树谈到R 树 里面讲得特别详细！
- 二叉树
- 满二叉树 国内：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。 国外：:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.（二叉树中节点的度只能是0或2）
- 完全二叉树 设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。
- 二叉排序树
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
左节点小于父节点的值，右节点大于父节点。
- 自平衡二叉搜索树
- AVL树 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
- 伸展树
- 红黑树
- 自平衡二叉搜索树
- 哈弗曼树
- 线索二叉树
- B树（B-树） m阶B树 (m >= 2)： (1) 每个节点最多m个孩子； (2) 除根和叶，其他至少 ceil(m/2) 个孩子； (3) 若根节点不是叶，则至少2个孩子； (5) 包含k个孩子的非叶子节点有k-1个关键字，每个节点中关键字按升序排序 (4) 所有叶子都在同一层； 总结：有孩子和键值的上下限；叶子在同一层；键值升序； 一棵含有N个总关键字数的m阶的B树的最大高度是多少?<=log┌m/2┐((N 1)/2 ) 1
插入：从最后一层插入，太满则分裂（从中切开），中间码加入到父节点。重复。一直到根节点，则分裂，新建一个根节点。 删除： (1) 找到元素，删掉，上移其左/右孩子的相近元素； (2) 若一节点元素太少，则看其兄弟是否丰满，丰满则向其父节点借，让其兄弟去填补父节点（还债）； (3) 如果兄弟都刚脱贫，则与相邻兄弟合并（合并也要带上父元素）。
- B 树 有序数组链表 平衡多叉树； 叶子节点多了链；键值没有卫星数据的索引。
所有的非终端结点可以看成是索引部分。 叶子结点本身依关键字的大小自小而大的顺序链接。 (1) 更加高效的单元素查找。磁盘读写代价更低。 (2) 查询效率更加稳定。 (3) 范围查找性能更优。
- B*树 一棵丰满的B 树。 最少孩子2/3m；兄弟间有了链。
B 树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B 树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。 B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。 所以，B*树分配新结点的概率比B 树要低，空间使用率更高。
- 字典树 应用：单词判断拼写正误；单词前缀次数查找。
未完待续
