1. 树(Tree)的基本概念

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

2. 二叉树

每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

2.1 二叉树的性质

1. 若二叉树的层次从0开始，则在二叉树的第 i 层至多有 $2^i$ 个结点( i >= 0 )

2. 高度为 k 的二叉树最多有 $2^{(k+1)}-1$个结点 ( k >= -1 )(空树的高度为 -1 )

3. 对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则 m=n+1

二叉树又分为：完美二叉树，完全二叉树，完满二叉树

2.1.1 完美二叉树(满二叉树)

2.1.2 完全二叉树

2.1.3 完满二叉树

2.1.4 区别

名称	英文术语	特点
完美二叉树	Perfect Binary Tree	除了叶子节点之外的每一个结点都有两个孩子，每一层（包括最后一层）都被完全填充
完全二叉树	Completed Binary Tree	除了最后一层之外的其它层都被完全填充，并且所有节点都保持向左对齐。（左对齐的意思最底层的节点如果有缺失，只会发生在右边连续的一段，左边连续的一段是满的。）
完满二叉树	Full/Strict Binary Tree	除了叶子节点之外的每一个节点都有两个孩子结点。

2.2 二叉树的遍历方法

1. 中序遍历：即左-根-右遍历，对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的节点i，其必然为叶子，然后遍历i的父节点，再遍历i的兄弟节点。随着递归的逐渐出栈，最终完成遍历

2. 先序遍历：即根-左-右遍历

3. 后序遍历：即左-右-根遍历

3. 二叉树的一些特殊形态

3.1 二叉查找树

二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质：

1. 任意节点左子树不为空,则左子树的值均小于根节点的值

2. 任意节点右子树不为空,则右子树的值均大于于根节点的值

3. 任意节点的左右子树也分别是二叉查找树

4. 没有键值相等的节点

局限性及应用

一个二叉查找树是由 n 个节点随机构成,所以，对于某些情况,二叉查找树会退化成一个有 n 个节点的线性链。如下图:

3.2 AVL树

AVL 树是带有平衡条件的二叉查找树，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足(所有节点的左右子树高度差不超过 1 )。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的。

3.2.1 使用场景：

AVL树适合用于插入删除次数比较少，但查找多的情况。

也在 Windows 进程地址空间管理中得到了使用。

旋转的目的是为了降低树的高度，使其平衡。

3.2.2 AVL树特点

1. AVL树是一棵二叉搜索树

2. AVL树的左右子节点也是 AVL 树

3. AVL树拥有二叉搜索树的所有基本特点

4. 每个节点的左右子节点的高度之差的绝对值最多为1，即平衡因子为范围为 [-1,1]

3.3 红黑树

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

3.3.1 使用场景：

红黑树多用于搜索,插入,删除操作多的情况下 红黑树应用比较广泛：

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. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

作者：意识流丶 链接：https://www.jianshu.com/p/912357993486/
来源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

感谢这位大哥整理学习资料