链表、树和图专项练习

链表和数组的区别：

链表是链式存储结构，数组是顺序存储结构；

链表通过指针连接元素，而数组则是把所有元素按顺序进行存储；

链表插入和删除元素不需要移动元素，数组删除和增加元素需要移动元素。

需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构是静态链表。

B树支持随机搜索，B+树支持随机和顺序搜索。

在哈夫曼树（二叉）中，结点的度可能为0或2。、

红黑树的插入复杂度为O(log(n))。

完全二叉树满足，深度h：。

TRIE树，又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希表高。

计算树叶子结点的等量关系为：边数相等。例如：e=n-1=n0+n1+n2+n3+n4+n5-1，e=n0*0+n1*1+n2*2+n3*3+n4*4+n5*5。

具有n个结点的二叉树的形态个数计算公式：。

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；B-树：多路搜索树，每个结点存储向上取整M/2-1到M-1个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整棵树中出现，且只出现一次，非叶子结点可以命中；B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。

不稳定排序：快速排序、希尔排序、选择排序、堆排序。

LTag=0：lchild域指示结点的左孩子；LTag=1：lchild域指示结点的前驱；

采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的先序遍历；

采用邻接表存储的图按广度优先搜索方法进行遍历的算法类似于二叉树的层序遍历。

图的广度优先（队列），深度优先（栈）。

求图的最小生成树算法：prim算法权值可正可负（稠密图）、Kruskal算法（稀疏图）；求图最短路径算法：Dijkstra算法不能有负的权值（单源）、DFS/BFS（单源）、Floyed算法（多源）、Bellman-Ford算法（单源、负权）。

m阶B-树：一种平衡的多路查找树；树中每个结点至多有m棵子树；若根节点不是叶子结点，则至少有两颗子树。

从二叉排序树中查找一个元素时，其时间复杂度一般为O（log2n）

平衡二叉树本质是二叉排序树。

拓扑排序是结点的逻辑排序。

路径最长叫关键路径，关键路径上面的活动叫做关键活动。

图中任意两点度的和大于或等于顶点总数，那么这个图一定是哈密顿图。

对于用邻接表表示图（包含n个定点e条边）时，拓扑排序算法时间复杂度为O(n+e)。

求最短路径的 FLOYD 算法的时间复杂度为O(n^3),空间复杂度O(n^2)。

一个无向图的连通分量是其极大地连通子图。

无向图特有：邻接多重表；有向图特有：十字链表，边集数组；二者共有：邻接表，邻接矩阵。

检测有向图中是否存在环的算法：深度优先遍历，拓扑排序。