《漫画算法2：小灰的算法进阶》第二章 树的进阶
什么是二叉查找树
二叉查找树(Binary Search Tree):
1. 如果左子树不为空，则左子树上所有节点的值均小于根节点的值。
2. 如果右子树不为空，则右子树上所有节点的值均大于根节点的值。
3. 左、右子树也都是二叉查找树。
二叉查找树会维持节点的有序性，也称作二叉排序树(Binary Sort Tree)，无论进行多少次插入、删除操作，都始终保持有序
二叉查找树的插入和删除
节点11以下的节点关系无须变动
二叉查找树的缺陷
虽然这样一棵树也符合二叉查找树的特性，但是查找节点的时间复杂度退化成了O(n)
什么是平衡二叉树
平衡二叉树(AVL树)，它在每次插入、删除节点之后，可以进行“自平衡”，也就是通过一系列调整重新达到平衡状态。
对于AVL树的每一个节点，平衡因子是它的左子树高度和右子树高度的差值。
只有当二叉树所有节点的平衡因子都是-1, 0, 1这三个值的时候，这棵二叉树才是一棵合格的AVL树。
AVL树提供了两种特殊的操作：左旋和右旋来恢复AVL树的平衡
什么是红黑树
红黑树复杂一些，通过红色和黑色两种节点，以及若干规则来判断平衡；
红黑树的存在目的也是为了维护二叉查找树的平衡
红黑树的规则如下：
1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点都是黑色的空节点（NIL节点）。
4. 每个红色节点的子节点都是黑色（即不存在两个连续的红色节点）。
5. 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树从根到叶子的最长路径不会超过最短路径的2倍
红黑树的调整方法有两种：
调整的方法有两种：变色和旋转
在需要频繁查找时，选用AVL树更合适，在需要频繁插入、删除时，选用红黑树
什么是B树和B+树
B树和B+树非常适合做数据库和文件系统的索引；
B树：
B树单一节点拥有的最多子节点数量，称为B树的“阶”；
一个m阶的B树，具有如下几个特征：
1. 根节点至少有两个子节点。
2. 每个中间节点都包含k-1个元素（也被称为关键字）和k个孩子，其中m/2 <= k<=m。
3. 每一个叶子节点都包含k-1个元素，其中m/2 <= k<= m。
4. 所有的叶子节点都位于同一层。
5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
B树虽然可以改善数据库查询的性能，但是却存在一个不足之处：不方便进行范围查询。
一个m阶的B+树具有如下几个特征：
1. 有k个子树的中间节点包含k个元素（B树中是k-1个元素），每个元素不保存数
据，所有数据都保存在叶子节点。
2. 所有的叶子节点包含了全部元素，依照元素的大小升序排列，叶子节点之间用双向
指针相连接。
3. 所有中间节点的元素都同时存在于子节点，在子节点元素中是最大（或最小）元
素。
并且每一个叶子节点都带有指向相邻叶子节点的指针，形成了一个双向有序链表
B+树用于范围查询十分方便。
小结
二叉查找树
可以提高节点查找的效率，并维持节点的有序性。理想状态下，二叉查找树查找的时间复杂度是O(logn)，但如果节点分布失衡，查找的时间复杂度有可能退化到O(n)
平衡二叉树
也叫作AVL树，是一种特殊的二叉查找树，可以自动调节平衡。
AVL树维持着严格的平衡，任意节点的两棵子树的高度差都不超过1。这样的优点是保证了查询的效率，缺点是维持平衡的成本比较高，适合查询较多的场景。
红黑树
是另一种可以自动调整平衡的二叉查找树。
红黑树维持着相对的平衡，要求任何一条路径的长度不超过其他路径长度的2倍。
这样的优点是降低了维持平衡的成本，缺点是查询效率略低，适合频繁插入、删除的场景。
B树
解决了从磁盘海量数据中查询的需求，有效减少了磁盘I/O的频次。
B+树
是B树的升级，叶子节点包括全量数据，并使用双向指针连接相邻节点，为范围查询提供了便利。
