各种树

一、二叉树（B树）

每个节点只存储一个关键字，等于则命中，小于走左节点，大于走右节点。

二、B-树（多路搜索树）

每个节点存储M/2到M个关键字，非叶子节点存储指向关键字范围的子节点；所有关键字在整颗树中出现，且只出现一次，不是叶子节点也可以命中。

三、B+树

在B-树基础上，为叶子节点增加链表指针，所有关键字都在叶子节点中出现，非叶子节点作为叶子节点的索引；B+树总是到叶子节点才命中。

四、B*树

在B+树基础上，为非叶子节点也增加链表指针，将节点的最低利用率从1/2提高到2/3。

五、平衡二叉树

平衡二叉树定义：1. 可以是空树。2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1。
概念：平衡二叉查找树简称平衡二叉树，也被叫做AVL树，是1962年由两位俄罗斯的数学家G.M.Adel'son-Vel,sky和E.M.Landis提出 的.引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入 一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度。
调整方式：根据破坏平衡性的加入点，将插入操作分为了四种，分别是：LL、LR、RR、RL。

六、红黑树

红黑树定义：
1.每个节点要么是“红色”，要么是“黑色”。
2.根结点永远是“黑色”的 。
3.红节点的孩子节点不能是红节点。
4.从根到前端节点的任意一条路径上的黑节点数目一样多。
说明：这两条定义确保该树的高度为logN，所以是平衡树。
概念：红黑树是每个节点都带颜色的树，节点颜色为红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。