B树，B+树，B-树以及红黑树等的概念以及原理

学习 Java

文章目录

• B树
• B+树
• B-树

1. B树

B树：即二叉搜索树，它的定义如下：

• 所有非叶子节点至多拥有两个子节点(left,right)
• 所有节点存储一个关键字
• 非叶子节点的左指针指向比他关键字小的子树，右节点则指向比他大的

B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字。
如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销。在实际使用中，通常是在B树的基础上添加平衡算法，编程平衡二叉树。平衡二叉树又叫AVL树，是由作者姓名命名的，平衡二叉树还有一个改进的版本，叫做红黑树。

2. B-树

B-树：一种非二叉多路搜索树，它的定义是：

• 定义任意非叶子结点最多具有M个儿子，M>2；
• 根节点的儿子树[2,M]；
• 除根节点之外的非叶子结点的儿子数为[M/2,M]；
• 每个节点存放至少M/2-1(向上取整)和至多M-1个关键字；
• 非叶子结点的关键字个数等于指向儿子的指针个数减去1
• 非叶子结点的关键字：K[1],K[2]...K[M-1],:且K[i]小于K[i+1]；
• 非叶子结点的指针：P[1],P[2],,,,,P[M],其中P[M]指向关键字大于K[M-1]的子树，其他P[i]指向关键字属于(K[i-1],k[i])的子树；

• 所有叶子节点位于同一层。

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

  

  B-树有着如下的特性：

  1. 关键字集合分布在整颗树中；
  2. 任何一个关键字出现且只出现在一个结点中；
  3. 搜索有可能在非叶子结点结束；
  4. 其搜索性能等价于在关键字全集内做一次二分查找；
  5. 自动层次控制；

  同时，由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：
  

  $$\begin{align} O_{min} &= O[log_2([\frac M2-1])*log_{\frac N2}(\frac N{|\frac M2-1|})]\\ &= O[log_2(\frac M2)]*O[log_{\frac M2}(\frac N{\frac M2})]\\ &=O[log_2(\frac M2)*(log_{\frac M2}N-1)]\\ &=O[log_2N-log_2(\frac M2)]\\ &=O[log_2N]-O[C]\\ &=O[log_2N]\\ \end{align}$$

公式中，M为设定的非叶子节点最多子树的个数，N为关键字总数；所以B-树的性能总是等价于2分查找（与M值无关），也就没有B树平衡的问题；
由于M/2的限制，在插入节点的时候，如果节点已经满了，需要将节点分裂成两个各占M/2的节点；删除节点的时候，需要将两个不足M/2的节点合并

3. B+树

B+树：B-树的变体，同样是一种多路搜索树，定义基本与B-树相同，除了：
- 非叶子结点的子树指针与关键字个数相同而不是多一个
- 非叶子结点子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树，(B-树是开区间）;
- 为所有叶子结点增加了一个链指针;
- 所有关键字都在叶子结点出现.

eg：

4：红黑树，AVL，平衡二叉搜索树

• 红黑树是在AVL的基础上改进的新的平衡二叉搜索树.
• AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；

红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低,所以简单说，搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择RB树。
红黑树上每个结点内含五个域，color，key，left，right，p。如果相应的指针域没有，则设为NIL。
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

5:AVL平衡二叉搜索树:

AVL平衡二叉搜索树定义：

• 平衡二叉树或为空树,或为如下性质的二叉排序树:
• 左右子树深度之差的绝对值不超过1;
• 左右子树仍然为平衡二叉树.

平衡因子BF=左子树深度－右子树深度.
平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。