1.树

定义：树是由节点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。

树的定义非常简单，所有定节点和边组成的非环结构都可以成为树。

2.二叉树

定义：度为2的树。

2.1 完美二叉树（满二叉树）

除了叶子节点外，每个节点都有两个孩子节点。且每一层都被填满。

2.2 完全二叉树

除了最后一层外，每一层都是满的。并且最后一层左右节点都向左靠齐。

2.3 完满二叉树

除了叶子节点外，每个节点都有两个孩子节点。每一层不一定是满的。

2.4 二叉查找树

所有左孩子都小于根节点
所有右孩子都大于根节点
没有重复的节点

2.5 AVL树（自平衡二叉查找树）

左右孩子高度差最多不超过1的二叉查找树

2.6 红黑树

一种自平衡二叉查找树, 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保从根到叶子节点的最长路径不会是最短路径的两倍，用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决。

使用场景：

红黑树多用于搜索,插入,删除操作多的情况下

1.广泛用在C++的STL中。map和set都是用红黑树实现的。
2.著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。
3.epoll在内核中的实现，用红黑树管理事件块
4.nginx中，用红黑树管理timer等

红黑树的查询性能略微逊色于AVL树，因为比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上完爆AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多。

红黑树特性：

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

3.多叉树

每个节点的孩子节点不止2个，可能有多个

4.平衡树（B树)

也叫多叉自平衡树。M阶平衡树有如下特点：

1.定义任意非叶子结点最多只有M个儿子；且M>2
2.根结点的儿子数为[2, M]
3.除根结点以外的非叶子结点的儿子数为[M/2, M]
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]
7.非叶子结点的指针：P[1], P[2], …, P[M]，其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树
8.所有叶子结点位于同一层

如M=3,表示每个节点最多有3个孩子，2个关键字

4.2 平衡多叉树

4.2.1 B+树

B+树是B树的一种变体，特征如下：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的
2.不可能在非叶子结点命中
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
4.更适合文件索引系统
原因：增删文件（节点）时，效率更高，因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率

B+树最大的特点就是所有数据都在叶子节点，非叶子节点相当于是叶子节点的一个索引，并且所有叶子节点都串起来了，因此只需要找到某一个叶子节点，即可按顺序找到其他叶子节点，这样连续的数据方便快速定位。

3阶B+树结构如下：

使用场景：

文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：
Windows：HPFS 文件系统
Mac：HFS，HFS+ 文件系统
Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统
数据库：ORACLE，MYSQL，SQLSERVER 等中

B树：有序数组+平衡多叉树
B+树：有序数组+平衡多叉树+链表

B+树的优点：