数据结构和算法 - Githubissues

排序

冒泡排序，冒泡排序的时间复杂度为O(n^2)。稳定。

冒泡排序的Python代码实现（也包含其他算法） https://www.geeksforgeeks.org/bubble-sort/

快速排序 http://bubkoo.com/2014/01/12/sort-algorithm/quick-sort/


1. 在数据集之中，选择一个元素作为”基准”（pivot）。
2. 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
3. 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。


首先，把基准元素移到結尾（如果直接选择最后一个元素为基准元素，那就不用移动），然后从左到右（除了最后的基准元素），循环移动小于等于基准元素的元素到数组的开头，每次移动 storeIndex 自增 1，表示下一个小于基准元素将要移动到的位置。循环结束后 storeIndex 所代表的的位置就是基准元素的所有摆放的位置。所以最后将基准元素所在位置（这里是 right）与 storeIndex 所代表的的位置的元素交换位置。要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。

![image](https://user-images.githubusercontent.com/12871721/39025895-cd79d918-4484-11e8-8c7a-4c0a6fbfd946.png)

C语言里的qsort()函数

- マージソート（归并排序）
マージソートの例。まずリストを小さな単位に分け、二つのリストをそれぞれの要素の先頭を比較してマージする。最後までこの操作をくり返すと、リストはソートされている。
空间复杂度为O(n)，时间复杂度为O(nlogn)。
![image](https://user-images.githubusercontent.com/12871721/34046940-0c8f43fe-e1f2-11e7-93e0-b1c9b8ed625a.png)

- コムソート（英: comb sort）やコームソート, 梳排序
梳排序是改良自泡沫排序和快速排序，其要旨在于消除乌龟，亦即在阵列尾部的小数值，这些数值是造成泡沫排序缓慢的主因。相对地，兔子，亦即在阵列前端的大数值，不影响泡沫排序的效能。
在泡沫排序中，只比较阵列中相邻的二项，即比较的二项的间距(Gap)是1，梳排序提出此间距其实可大于1，改自插入排序的希尔排序同样提出相同观点。梳排序中，开始时的间距设定为阵列长度，并在循环中以固定比率递减，通常递减率设定为1.3。在一次循环中，梳排序如同泡沫排序一样把阵列从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。如果间距递减至1，梳排序假定输入阵列大致排序好，并以泡沫排序作最后检查及修正。
原作者以随机数作实验，得到最有效递减率为1.3的。如果此比率太小，则导致一循环中有过多的比较，如果比率太大，则未能有效消除阵列中的乌龟。

- 插入排序
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。

举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。

- 二分排序
利用二分法的思想对插入排序进行改进的一种插入排序算法。
二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

- 面试中的 10 大排序算法总结.md
https://github.com/francistao/LearningNotes/blob/master/Part3/Algorithm/Sort/%E9%9D%A2%E8%AF%95%E4%B8%AD%E7%9A%84%2010%20%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93.md

- 排序算法稳定性
定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，
而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。

稳定性的好处：
排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。

-----------------------------------------------------------------
**排序算法性能和使用场景总结**
按平均时间将排序分为四类：
（1）平方阶(O(n2))排序
    　一般称为简单排序，例如直接插入、直接选择和冒泡排序；
（2）线性对数阶(O(nlgn))排序
    　如快速、堆和归并排序；
（3）O(n1+￡)阶排序
    　￡是介于0和1之间的常数，即0<￡<1，如希尔排序；
（4）线性阶(O(n))排序
    　如桶、箱和基数排序。
各种排序方法比较
     简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
    　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
    　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
    　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
    　若要求排序稳定，则可选用归并排序。
----------------------------------------------------------------------------
**海量排序算法**
各种各样的排序，但是那些排序都是只能在内存中进行排序，而如果给大量的数据（内存中无法容纳）,要给这些数据进行排序，我们就需要借助于一种外排序----归并排序.

对于大数据的排序，我们只能讲数据存储在磁盘上，然后将存储数据的文件进行分割，将小文件中的数据拿到内存中去借助快排进行排序，最后将小文件合并为一个大文件。在这中间，小文件比较多，我将小文件名存储在一个队列中，当队列的大小为1时，合并完毕。

**实际场景 的思路**
首先因为内存足够大所以可以把所有数据上载到内存，所以只用考虑内部排序。至于使用什么内部排序，就与数据本身有关了。如果数据足够混乱，当然选择快速排序。如果数据本身就有一定次序，就应该考虑其他排序了，如希尔排序。还有就是因为数据本身很大建议使用链表而非数组存储。（虽然内存足够大）

**海量数据处理 - 10亿个数中找出最大的10000个数（top K问题）**
http://blog.csdn.net/zyq522376829/article/details/47686867
最容易想到的方法是将数据全部排序，
第二种方法为局部淘汰法，
第三种方法是分治法，
第四种方法是Hash法：先通过Hash法，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的10000个数。
第五种方法采用最小堆。首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000），然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O（nmlogm），空间复杂度是10000（常数）。

查询算法 http://www.cnblogs.com/maybe2030/p/4715035.html

■リニアサーチ（線形探索法）、顺序查找先頭から順番に探す値が見つかるまで探していくだけ.

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 当查找不成功时，需要n+1次比较，时间复杂度为O(n);

■バイナリサーチ、二分查找ソート済みの配列において、検索する間隔を半分に分割しながらデータを探し出すアルゴリズムです。探索対象の配列がソートされていなければなりません。 C言語はbsearch関数。
■3. 插值查找基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。　　注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。　　复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。二分查找中查找点计算如下：　　mid=(low+high)/2, 即mid=low+1/2(high-low); 　　通过类比，我们可以将查找的点改进为如下：　　mid=low+(key-a[low])/(a[high]-a[low])(high-low)，
■4. 斐波那契查找基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

■5. 树表查找 ■5.1 最简单的树表查找算法——二叉树查找算法。复杂度分析：它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡

■5.2 平衡查找树之2-3查找树（2-3 Tree）和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key

■5.3 平衡查找树之红黑树（Red-Black Tree） 2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。基本思想：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。下图可以看到红黑树其实是2-3树的另外一种表现形式：如果我们将红色的连线水平绘制，那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。红黑树的平均高度大约为logn。

红黑树这种数据结构应用十分广泛，在多种编程语言中被用作符号表的实现，如： Java中的java.util.TreeMap,java.util.TreeSet； C++ STL中的：map,multimap,multiset； .NET中的：SortedDictionary,SortedSet 等。

■5.4 B树和B+树（B Tree/B+ Tree）维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。

B树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。

B+树定义： B+树是对B树的一种变形树

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B/B+树常用于文件系统和数据库系统中，它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中，如： Windows：HPFS文件系统； Mac：HFS，HFS+文件系统； Linux：ResiserFS，XFS，Ext3FS，JFS文件系统；数据库：ORACLE，MYSQL，SQLSERVER等中。

■分块查找算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……

■哈希查找总的来说，"直接定址"与"解决冲突"是哈希表的两大特点算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

求解复杂的方程式 1，2分法搜索逼近 2，Newton法（牛顿迭代法）

文字检索

KMP法検索ワードのどの位置で不一致になったかを把握することによって、どこから比較を再開すればよいかをあらかじめ決めることができます。 http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：　移动位数 = 已匹配的字符数 - 对应的部分匹配值 因为 6 - 2 等于4，所以将搜索词向后移动4位。因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。因为空格与A不匹配，继续后移一位。逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

《部分匹配表》是如何产生的？首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。 "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

　   －　"A"的前缀和后缀都为空集，共有元素的长度为0；
　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

BM法 BM（Boyer-Moore）算法是目前被认为最高效的字符串搜索算法，它由Bob Boyer和J Strother Moore设计于1977年。一般情况下，比KMP算法快3-5倍。该算法常用于文本编辑器中的搜索匹配功能。比如大家所熟知的GNU grep命令使用的就是该算法，这也是GNU grep比BSD grep快的一个重要原因。

假设文本串text长度为n，模式串pattern长度为m，BM算法的主要特征为：从右往左进行比较匹配（一般的字符串搜索算法如KMP都是从从左往右进行匹配）；算法分为两个阶段：预处理阶段和搜索阶段；

常规的匹配算法移动模式串的时候是从左到右，而进行比较的时候也是从左到右的；而BM算法在移动模式串的时候是从左到右，而进行比较的时候是从右到左的。

BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。即它充分利用待搜索字符串的一些特征，加快了搜索的步骤。

BM算法实际上包含两个并行的算法（也就是两个启发策略）：坏字符算法（bad-character shift）和好后缀算法（good-suffix shift）。这两种算法的目的就是让模式串每次向右移动尽可能大的距离（即上面的BM()尽可能大）。

■深度优先搜索算法(DFS)/广度优先搜索算法(BFS) 深度优先搜索算法是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

图的深度优先搜索算法和广度优先搜索算法在时间复杂度上是一样的。深度优先更适合目标比较明确，以找到目标为目的的情况。广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

■贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。[1]比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。

细节：

建立数学模型来描述问题。
把求解的问题分成若干个子问题。
对每一子问题求解，得到子问题的局部最优解。
把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步 do ,求出可行解的一个解元素；最后，由所有解元素组合成问题的一个可行解。

■滑动窗口算法应用例：文本检测中的滑动窗口滑动窗口是检测图像中目标对象的最常用手段。 1，在文本检测阶段，我们首先定义正、负样本，正样本图像描述了含有文本的图像，负样本描述了不含文本的图像。 2，通过在原图像沿行、列滑动我们定义好的窗口，并让窗口内图像与正负样本进行比较。 3，当窗口遍历过整幅图像后，获得原图像对应的掩膜，高亮度的区域都为疑似文本框的区域。 4，掩膜中的文本框断断续续的，因此还考虑使用形态学膨胀操作来让文本框更加完整

■分治算法在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

三、分治法适用的情况分治法所能解决的问题一般具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 3) 利用该问题分解出的子问题的解可以合并为该问题的解； 4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

■递归算法自己直接或间接调用自己的函数称为递归函数。

■动态规划算法（Dynamic programming，简称DP）动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

https://www.cnblogs.com/erma0-007/p/8629831.html 链表链表是一种由节点（Node）组成的线性数据集合，每个节点通过指针指向下一个节点。它是一种由节点组成，并能用于表示序列的数据结构。

单链表：每个节点仅指向下一个节点，最后一个节点指向空（null）。双链表：每个节点有两个指针p，n。p指向前一个节点，n指向下一个节点；最后一个节点指向空。循环链表：每个节点指向下一个节点，最后一个节点指向第一个节点。

时间复杂度：索引：O(n) 查找：O(n) 插入：O(1) 删除：O(1)

栈栈是一个元素集合，支持两个基本操作：push用于将元素压入栈，pop用于删除栈顶元素。后进先出的数据结构（Last In First Out, LIFO）

时间复杂度索引：O(n) 查找：O(n) 插入：O(1) 删除：O(1)

C++代码实现： http://www.cnblogs.com/QG-whz/p/5170147.html

队列队列是一个元素集合，支持两种基本操作：enqueue 用于添加一个元素到队列，dequeue 用于删除队列中的一个元素。先进先出的数据结构（First In First Out, FIFO）。

时间复杂度索引：O(n) 查找：O(n) 插入：O(1) 删除：O(1)

树

Edge – connection between one node to another.
Path – a sequence of nodes and edges connecting a node with a descendant.
Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.
Depth –The depth of a node is the number of edges from the node to the tree's root node.
Level – The level of a node is defined by 1 + the number of connections between the node and the root. Simply, level is depth plus 1. The important thing to remember is when talking about level, it starts from 1 and the level of the root is 1.

二叉树（Binary Tree） 二叉树是一个树形数据结构，每个节点最多可以有两个子节点，称为左子节点和右子节点。（have the most 2 nodes. allow: 0, 1, 2 nodes. Dont allow 3,4,... nodes ）满二叉树（Full Tree）：二叉树中的每个节点有 0 或者 2 个子节点。(即不允许只有一个节点。要么没节点，要有就必须有2个节点) A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.

完美二叉树（Perfect Binary）：二叉树中的每个节点有两个子节点，并且所有的叶子节点的深度是一样的。 (上图其实就是一个Perfect Binary)

完全二叉树：二叉树中除最后一层外其他各层的节点数均达到最大值，最后一层的节点都连续集中在最左边。 A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

BST 二叉查找树（BST）是一种二叉树。其任何节点的值都大于等于左子树中的值，小于等于右子树中的值。时间复杂度索引：O(log(n)) 查找：O(log(n)) 插入：O(log(n)) 删除：O(log(n))

平衡二叉树和红黑树，可以使查找为O(log(n))。

ハッシュ木(Hash tree, ハッシュツリー)またはマークル木(Merkle tree) https://github.com/rainit2006/Block-Chain/issues/1 https://www.cnblogs.com/fengzhiwu/p/5524324.html 在p2p网络下载网络之前，先从可信的源获得文件的Merkle Tree树根。一旦获得了树根，就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接受到的Merkle Tree。如果Merkle Tree是损坏的或者虚假的，就从其他源获得另一个Merkle Tree，直到获得一个与可信树根匹配的Merkle Tree。

Merkle Tree和Hash List的主要区别是，可以直接下载并立即验证Merkle Tree的一个分支。因为可以将文件切分成小的数据块，这样如果有一块数据损坏，仅仅重新下载这个数据块就行了。如果文件非常大，那么Merkle tree和Hash list都很到，但是Merkle tree可以一次下载一个分支，然后立即验证这个分支，如果分支验证通过，就可以下载数据了。而Hash list只有下载整个hash list才能验证。

Merkle Tree的特点 MT是一种树，大多数是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点； Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出的。[4][5] 　　通常，加密的hash方法像SHA-2和MD5用来做hash。但如果仅仅防止数据不是蓄意的损坏或篡改，可以改用一些安全性低但效率高的校验和算法，如CRC。

我们怎么通过两个机器的merkle treee信息找到不相同的文件? 这个比较检索过程如下: 　　Step1. 首先比较v0是否相同,如果不同，检索其孩子node1和node2. 　　Step2. v1 相同，v2不同。检索node2的孩子node5 node6; 　　Step3. v5不同，v6相同，检索比较node5的孩子node 11 和node 12 　　Step4. v11不同，v12相同。node 11为叶子节点，获取其目录信息。　　Step5. 检索比较完毕。　　以上过程的理论复杂度是Log(N)。过程描述图如下:

Merkle Tree的应用

数字签名
P2P网络在P2P网络中，Merkle Tree用来确保从其他节点接受的数据块没有损坏且没有被替换，甚至检查其他节点不会欺骗或者发布虚假的块。大家所熟悉的BT下载就是采用了P2P技术来让客户端之间进行数据传输，一来可以加快数据下载速度，二来减轻下载服务器的负担。
Trusted Computing 可信计算是可信计算组为分布式计算环境中参与节点的计算平台提供端点可信性而提出的。

パトリシア木（英: Patricia tree），基数树 通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。

Trie tree トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。

Merkle Patricia Tree(简称MPT树，实际上是一种trie前缀树) https://ethfans.org/toya/articles/588 一种经过改良的、融合了默克尔树和前缀树两种树结构优点的数据结构，是以太坊中用来组织管理账户数据、生成交易集合哈希的重要数据结构。

哈希函数 基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。 https://blog.csdn.net/Thousa_Ho/article/details/73065017

rainit2006 / C-Program

数据结构和算法 #28