算法

数据结构复习

红黑树：红色节点不能连续两个，从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点，根和叶子（null）是黑的

AVL：AVL树中任何节点的两个子树的高度最大差别为1

快排：worst case是n^2，优化变为nlogn的最差：

哈希表的separate chaining（分离链接法）方法：直接把冲突的放到一个链表里面

skiplist：跳表，一个英文的说明
，https://segmentfault.com/a/1190000018452079， https://blog.csdn.net/weixin_41462047/article/details/81253106 找关键节点，先在关键节点这里搜索

小顶堆：堆实际上是一棵完全二叉树

  • 复杂度：创建一个堆是O(n)的，建堆的时候你看看是不是多次调用了调堆的函数呢，那肯定就不只是logN了，如果从底部最后的父节点开始建堆，那么我们可以大概算一下：假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次，而最后一层父节点共有2^(H-1)个,倒数第二层公有2^(H-2),顶点只有1(2^0)个，所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + … + (H-1) * 2^1 + H * 2^0 将H代入后s= 2N - 2 - log2(N)，近似的时间复杂度就是O(N)。（https://zhidao.baidu.com/question/566218328045983884.html）

最小生成树：https://blog.csdn.net/a2392008643/article/details/81781766

  • 加点的方法：Prim
  • 加边的方法：Kruskal

最短路径：Dijkstra：https://blog.csdn.net/heroacool/article/details/51014824 这个里面有一些错误，但大致是对的

最大流最小割：https://www.bilibili.com/video/BV1hW411W7Tb ，本质上是在找一条能过去的路