前言：耗费了五个多小时，算是差不多了 红黑树是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外，还有以下要求： 下图就是一个典型的红黑树： 但实现上我省略了其中的 Nil 结点，一般如下图，大家理解时也可以忽略它们。 优势和用途 我们知道二叉查找树在不停地添加或删除结点后，可能会导致结点情况如下： 这种情况下，二叉查找树的查找效率最坏会降低为 O(n)。 而红黑树由于在插入和删除结点时都会进行变色旋转等操作，在符合红黑树条件的情况下，即使一边子树全是黑色结点，另一边子树全是红黑相间，两子树的高度差也不会超过一半。一棵有 n 个结点的红黑树高度至多为 2log(n+1)，查找效率最坏为 O(log(n))。 所以红黑树常被用于需求查找效率稳定的场景，如 Linux 中内核使用它管理内存区域对象、Java8 中 HashMap 的实现等，所以了解红黑树也很有意义。 下面介绍一下红黑树的等同 2-3-4树。 2-3-4树 2-3-4树是四阶的 B树(Balance Tree)，它的结构有以下限制： 下图是一个典型的 2-3-4树（来自维基百科）： 2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同——红黑树。 红黑树维持平衡的方式 对应红黑树 至于为什么说红黑树是 2-3-4树的一种等同呢，这是因为 2-3-4树的每一个结点都对应红黑树的一种结构，所以每一棵 2-3-4树也都对应一棵红黑树，下图是 2-3-4树不同结点与红黑树子树的对应。 而上文中的 2-3-4树也可以转换成一棵红黑树： 由红黑树的性质5，和 2-3-4树的性质1，为了便于理解红黑树和 2-3-4树的对应关系，我们可以把红黑树从根结点到叶子结点的黑色结点个数定义为高度。 红黑树和 2-3-4树的结点添加和删除都有一个基本规则：避免子树高度变化，因为无论是 2-3-4树还是红黑树，一旦子树高度有变动，势必会影响其他子树进行调整，所以我们在插入和删除结点时尽量通过子树内部调整来达到平衡，2-3-4树实现平衡是通过结点的旋转和结点元素数变化，红黑树是通过结点旋转和变色。 下面来对照着 2-3-4树说一下红黑树结点的添加和删除： 结点插入 2-3-4树中结点添加需要遵守以下规则： 而将这些规则对应到红黑树里，就是： 如上图所示，虽然向红黑树中插入了一个新结点，但由于旋转和变色，子树的高度保持不变。 删除结点 红黑树的删除要比插入要复杂一些，我们还是类比 2-3-4树来讲： 将这些规则对应到红黑树中即： […]

