浅谈【树】（红黑树、AVL树、B树、B+树）浅谈【树】：红黑树、AVL树、

一、红黑树（漫画理解）（PS:标题超链接着漫画版的解读，看漫画，学数据结构，轻松get知识点~...）
1.1 二叉查找树

某节点的左子树节点值仅包含小于该节点值
【浅谈【树】（红黑树、AVL树、B树、B+树）】某节点的右子树节点值仅包含大于该节点值
左右子树每个也必须是二叉查找树

1.2 红黑树一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
1. 红黑树限制规则
Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

1.节点是红色或黑色。
2.根节点是黑色。(黑土地孕育黑树根)
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2. 调整规则
先试变色再试旋转（左旋或右旋）
3. 优点
正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间
4. 用途
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是 O(lgn)，效率非常之高。
例如，Java 集合中的 TreeSet 和 TreeMap，C++ STL 中的 set、map，以及 Linux 虚拟内存的管理，都是通过红黑树去实现的。
二、树的深度优先遍历和广度优先遍历（漫画解读）
【简介】深度优先遍历简称DFS(Depth First Search)，广度优先遍历简称BFS(Breadth First Search)，它们是遍历图当中所有顶点的两种方式。
2.1 深度优先遍历

深度优先遍历，相当于你在游乐场游玩景点时，一头扎到底的玩法。我们选择一条支路，尽可能不断地深入，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入。
像这样先深入探索，走到头再回退寻找其他出路的遍历方式，就叫做深度优先遍历(DFS)。
其实二叉树的前序、中序、后序遍历，本质上可以认为是深度优先遍历。
算法实现的关键在于回溯，利用栈先进后出的特性或递归来实现（递归本质上是基于方法调用栈来实现）。
回溯：顾名思义，就是自后向前，追溯曾经走过的路径。

2.2 广度优先遍历

广度优先遍历，相当于在游乐场首先把起点相邻的几个景点玩遍，然后去玩距离起点稍远一些（隔一层）的景点，然后再去玩距离起点更远一些（隔两层）的景点......
像这样一层一层由内而外的遍历方式，就叫做广度优先遍历(BFS)。
其实二叉树的层序遍历本质上也可以认为是广度优先遍历
算法实现的关键在于重放，可以利用队列先进先出特性来实现
重放：与回溯完全相反，把遍历过的顶点按照之前的遍历顺序重新回顾，就叫做重放

三、B-树和 B+树
【简单介绍】：动态查找树主要包括：二叉查找树，平衡二叉树，红黑树，B树，B+树，查找的时间复杂度就为O(log2N)，通过对数就可以发现降低树的深度就会提高查找效率。因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。在大数据存储过程，大量的数据会存储到外存磁盘，外存磁盘中读取与写入某数据的时候，首先定位到磁盘中的某一块，这就有个问题：如何才能有效的查找磁盘中的数据呢，这就需要一种高效的外存数据结构，B树就是为了提高磁盘或外部存储设备查找效率而产生的一种多路平衡查找树。
3.1 B树
【简介】：B树：（Balance Tree）即为平衡树的意思，为了存储设备或者磁盘而设计的一种多路平衡查找树，每个节点拥有更多的子节点，子节点的个数一般称为阶。
【备注一条】：在数据库索引中，没有B-树(B减树)的说法，这就是B树！！！
用途：主要用于文件系统以及部分数据库索引（比如：MongoDB菲关系型数据库）
B树特性一棵m阶的B树，特性如下：