复习基本数据结构树，不涉及到具体的代码实现，主要是每个树的特点和原理弄清楚。

红黑树

红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

• 性质1：每个节点要么是黑色，要么是红色。
• 性质2：根节点是黑色。
• 性质3：每个叶子节点（NIL）是黑色。
• 性质4：每个红色结点的两个子结点一定都是黑色。
• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

红黑树并不是一个完美平衡二叉查找树，任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异。正由于红黑树总保持黑色完美平衡，所以它的查找最坏时间复杂度为O(2lgN)，也即整颗树刚好红黑相隔的时候。能有这么好的查找效率得益于红黑树自平衡的特性，而这背后的付出，红黑树的插入操作功不可没～

AVL树

AVL树本质上还是一棵二叉搜索树，它的特点是：

1.本身首先是一棵二叉搜索树。

2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

右-右型，需要进行左旋。左-左型，需要右旋调整。

右-左型的，我们需要进行一次右旋转换成右-右型再左旋。

左-右型的，我们需要进行一次左旋转换成左-左型再右旋。

红黑树与AVL的对比

B树

B树的特征：

• 根节点至少有两个子节点
• 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 ≤ k ≤ m （m为树的阶）
• 每个叶子节点都包含k-1个元素，其中 m/2 ≤ k ≤ m （m为树的阶）
• 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分（一个结点有k个孩子时，必有k-1个元素才能将子树中所有元素划分为k个子集）

多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

在B树的查找过程为：

1. 在B树中查找结点
2. 在结点中查找关键字。

由于B树通常存储在磁盘上， 则前一查找操作是在磁盘上进行的， 而后一查找操作是在内存中进行的，即在磁盘上找到指针p 所指结点后， 先将结点中的信息读入内存， 然后再利用顺序查找或折半查找查询等于K 的关键字。显然,在磁盘上进行一次查找比在内存中进行一次查找的时间消耗多得多. 因此,在磁盘上进行查找的次数、即待查找关键字所在结点在B树上的层次树，是决定B树查找效率的首要因素，对于有n个关键字的m阶B树，从根结点到关键字所在结点的路径上路过的结点数不超过： log底m/2对数((n+1)/2)+1

B+树

B+树是B树的变体，也是一种多路搜索树：

1. 其定义基本与B树同，除了：
2. 非叶子结点的子树指针与关键字个数相同；
3. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B树是开区间）；
4. 为所有叶子结点增加一个链指针；
5. 所有关键字都在叶子结点出现；

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2. 不可能在非叶子结点命中；
3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4. 更适合文件索引系统；

B+树的优势：

• 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
• B+树的叶子节点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

总结：我们知道二叉查找树的时间复杂度是Ｏ(logN)，效率已经足够高。为什么出现B树和B+树呢？当大量数据存储在磁盘上，进行查询操作时，需要先将数据加载到内存中（磁盘IO操作），而数据并不能一次性全部加载到内存中，只能逐一加载每个磁盘页（对应树的一个节点），并且磁盘IO操作很慢，平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。为了减少磁盘IO的次数，就需要降低树的深度，那么就引出了B树和B+树：每个节点存储多个元素，采用多叉树结构。这样就提高了效率，比如数据库索引，就是存储在磁盘上，采用的就是B+树的数据结构。