基本概念 字典树是一种有序的树状结构，每个节点表示字符与字符串。字典树可以合并储存有相同前缀的字符串。常用于解决前缀匹配和字串查找的问题。是一种牺牲空间换取时间的做法。 插入 字串长度的时间 插入一个新单词 查找 单词长度的时间 查找是否存在某单词 查找是否存在某前缀 实现 通过HashMap实现子节点 class TrieNode {    String word;    HashMap<Character, TrieNode> next;​    public TrieNode() {        next = new HashMap<>();   }}​class TrieTree {    public TrieNode root;​    public TrieTree(TrieNode root) {        this.root = root;   }​    public […]

代码：包含初始化、合并（包含按秩优化）、查询（包含路径压缩）、校验是否为同一集合

转自某论坛 （i）邻接矩阵表示法，如图： 矩阵中，行和列 与图中的节点对应 　　也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有 个元素中，只有 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。 　　同样，对于网络中的权，也可以用类似邻接矩阵的 矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。 （ii）关联矩阵表示法 　　也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为 -1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个 1，一个-1）可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有mn 个元素中，只有 2m个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。 　　同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。 （iii）弧表示法 例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表示如上： 为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按照这样的顺序存储的。 （iv）邻接表表示法 　　邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如，例7所示的图，邻接表表示为 最后的0应该表示结尾。 （v）星形表示法 星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点n 出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（forward star）表示法。 例如，在例7所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前向星形表示法表示如下： 《星形表示法详解及其转化算法》 注意：上面的第一张表实际上有个错误，仔细看的童鞋应该能发现，起始地址point(i) : 1 , 3 , 4 , 5 , 7 , 9 ,那个6应该是5（这里待核实） 通常情况下会设置一个st[i] 数组，和STL类似， [st[i],st[i+1]) 恰好为以结点i开头的边下标。对应于上个例子的第一张表，则该数组为： st[6]={1,3,4,5,7,9}; 还会有一个数组对应于第二张表，主要使用第三行数据， v[8]={2,3,4,2,3,5,3,4}; 下面的程序把树的前向星表示转化成左儿子-右兄弟表示，以方便后续算法实现。 图最常用的表示法是邻接矩阵和邻接表。对于静态图（建图完毕后不再修改图的结构）往往用前向星来代替邻接表，节省空间和时间。 邻接矩阵不管输入格式如何，总是很容易得到邻接矩阵，只需要注意平行边的情况。前向星邻接矩阵本身就包含了顶点序，因此很容易转化为前向星： 把邻接矩阵转换为前向星表示法： 把边列表转化成前向星的方法类似，只需要把第一顶点相同的结点串成链表，用计数器法进行结点编号分配，和前向星转化成左儿子-右兄弟一样每次插入到链表首部，在O(m)时间内可以建立前向星表示。当然，也可以按第一顶点为关键字直接进行快速排序，不过速度稍微慢一些

转自某故事会。 最近在看数据结构中图的相关知识，之前看的很混乱，现在总算是理清了，在此记录一下。 目录： 图的基本知识 广度优先搜索（BFS） 深度优先搜索（DFS） 总结 代码实现 一、图的基本知识 日常有很多地方都用到了图，比如地铁线路图，计算机网络连线图等。 图就就是下面这种由节点和连接每对节点的边所构成的图形。 这是最简单的图，我们可以根据图的一些特性将其进行分类： 1、如果给边加上一个值表示权重，这种图就是加权图，没有权重的图就是非加权图，没有权重的边只能表示两个节点的连接状态，而有权重的边就可以表示节点之间的“连接程度”。 2、如果给边加上表示方向的箭头，即表示节点之间的传递方向，这种图就是有向图，而边上没有箭头的图就是无向图。 3、如果图中任意两个节点都能找到路径可以将它们进行连接，则称该图为连通图，上面这个图就是连通图，反之则为非连通图。 下面两个图分别为加权图和有向图： 非连通图如下所示： 知道了什么是图，和图相关的算法主要有两类： 图的搜索算法：图的搜索指的就是从图的某一节点开始，通过边到达不同的节点，最终找到目标节点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”两种。 图的最短路径问题：最短路径问题就是要在两个节点的所有路径中，找到一条所经过的边的权重总和最小的路径。相关算法有“贝尔曼-福特算法”，“狄克斯特拉算法”和“A* 算法”三种。 二、广度优先搜索 广度优先搜索和深度优先搜索一样，都是对图进行搜索的算法，都是从起点开始顺着边搜索，此时并不知道图的整体结构，直到找到指定节点(即终点)。在此过程中每走到一个节点，就会判断一次它是否为终点。 广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。 在广度优先搜索中，有一个保存候补节点的队列，队列的性质就是先进先出，即先进入该队列的候补节点就先进行搜索。 下图中红色表示当前所在的节点（节点A），终点设为节点G，将与节点A直连的三个节点B, C, D放入存放候补节点的队列中（与节点A直连的三个节点放入时可以没有顺序，这里的放入顺序为B, C, D），用绿色表示。 此时队列中有B, C, D三个节点，我们来看看广度优先搜索是如何对各节点进行搜索的。 1、上面左图：此时从队列中选出一个节点，优先选择最早放入队列的那个节点，这里选择最左边的节点B。将已经搜索过的节点变为橙色（节点A），搜索到节点B时，将与节点B直连的两个节点E和F放入队列中，此时队列为 [C, D, E, F]。 2、上面中图：对节点B搜索完毕，节点B不是要找的终点，再搜索节点C，将与节点C直连的节点H放入队列中，此时队列为 [D, E, F, H]。 3、然后对节点D进行同样的操作，此时队列为 [E, F, H, I, J]。 4、上面右图：对与节点A直连的节点搜索完毕，再对与节点B直连的节点进行搜索（因为剩下的点中它们最先放入队列），这里选择节点E，将与节点E直连的节点K放入队列中，此时队列为 [F, H, I, J, K]。 […]

链表概念的讲解 链表是什么： 链表是一种线性数据结构，每个节点都存有数据，通过指针将各个节点链接在一起。 链表的性质： 一致性: 每个节点有相同的数据结构，相同的数据大小，内存中占据相同的大小，存储相同的数据类型。 有序性: 节点之间的相对顺序固定，排在某节点前面的节点就是它的前驱，后面的节点就是它的后继，所以定义里面有’线性’。 链表的分类： 链接方式分类：单向链表，双向链表。 ps: 代码展示只用单链表举例。 单链表结构 单链表中的每个结点包含数据+指向后继节点的指针，通过这种方式，单链表将所有结点按顺序组织起来。 节点定义： 双链表结构 双链表中的每个节点包含数据+指向前驱和后继的指针。 链表的基本操作： 链表基本操作: 插入、搜索、删除。 以下分别讲每个操作是如何进行的，时间复杂度多少，为什么是那么多，根据时间复杂度判断链表的适合场景。 查找 按照索引/值查找：遍历找到对应的位置/值，然后返回该节点。 时间复杂度：是线性遍历的，所以时间复杂度是 O(n)。因为时间复杂度相对较高，所以在大量数据需要经常用检索的时候就不要用链表了。 插入 按照 index 插入 先创建新节点 new_node； 找到要插入的位置的前驱节点 pre； 新节点 new_node 指向 pre 的后继节点； pre 指向新节点。 时间复杂度：由于第2步要线性遍历去找 index 位置，所以时间复杂度是 O(n)。如果插入在头部，就不需要找位置，时间复杂度是 O(1)。 删除 如何做删除的？ 找到待删节点的前驱 pred； 把它的前驱节点的后继指向待删节点后继的后继。 时间复杂度：因为要去找前驱，所以线性遍历，时间复杂度是 O(n)。如果删除头部，就不需要找位置，时间复杂度是 O(1)。 链表常见的考点: 哑节点(边界条件)-用于简化边界情况，链表为空或链表的头结点和尾节点。解决办法：自己创建一个哑节点，然后把它的后继连接原节点。 […]