{总结帖}--认识数据结构里的各种树
1. 树
树是一种非常常用的数据结构，树与线性表，栈，队列等线性结构不同，树是一种非线性结构
树的定义
计算机世界里的树，是从自然界中实际的树抽象而来的，它指的是N个有父子关系的节点的有限集合。对于这个有限的节点集合而言，它满足如下条件：
- 当N=0时，该节点集合为空，这课树也被称为空树
- 在任意的非空树中，有且仅有一个根(root)节点
- 当N>1时，除根节点以外的其余节点可分为M个互为相交的有限集合T1,T2,...,Tm，其中的每个集合本身又是一棵树，并称其为根的子树（subtree）。
从上面定义可以发现树的递归特性：一棵树由根和若干棵子树组成，而每棵子树又由若干棵更小的子树组成。
树
2. 二叉树
二叉树指的是每个节点最多只能有两个子树的有序树。
通常左边的子树被称作“左子树”(left subtree)，右边的子树被称为“右子树”(right subtree).由此可见，二叉树依然是树，它是一种特殊的树。
二叉树的每个节点最多只有来两颗树(不存在度大于2的节点)，二叉树的子树有左，右之分，次序不能颠倒。
树和二叉树的两个重要区别如下：
- 树中节点的最大度数没有限制，而二叉树节点的最大度数为2，也就是说，二叉树是节点的最大度数为2的树。
- 无序树的节点无左右之分，而二叉树的节点有左，右之分，也就是说，二叉树是有序树。
满二叉树、完全二叉树
3. 二叉搜索树（二叉排序树，二叉查找树）
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
二叉查找树
4. 平衡二叉搜索树（AVL树）
平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：
- 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
5. B- 树
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。敲黑板，绝不能称之为B减树，会被笑话的。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
- 1.根结点至少有两个子女；
- 2、每个非根节点包含 k-1个元素和k个孩子，其中m/2 <= k <= m；
- 4、所有的叶子结点都位于同一层。
- 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划
B树，注意到卫星数据在所有节点元素中都带
B-树的应用：
- 文件系统
- 部分数据库如 MengoDB 的索引
6. B+ 树
B+树是 B树的变体，有着比B树更高的查询性能
一个m阶的B+树具有如下几个特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B+树
在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
B+树的结构设计带来的好处：
非叶子节点不包含卫星数据，使得B+树的身形更加矮胖，查询IO次数更少；
B+树上的查询都是遍历到根节点，性能较B-树要稳定；
范围查询比B-树方便，找到下界后沿链表往后遍历即可。
7. 红黑树
红黑树是平衡二叉查找树的一种实现，但是并没有追求绝对的平衡。
红黑树在符合二叉查找树的特征之外，还具有以下的附加特征：
- 1.节点是红色或黑色。
- 2.根节点是黑色。
- 3.每个叶子节点都是黑色的空节点（NIL节点）。
- 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树
规则打破后的调整：变色和旋转
参考链接：
程序员小灰-漫画：什么是红黑树？
一步一图一代码，一定要让你真正彻底明白红黑树（平衡二叉树）
红黑树的实际应用： JDK 集合类中的TreeMap TreeSet,HashMap(Java 8)
