二叉搜索树

       1.所有非叶子结点至多拥有两个儿子（Left和Right）；

       2.所有结点存储一个关键字；

       3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树。

       搜索：从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字。

B-树

1. M阶B-树是一种多路平衡搜索树（并不是二叉的）：

2. 根结点的儿子数为[2, M]；

3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；

4. 所有叶结点都为空且位于同一层；

5. 若一个非叶结点有n个孩子，那么它有n-1个关键字，结构见下：

n-1

P0

K1

P1

K2

P2

...

Kn-1

Pn-1

表一：非叶结点存放的数据

 

K[1], K[2], …, K[n-1]为非叶子结点的关键字且K[i] < K[i+1]；

P[i]为指向孩子节点的指针。其中P[i-1]所指结点的关键字全小于K[i],P[i]所指结点的关键字全大于K[i]。

B-树的搜索：从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。

B-树的插入：找到待插入结点并插入。若所在结点关键字个数等于孩子数，进行分裂。若分裂后导致父节点关键字个数等于孩子数，再进行父节点的分裂。

B-树的删除：若删除后导致所在结点关键字个数等于M/2(向上取整)-2，需要对节点进行合并。

B-树举例：

 

B+树

B+树也是多路平衡查找树，与B-树的区别在于：

1.含有n个关键字的结点有n个孩子。

2.B+树中所有非叶结点仅起到索引作用，不含待查元素的存储地址。

3.叶结点包含了全部元素的关键字和存储地址。

4.非叶结点的存储结构见下：

n

k1

p1

k2

p2

...

kn

pn

Ki为关键字，pi指向的孩子结点，其关键字的最大值为Ki。

举例：

 

红黑树

红黑树是一种二叉查找树。因结点带有颜色属性而得名。

在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。

性质：

1.每个节点都有颜色属性，非红即黑。

2.根节点和每个叶节点（NIL节点，空节点）是黑色的。

3.每个红色节点的两个孩子节点都是黑色。

4.对于任意一节点，它到其所有后代叶子节点的简单路径，均包含相同数目的黑色节点。

4.左孩子<根结点<右孩子。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

举例：

 

AVL 树

自平衡二叉查找树。

红黑树与AVL的比较

AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。