1 树
1.1 概念
节点
- 节点 ：每一个都称为节点
- 根节点：根上的节点（第一个开始节点）
- 叶子节点：没有分支的都称为叶子节点
树的高度、深度、层
- 高度 由下至上 0，1，2...
- 深度 由上至下 0，1，2...
- 层 由上至下 1，2，3...
特点
- 每个节点有零个或多个子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
1.2 二叉树
1.2.1 概念
二叉树的任何一个节点的子节点数量不超过2，子节点分左节点和右节点 不能随意颠倒。
- 普通二叉树：每个节点最多有两个孩子节点
- 满二叉树：除了叶子节点每个节点都有左右两个孩子节点，所有叶子节点在同一层
- 完全二叉树：从树的根节点，从上到下，从左到右一次添满节点形成的二叉树是完全二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
二叉树的遍历：
- 前序遍历：根节点->左子树->右子树
- 中序遍历：左子树->根节点->右子树
- 后序遍历：左子树->右子树->根节点
1.2.2 二叉堆
什么是堆呢？它是满足以下要求的二叉树
- 完全二叉树
- 每个节点>= or <= 孩子节点（大顶堆，小顶堆）
我们常说的堆排序就是借助堆顶元素的特点，衍生出来的一种排序算法
访问的时间复杂度（×）
搜索的时间复杂度（O（1）只关注堆顶元素）
插入的时间复杂度（O（logn））
删除的时间复杂度（O（logn）删除一般也是删除堆顶元素）
堆化操作（将一组树转化为一个堆）时间复杂度为（O（N））
Java中可以使用PriorityQueue<>创建堆。
1.2.3 二叉查找树
二叉查找树，也称为二叉搜索树、有序二叉树或二叉排序树，就是让二叉树的数据结构具备二分查找的特点。
特点：
- 任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
查找、插入的时间复杂度较低为 O ( log n )
1.2.4 平衡二叉树（AVL树）
平衡二叉树是为了优化二叉查找树，如果二叉查找树的两个子树数据相差过大，就不能很好的实现二分查找，甚至随着数据的不断加入，二叉查找树会退化变成一个单链表，或者近似的单链表。
平衡二叉树借助自旋的方式，当插入数据使两棵子树的高度差大于1，就会触发自旋
特点：
- 任何节点的两棵子树的高度差不大于1的二叉树。
1.2.5 红黑树
红黑树相比大家都如雷贯耳，每当我们提及Java中的HashMap都会说它的底层实现是数组+链表+红黑树，这就是一种典型的复合数据结构，在下一篇文章会详细讲复合数据结构都有哪些。
红黑树是为了优化平衡二叉查找树，我们都知道平衡二叉树，在高度差大于1就会立即自旋，自旋对程序性能是有一定影响的，频繁的自旋会极大的降低程序的性能，红黑树就是抓住这一特点进行了优化，它也是一种自平衡二叉树，但是不会像AVL树那样频繁自旋。
之前专门写过一篇文章讲的红黑树，感兴趣的可以看一下JDK底层应用最多的 红黑树
特点：
- 每个节点不是红色就是黑色
- 不可能有连在一起的红色节点
- 根节点都是黑色
- 每个红色节点的两个子节点都是黑色的，叶子节点都是黑色的
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
1.2.6 哈夫曼树
哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。
基于哈弗曼树的特点，它可以用于最佳判定，哈夫曼编码（压缩）等场景
概念：
- 路径：在一棵树中，一个节点到另一个节点之间的通路，称为路径。
- 路径长度：在一条路径中，每经过一个节点，路径长度都要加 1 。例如在一棵树中，规定根节点所在层数为1层，那么从根节点到第 i 层节点的路径长度为 i - 1 。
- 节点的权：给每一个节点赋予一个新的数值，被称为这个节点的权。
- 节点的带权路径长度：指的是从根节点到该节点之间的路径长度与该节点的权的乘积。
举一个哈夫曼编码的应用
假设存在一段字符文本，AAABBCCAA... 我们可以先统计文本中文字出现的频率，得到如下频率表（字符：出现次数）
频率表 A：80, B:46, C:23 D:69 E:18 F:6 G:3
我们就可以得到如下哈夫曼树
将出现次数少的放在下边，将出现频率高的放在上边，然后左边路径设为0，右边为1，这样就可得到一张哈夫曼编码表。
A：11, B:01, C:000 D:10 E:0011 F:00101 G:00100
我们就可以用这种二进制编码表示字符，从而达到加密压缩的目的
1.3 非二叉树
1.3.1 B-树
B-树即B树，他也是一种多路自平衡查找树。
B树出现是为了实现高效 I/O的平衡二叉查找树。平衡二叉树的查找效率是非常高的，但是当数据量非常大，树的深度就会很大，这样就会造成磁盘I/O读写过于频繁，从而导致查询效率低下，并且数据量过大会导致内存空间不够容纳平衡二叉树所有节点的情况。B树是解决这个问题的很好的结构。
小知识
为啥说树的深度越大，磁盘IO会越平凡呢?
因为我们无法控制树的不同节点存储在相同的磁盘块中，访问不同的磁盘块就会加剧IO次数，所以我们通过降低树的深度，使其在查找数据时访问更少的磁盘块，这样就可以减少IO次数。
特点：
- 每个节点最多只有m个子节点。
- 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。
- 如果根不是叶节点，则根至少有两个子节点。
- 具有k个子节点的非叶节点包含k -1个键。
- 所有叶子都出现在同一水平（平衡）。
1.3.2 B+树
B+树又是一个被大家熟知的数据结构，MySQL中InnoDB索引的数据结构一般都是采用B+树的，我们都知道对数据库中的数据添加索引可以极大的提高读取数据的速度，B+树就是对B树的一种升级，使数据全部存储在叶子节点上，并且通过指针连接形成链表，这样可以极大的减小树的深度，还可以更好的范围查询。
MySQL中采用内存页的存储方式，一个内存页是16k，而一个节点是占一个内存页，所以数据全部存在叶子节点上可以，让中间层少存储数据，从而可以存储更多的指针，降低树的深度。
B+树对B树升级的点有：
- 非叶子节点存储key，叶子节点存储key和数据
- 叶子节点两两指针相互连接（叶子节点构成双向循环链表）便于排序，顺序查找
1.3.3 前缀树（Trie树）
前缀树又被称为前缀树、字典树。
前缀树典型应用是用于快速检索（最长前缀匹配），统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计，搜索提示等场景。
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
- 每个节点的所有子节点包含的字符都不相同
由下图可以清晰的看到前缀树的特点，这样不但能极大的节约内存，也能便于搜索。
2 图（Graph）
图是由顶点（Vertex）和边（Edge）构成
图分为有向图和无向图，还有带权图
邻接关系
- 无向图
邻接顶点是指图结构中一条边的两个顶点。
有向图
- 入边邻接顶点：连接该顶点的边中的起始顶点。
- 出边邻接顶点：连接该顶点的边中的结束顶点。
往往我们在表示复杂的地图，铁道，公交路线，人物之间的复杂关系网等都可以使用图结构来表示。
图是相对复杂的数据结构，一般我们日常使用会很少，由图衍生出多种存储结构，如：邻接矩阵 、邻接表、十字链表、邻接多重表等等。
图的遍历是我们需要关注的。
遍历：
- 深度优先搜索算法遍历（栈思想）
- 广度优先搜索算法遍历（队列思想）
