6. 图表（Graphs）
图是表示一对两个集合的非线性数据结构：G={V, E}，其中 V 是顶点（节点）的集合，而 E 是边（箭头）的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。
图有两种主要类型：有向图和无向图。在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。
它们是做什么用的？
图是各种类型网络的基础：社交网络（如 weixin、csdn、weibo），甚至是城市街道网络。社交媒体平台的每个用户都是一个包含他/她的所有个人数据的结构——它代表网络的一个节点。weixin 上的好友关系是无向图中的边（因为它是互惠的），而在 CSDN 或 weibo上，帐户与其关注者/关注帐户之间的关系是有向图中的箭头（非互惠）。
特性
图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：
无向图中节点的度数是它的关联边数；
有向图中节点的内部/外部度数是指向/来自该节点的箭头的数量；
从节点 x 到节点 y 的链是相邻边的连续，x 是它的左端，y 是它的右边；
一个循环是一个链，其中 x=y；图可以是循环/非循环的；如果 V 的任意两个节点之间存在链，则图是连通的；
可以使用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 遍历和处理图，两者都在 O(|V|+|E|) 中完成，其中 |S| 是集合S 的基数；查看下面的链接，了解图论中的其他基本信息。
7. 树（Trees）
一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的） . 所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。
根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。
一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。
它们是做什么用的？
我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。
树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。
特性
根没有父级；
叶子没有孩子；
根和节点 x 之间的链的长度表示 x 所在的级别；
一棵树的高度是它的最高层（在我们的例子中是 3）；
最常用的遍历树的方法是 O(|V|+|E|) 中的 DFS，但我们也可以使用 BFS；使用 DFS 在任何图中遍历的节点的顺序形成 DFS 树，指示我们访问节点的时间。
8. 二叉树（Binary Trees）和二叉搜索树（Binary Search Trees）
二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。
二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。
它们是做什么用的？
BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。
BST 经常使用，因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。
特性
BST 有三种类型的 DFS 遍历：
先序（根、左、右）；
中序（左、根、右）；
后序（左、右、根）；全部在 O(n) 时间内完成；
中序遍历以升序为我们提供了树中的所有节点；
最左边的节点是 BST 中的最小值，最右边的节点是最大值；
注意 RPN 是 AST 的中序遍历；
BST 具有排序数组的优点，但有对数插入的缺点——它的所有操作都在 O(log n) 时间内完成。
9. AVL树（Adelson-Velsky and Landis Trees ）
所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。
AVL 树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名：Adelson-Velsky 和 Landis。
在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。
在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是 O(log n)。
它们是做什么用的？
AVL 似乎是数据库理论中最好的数据结构。
RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 版本中，HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。
在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。
特性
ANY自平衡BST中ANY操作的摊销时间复杂度为O(log n)；
在最坏的情况下，AVL 的最大高度是 1.44 * log2n（为什么？提示：考虑所有级别都已满的 AVL 的情况，除了最后一个只有一个元素）；
AVLs 在实践中搜索元素是最快的，但是为了自平衡而旋转子树的成本很高；
同时，由于没有旋转，RBT 提供了更快的插入和删除；
展开树不需要存储任何簿记数据。
10.堆（Heaps）
最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]] <= val[x]，具有堆的 xa 节点，其中val[ x]是它的值，par[x] 是它的父级。
还有一个实现相反关系的最大堆。
二叉堆是一棵完整的二叉树（它的所有层都被填充，除了最后一层）。
它们是做什么用的？
正如我们几天前讨论过的，优先队列可以使用二叉堆有效地实现，因为它支持 O(log n) 时间内的 insert()、delete()、extractMax() 和 reduceKey() 操作。这样，堆在图算法中也是必不可少的（因为优先级队列）。
任何时候您需要快速访问最大/最小项目，堆都是最好的选择。
堆也是堆排序算法的基础。
特性
它总是平衡的：无论何时我们在结构中删除/插入一个元素，我们只需要“筛选”/“渗透”它直到它处于正确的位置；
节点k > 1的父节点是[k/2]（其中 [x] 是 x 的整数部分），其子节点是2k和2k+1；
设置优先级队列的替代方案，ordered_map（在 C++ 中）或任何其他可以轻松允许访问最小/最大元素的有序结构；
根优先，因此其访问的时间复杂度为O(1)，插入/删除在O(log n)中完成；创建一个堆是在 O(n) 中完成的；O(n*log n)中的堆排序。
11.字典树（Tries）
trie 是一种高效的信息检索数据结构。也称为前缀树，它是一种搜索树，允许以 O(L) 时间复杂度插入和搜索，其中 L 是键的长度。
如果我们将密钥存储在一个平衡良好的 BST 中，它将需要与 L * log n 成正比的时间，其中 n 是树中的密钥数量。这样，与 BST 相比，trie 是一种更快的数据结构（使用 O(L)），但代价是 trie 存储要求。
它们是做什么用的？
树主要用于存储字符串及其值。它最酷的应用程序之一是在 Google 搜索栏中键入自动完成和自动建议。特里是最好的选择，因为它是最快的选择：如果我们不使用特里，更快的搜索比节省的存储更有价值。
通过在字典中查找单词或在同一文本中查找该单词的其他实例，也可以使用 trie 来完成键入单词的正字法自动更正。
特性
它有一个键值关联；键通常是一个单词或它的前缀，但它可以是任何有序列表；
根有一个空字符串作为键；
节点值与其子节点值之间的长度差为 1；这样，根的子节点将存储长度为 1 的值；作为结论，我们可以说来自第 k 层的节点 x 具有长度k 的值；
正如我们所说，插入/搜索操作的时间复杂度是 O(L)，其中 L 是键的长度，这比 BST 的 O(log n) 快得多，但与哈希表相当；
空间复杂度实际上是一个缺点：O(ALPHABET_SIZE*L*n)。
