40
二叉搜索、 B- 、B+、 红黑 、AVL 树
二叉搜索树
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。
最后更新：2017-04-03 12:55:58