数据结构与算法学习心得

2019-01-24 | 阅读：次

前言

本文档主要是针对在学习和工作中对于数据结构与算法的感悟，主要包括以下内容常用的基础的数据结构与算法。其涉及到以下数据结构：数组、链、栈、队列、散列表、二叉树、堆、跳表、图、树等。涉及到的算法主要包括递归、排序、二分查找、搜索、哈希算法、分治算法、回溯算法、动态规划、字符串匹配算法等。
对于此部分的学习不要死记硬背，要掌握分析的能力，抓住算法的特定，应用场景。用到的时候，能够想到即可，再花些时间弄懂即可。知识需要沉淀，不要想试图一下子掌握所有，学习知识的过程是反复迭代、不断沉淀的过程。

基础知识

数据结构，就是一组数据的存储结构。算法，就是操作数据的一组方法。数据结构是为算法服务的，算法要作用于特定的数据结构。

复杂度分析

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标，其中主要使用的是时间和空间复杂度分析。

大O复杂度

代码的执行时间T(n)与每行代码的执行次数n成正比，其表达式如下所示：

T(n)=O(f(n))

注释：

T(n)：表示代码的执行时间。
n：表示数据规模的大小。
f(n)：表示每行代码执行次数的总和。
O：表示代码的执行时间T(n)与f(n)成正比。

大O时间复杂度，并非代码执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。其表示法，指出了最糟糕情况下的运行时间。

时间复杂度分析

只关注循环次数最多的一段代码。由于大O表示法只是表示一种变化趋势，因此会忽略掉公式中的常量、低级、系数。
将所有复杂度相加，总复杂度等于量级最大的那段代码复杂度。
对于嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
对于多规模，要求多个规模复杂度之和。

常见时间复杂度分析

以下将列举几种常见时间复杂度量级，按数量级递增

常量阶：O(1)
对数阶：O(logn)
线性阶：O(n)
线性对数阶：O(nlongn)
平方阶：O(n^2)、立方阶阶O(n^3)…K次方阶O(n^k)
指数阶：O(2^n)
阶乘阶：O(n!)

常见的复杂度级别

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。其中常见的如下所示

O(1)：只要代码的时间复杂度不随n的增长而增长，这样代码的时间复杂度表示常量级。

O(log n)、O(nlog n)：不管以2为底、以3为底、还是以10为底，都把所有对数阶的时间复杂度记为O(log n)，因为对数之间可以相互转化，log3^n =log3^2 * log2^n，所以O(log3^n)=O(Clogn)，其中C=log3^2是一个常量，忽略此系数。

O(m+n)：对于无法评估的m和n两个数据规模，要用此方法表示。

空间复杂度分析

空间复杂度全称为渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

常见数据结构

数组

数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。
数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。

改善数组低效的“插入”和“删除”

当数组中存储的数据没有任何规律，数组只是当做一个存储数据的集合，侧可以直接将数组插入第K个位置，为了避免大规模数据搬移，可以将原来k位置的数据摆到数组元素的最后。
在默写场景下，并非要数组中数据连续性，这时可以考虑将多次删除操作集中在一起执行，从而每次删除操作并不是真正的搬移数据，而是记录数据已经被删除，当数组没有更大空间存储数据时，才触发一次真正的删除操作，这样可以大大减少删除操作导致的数据搬移。
总结，不要去死记硬背某个数据结构或者算法，要学习它背后的思想和处理技巧，这些东西才是最有价值的。

用数组比高级数组更合适场景

Java ArrayList无法存储基本类型，例如int、long，需要封装为Integer、Long类型，而Autoboxing、Unboxing则有一定的性能消耗，若是特别关注性能，或是希望使用基本类型，就可以选用数组。
数组大小事先已知，并且对数组的操作非常简单，用不到ArrayList提供的大部分用法，也可以直接使用数组。
多维数组用数组更加直观。

数组寻址公式

一维数组寻址公式：

a[k]_address = base_address + k * type_size
二位数组寻址公式m*n数组：

a[i][j]_address = base_address +(i * n + j) * type_size

链表

链表不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。
常见的链表结构为：单链表、双向链表、循环链表。

链表实际用法

在实际软件开发中，从链表中删除一个数据基本有两种情况：

删除节点中“只等于某个定值”的节点。

单纯的删除操作时间复杂度为O(1)，但是遍历查找的时间为主要的耗时点，对应的时间复杂度为O(n)，根据时间复杂度分析中加法法则，删除等于给定值节点对应的链表操作的总时间复杂度为O(n)。
删除给定指针的节点。

已知要删除的节点，需找到此节点的前驱节点，单向链表需要从链表头开始找，此时时间复杂度为O(n)，对于双向链表直接可以取得，此时时间复杂度为O(1)。

链表代码书写常用技巧

优雅的写出链表代码5大技巧：

理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

警惕指针丢失和内存泄漏（单链表）

关键为将拆分的数据，挂载到已知变量。

利用“哨兵”简化实现难度

链表中的“哨兵”节点是解决边界问题，不参与业务逻辑。

重点留意边界条件处理

对于边界处理方面，需要常问下面4个问题：

如果链表为空时，代码是否能正常工作？
如果链表只包含一个节点时，代码是否能正常工作？
如果链表只包含两个节点时，代码是否能正常工作？
代码逻辑在处理头尾节点时是否能正常工作？

举例画图，辅助思考

核心思想：释放脑容量，留更多的给逻辑思考，产生一个清晰思路。

栈

从栈的操作特性上来看，栈是一种“操作受限”的线性表，只运行在一段插入和删除数据。相比于数组和链表，栈带给我们的只有限制，并没有任何优势，那我们直接使用数组或链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？

事实上，从功能上来说，数组或链表确实可以替代栈，但是，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也容易出错。

什么场景下使用栈

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，此时首选“栈”这种数据结构。

栈复杂度

不管是顺序栈还是链式栈，存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)，注意，这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为，这n个空间必须的，无法省掉。所以我们说空间复杂度的时候，是指出了原本的数据存储空间外，算法运行还需要额外的存储空间。
不管顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)。

队列

队列的核心特点是先进先出，也是一种操作受限的线性表数据结构。

队列应用场景

队列作为基础的数据结构，其应用也很广泛，特别是一些特有某些额外特性的队列，比如循环队列，阻塞队列，并发队列。他们在很多底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列Disruptor、Linux环形缓存，都用到了循环并发队列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁等。

阻塞队列

阻塞队列，其实就是队列基础上增加了阻塞操作。就是在队列为空时，从队头取数据会被阻塞。因为此时没有数据可取，直到队列中有了数据才能返回；如果队列已满，那么插入数据的操作就会被阻塞，直到队列中空闲位置后再插入数据，然后再返回。例如“生产者-消费者模型” ，这种基于阻塞队列实现的“生产者-消费者模型” ，可以有效地协调生产和消费的速度。

并发队列

线程安全的队列叫并发队列，实现方式是直接在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。实际上，基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列。

队列应用举例

对于大部分资源有限的场景，当没有空闲资源时，基本上可以通过“队列”这种数据结构来实现请求排队。

线程池中没有空闲线程时，如何处理

一般情况有两种处理策略，第一种为非阻塞的处理方式，直接拒绝任务；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。
为了达到公平地处理每一个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。采用哪种队列存储也有两种方式。第一种，基于链表的实现方式，可以实现一个支持无限排队的无界队列，但是可能会导致过多的请求排队等待，请求处理的响应时间过长，所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。第二种，基于数组实现的有界队列，队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更合理。不过设置一个合理的队列大小，也是非常有讲究的，队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源，发挥最大性能。
总结：对于如何设计解决方法，先要分析业务中基本需求和特点，选择合适的数据结构，随后分析此类数据结构有几种实现方式，每种实现方式具有那些优点和缺点，平衡自己业务需求，进行最终选择。

核心算法

递归

什么是递归

递归是一种非常高效、简洁的编码技巧、一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等。

方法或函数调用自身的方式称为递归，调用称为递，返回称为归。

基本上，所有的递归问题都可以用递推公式来表示，比如:

f(n) = f(n-1) + 1

f(n) = f(n-1) + f(n-2)

f(n) = n*f(n-1)

递归优缺点

优点：代码的表达力很强，简洁。

缺点：空间复杂度高、有栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

什么样的问题采用递归解决

一个问题只要同时满足一下3个条件，就可以用递归来解决：

问题的解可以分解为几个子问题的解。

问题和分解后的子问题，除了数据规模不同，求解思路完全一样。

存在递归终止条件。

如何实现递归

递归代码编写
写递归代码的关键就是找到如何将大问题分解为小问题的规则，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件转化为代码。

递归代码理解
对于递归代码，若试图想清楚整个递和归的过程，实际上是进入一个思维误区，而具体做法为，如果一个问题A可以分解为若干个子问题B、C、D，可以假设子问题B、C、D已经解决。而且，只需要思考问题A和子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样理解起来就简单多了。
因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归常见问题及解决方案

警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。

警惕重复计算：通过某种数据结构来保存已求解过的值，例如hash，从而避免重复计算。

将递归转为非递归

基本上所有递归代码都可改为迭代循环的非递归写法。主要方式为：抽象递推公式，初始值和边界条件，然后用迭代循环实现。

排序

经典排序

最经典与常见的排序算法为：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。

冒泡排序、插入排序、选择排序：时间复杂度为O(n^2)，基于比较排序。

快速排序、归并排序：时间复杂度为O(nlogn)，基于比较排序。

计数排序、基数排序、通排序: 时间复杂度为O(n)，不基于比较排序。

如何分析一个排序算法

排序算法的执行效率。

最好情况、最坏情况、平均情况时间复杂度。有序度不同的数据，对于排序的执行时间肯定是有影响的，因此要知道排序算法在不同数据下的性能表现。
2，时间复杂度的系数、常数、低阶。从实际软件开发中考虑，基本排序都是规模比较小的数据。

比较次数和交换（或移动）次数。以及比较的排序算法，会涉及两种操作，比较和交换或移动，分析执行效率时，应当考虑。

排序算法的内存消耗。

原地排序算法，就是特质空间复杂度是O(1)的排序算法，即不用耗费额外的内存进行存储。

排序算法的稳定性。

稳定性，指待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

冒泡排序

冒泡排序执行过程

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让他俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就会完成了n个数据的排序工作。

冒泡优化方式

优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

冒泡分析

是原地排序算法吗？
冒泡过程只涉及相邻数据的交互操作，没有申请格外的临时空间，空间复杂度为O(1)，因此是原地排序算法。

是稳定的排序算法吗？
只有交互才改变两个元素的前后顺序，当相等的时候，不做交互，相同大小的数据在排序前后不会改变顺序，因此是稳定的排序算法。

时间复杂度是多少？

最好时间复杂度：顺序排列，只需要进行一次冒泡操作，就可以结束，O(n)。

最坏时间复杂度：逆序排列，需要进行n次冒泡操作，O(n^2)。

平均时间复杂度：加权平均期望时间复杂度为O（n^2）

冒泡平均时间复杂度

通过有序度和逆序度来分析平均时间复杂度。

有序度是数组中具有有序关系的元素对的个数。其数学表达式为：a[i] <= a[j], 且 i < j
例如：对于一个倒序排列的数组，6、5、4、3、2、1，有序度为0；对于一个完全有序的数组，比如1、2、3、4、5、6，有序度就是n*(n-1)/2，也就是15，此为满有序度。

逆有序度的定义与有序度相反（从小到大为有序），a[i] > a[j],且 i < j。

核心公式： 逆虚度 = 满有序度 - 有序度。

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加1。不管算法怎么改进，交换次数总是确定的，为逆序度，也就是n*(n-1)/2-初始有序度。

对于包含n个数据的数组进行冒泡排序，平均交换次数是多少？

最坏情况下，初始状态为有序度为0，所以要进行n*(n-1)/2次交换（减少逆序度）。

最好情况下，初始状态的有序度是n*(n-1)/2，就不需要进行交换。

平均情况下，表示不高也不低的平均状况需要n*(n-1)/4次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是O(n^2)，所以平均情况下的实际复杂度为O(n^2)。

插入排序

核心思想

动态地往有序集合中添加数据，同时保持集合数据一致有序。

插入排序执行过程

首先，将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素（数组的第一个元素）。插入算法的核心思想是取未排序区间的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一致有序。重复这个过程，直到未排序区间中元素为空，算法结束。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。对于不同的查找插入点方法（从头到尾、从未到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，等于逆序度。

插入排序分析

插入排序是原地排序算法？
插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，因此是一个原地排序算法。

插入排序是稳定的排序算法？
对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，从而保持书序不变，因此插入排序是稳定的排序算法。

插入排序时间复杂度？

最好情况：要排序的数据有序，此时不需要搬移任何数据，每次只需要比较一个数据就能确定插入的位置，这时最好时间复杂度为O(n)。

最坏情况：如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以要移动大量数据，所以最坏情况时间复杂度为O(n^2)。

平均情况：在数组中插入一个数据的平均时间复杂度是O(n)，所以对于插入排序，每次插入操作都相当于在数组中插入一个数据，循环执行n此插入操作，所以平均是将复杂度为O(n^2)。

选择排序

核心思想

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序分析

选择排序空间复杂度为O(1)，是一种原地排序算法，选择排序最好情况时间复杂度，最好情况情况和平均情况时间复杂度都为O(n^2)。

选择排序是稳定排序算法吗？
否，选择排序每次都要找剩余未排序元素中最小值，并和前面的元素交换位置，这样破坏了稳定性。例如5、8、5、2、9一组数据，使用选择排序算法，第一次找到最小元素2，与第一个5交换位置，那么第一个5和中间的5顺序变了，所以为不稳定。正是如此，相对于冒泡排序和插入排序，选择排序就稍微逊色。

归并排序

核心思想

如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并再一起，这样整个数组就有序了。归并排序使用的是分治思想。分治，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。分治算法一般都是用递归来实现，分治是一种解决问题的处理思想，递归时一种编程技巧。

归并排序递推公式

递推公式：    
merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(a+1...r))，其q=(p+r)/2    

终止条件：    
p >= r 不用再继续分解    

归并排序性能分析

归并排序是稳定排序算法?
归并排序稳不稳定关键要看merge()函数，也就是两个有序子数组合并成一个有序数组那部分代码，在合并的过程中，如果A[p…q]和A[q+1…r]之间有值相同的元素，先把A[p…q]中的元素放入tmp数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定排序算法。

归并排序时间复杂度？
对于递归求解的问题可以写成递推公式，同时递归代码的时间复杂度也可以写成递推公式。

对于a可以分解为b、c求解，a的时间是T(a)，求解问题b、c的时间分别是T(b)和T(c)，那么其递推公式为T(a) = T(b) + T(c) + k，其中k等于将两个子问题b、c的结果合并成问题a的结果所消耗的时间。
假设n个元素进行归并排序需要的时间是T(n)，那分解成两个子数组排序的时间都是T(n/2)。对于merge()函数合并两个有序子数组的时间复杂度是O(n)，因此参照递推公式，归并排序的时间复杂度的计算公式是：
  T(1)=C; n=1时，只需要常量级的执行时间，所以表示为C。
  T(n)=2*(n/2)+n; n>1
  进一步推导：    
  T(n)=2*T(n/2) + n
  = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
  = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
  = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
  ......
  = 2^k * T(n/2^k) + k*n
  当T(n/2^k)=T(1)时，也就是n/2^k=1,得到k=log2n。
  将k值带入公式，得：T(n)=Cn+nlog2n。
  T(n) = O(nlogn)。
  ......
归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况、还是平均情况，时间复杂度都是O(nlogn)。
归并排序的空间复杂度？
递归代码的空间复杂度并不像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用，临时内存空间最大也不会超过n个数据大小，所以空间复杂度是O(n)。

快速排序

核心思想

如果要排序数组下标从p到r之间的一组数据，选择p到r之间的任意一个数据作为pivot(分区点，一般情况下，可以选择p到r区间的最后一个元素)。遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放在右边，将pivot放到中间，经此之后，数据p到r之间的数据就被分成三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。根据分治、递归的处理思想，可以用递归排序下标从p到q-1之间和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有数据都有序。

递推公式

递推公式：
quick_soft(p…r) = quick_soft(p…q-1) + quick_soft(q+1, r)
终止条件:
p>=r

核心分区函数实现思路

通游标i把A[p…r-1]分成两部分。A[p…i-1]的元素都是小于pivot的，我们暂时叫它“已处理区间”，A[i…r-1]是“未处理区间”。每次多度从未处理的区间A[i…r-1]中取一个元素A[j]，与pivot对比，如果小于pivot，则将其加入到已处理区间的尾部，也就是A[i]的位置。

快速排序和归并排序的不同

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。

快速排序的性能分析

快排是一种原地、不稳定的排序算法。

快速排序时间复杂度？
快排也是用递归来实现的，对于递归代码的时间复杂度公式同样适用，如果每次分区操作，都能正好包数组分成大小接近相等的两个小区间，那快排的时间复杂度求解公式跟归并是相同的。所以，快排的时间复杂度也是O(nlogn)。
若数组也有序，比如1、3、5、7、9，每次选择最后一个元素作为pivot，每次分区得到的两个区间都是不均等的。因此需要进行大约n此分区操作，才能完成快排的整个过程。每次分区平均要扫描大约n/2个元素，这种情况下，快排的时间复杂度从O(nlogn)退化为O(n^2)。

二分查找

核心思想

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。

时间复杂度

二分查找是一个非常高效的查找算法，其时间复杂度为O(logn)。
其分析过程为：
假设数据大小是n，每次查找后数据都会缩小为原来的一半，也就是会除以2。最坏情况下，直到查找区间被缩小为空，才停止。
被查找区间的大小变化：         
n, n/2, n/4, n/8,...,n/2^k...     
通过上式可以看出，这是一个等比数列。其中n/2^k=1时，k的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了k次区间缩小操作，时间复杂度就是O(k)。通过n/2^k=1,可以求出k=log2n，所以时间复杂度为O(logn)。

O(logn)对数小常识

O(logn)是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是O(1)的算法还要高效，因为logn是一个非常“恐怖”的数量级，即便n非常非常大，对应的logn也很小。比如n等于2^32次方，大约是42亿，但是我们查找一个数据，只需要32次。

用大O表示法时，常忽略掉常数，系数和低阶。对于常量级时间复杂度的算法来说，O(1)有可能表示的是一个非常大的常量值，比如O(1000)、O(10000)，所以，常量级时间复杂度的算法有可能有时候还没有O(logn)的算法执行效率高。

总结：任何算法的分析，都要站在应用场景之上。

二分查找引用的局限性

首先，二分查找依赖的是顺序表结构，其实就是数组。
主要原因是二分查找算法需要按照下标随时访问元素。数组按照下标随机访问数据的时间复杂度是O(1)，而链表随机访问的时间复杂度是O(n)。所以，如果数据使用链表存储，二分查找的实际复杂度就会变得很高。

其次，二分查找针对的是有序数据。
二分查找对这一点的要求比较苛刻，数据必须有序，如果数据没有序，需要先排序。排序的时间复杂度最低为O(nlogn)，对于一组静态的数据，没有频繁地插入、删除，可以进行一次排序，多次二分查找，这样排序的成本可以被均摊，二分查找的实际成本就会比较低。所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用。

再次，数据量太小不适合二分查找。
如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。不过，如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找，因为要尽可能地减少比较次数，而比较次数的减少会大大调高性能，这个时候二分查找就比顺序遍历更有优势。

最后，数据量太大也不适合二分查找。
二分查找的底层需要依赖数组这种数据结构，而数组为了支持顺序访问的特性，需要内存空间连续，对内存的要求比较苛刻。比如，我们有1GB大小的数据，如果希望用数组来存储，那就需要用1GB的连续内存空间。

链表二分查找时间复杂度

假设链表长度为n，二分查找每次都要找到中间点（计算中忽略奇偶数差异）：
第一次查找中间点，需要移动指针n/2次；
第二次，需要移动指针n/4次；
第三次，需要移动指针n/8次；
……
一次类推，一直到1时为止。
总共指针移动次数（查找次数）=n/2+n/4+n/8+…+1，这显然是个等比数列，根据等比数列求和公式：Sum=a1(1-q^n)/(1-q)=n*(1-(1/2)^k)/(1-1/2)=n*(1-(1/2)^log2n)/(1-1/2)=n-1.其中k的求解过程为：当2^k=n是表示最后一次，k=log2n。
最后，算法时间复杂度是O(n-1)，忽略常数，记为O(n)，时间复杂度和顺序查找时间复杂度相同，但是二分查找的时候，由于要进行多余的运算，严格来说，会比顺序查找时间慢。

高阶数据结构

跳表

出现背景

对于一个单链表来讲，即便链表中存储的数据是有序的，如果想要在其中找某个数据，也只能从头到尾遍历表，这样的效率很低，时间复杂度为O(n)。

什么是跳表

为一个有序的链表建立多级索引，比如没2个节点提取一个节点到上一级，这样抽出来的节点教唆索引或索引层。其中每个索引节点有个down指针，指向下级节点。依次类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构称为跳表。

跳表时间复杂度

高度

如果链表又n个节点，每2个节点抽取出一个节点作为上一级索引节点，那第1级索引的节点个数大于是n/2，第2级索引节点大约是n/4…第k级索引的节点个数是n/(2^k)。假设索引有h级别，最高级别的索引有2个节点，则有n/(2^h)=2，得出h=log2n -1，包含原始链表一层，整个跳表的高度就是log2n。

时间复杂度

假设在跳表中查询某个数据的时候，如果每一层都编译m个节点，那再跳表中查询一个数据的实际复杂度就是O(m*logn)。那这个m=3，因为每一级索引都最多只需要遍历3个节点。因此在调标中查询某个数据的时间复杂度是O(logn)。

跳表的空间复杂度以及优化

计算索引的节点总数

如果链表又n个节点，没2个节点抽取一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2、n/4…8、4、2，等比数列求和为n-1，所以跳表的空间复杂度为O(n)。

如何优化

多个数据节点，抽出一个索引节点，例如以3为例，n/3、n/9、n/27…27、9、3、1，等比数列求和为n/2。

高效的动态插入和删除

跳表本质上是链表，所以仅插入和删除操作时间复杂度为O(1)，但是在实际情况中，要插入和删除某个节点，需要先查找到指定位置，二个查找比较费时，在跳表中这个查找操作的时间复杂度为O(logn)，所以，跳表的插入和删除操作的时间复杂度为O(logn)。

跳表索引动态更新

当不停地往跳表中插入数据时，如果不更新索引，就有可能出现某两个索引结点之间数据非常多的情况，极端情况下，跳表将会退化称为单链表。解决办法，当网调标中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，可以通过随机函数来决定将这个节点插入到那几个索引中，比如随机函数生产了值K，那就可以把这个节点添加到第1级到第k级索引中。

哈希表

散列思想

散列表的英文叫“Hash Table”，即为“哈希表”或“Hash表”，散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

用于标识查找对象的值叫作键(key)值或者关键字。将其通过一定的规则转换为数组下标的映射方法叫作散列函数（或“Hash函数”“哈希函数”）,而散列函数计算得到的值就叫作散列值（或“Hash值”“哈希值”），而散列值对象的位置存储的为用户信息。

总结：散列表用的就是数组支持按照下标随机访问时，时间复杂度为O(1)的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，用同样的哈希函数，将键值转化为数组下标，从对应的数组下标的位置取数据。

散列函数

散列函数，其是一个函数，用来将key表示元素键值转化为存储下标即散列值。用公式表示为hash(key)，其中key表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值。

如何构造散列函数：

散列函数计算得到的散列值是一个非负整数；

如果key1=key2，那hash(key1) == hash(key2);

如果key1!=key2，那hash(key1) != hash(key2);

关于上述第三点，这个要求看起来比较合理，但是在真实情况下，要想找到一个不同的key对应的散列值都不一样的散列函数，几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突，而且，因为数组的存储空间有限，也会加大散列冲突的概率。

散列冲突

常用的散列冲突解决方法有两类：开放寻址发（open addressing）和链表法（chaining）。

开放寻址法：

开放寻址的核心思想是，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。

线性探测：Linear Probing 当往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
在散列表中查找元素的过程有点类似插入过程，通过散列函数求出要查找元素的键值对应的散列值，然后比较数组下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
使用线性探测法解决冲突的散列表，删除操作稍微有些特别，因为不能单纯地把删除的元素设置为空，因为在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在，解决办法为：将删除的元素，特殊标记为deleted。当线性探测查找的时候，遇到标记为deleted的空间，并不停下来，而是继续往下探测。
线性探测存在的最大问题：当散列表中插入的数据越来越多时，散列冲突发送的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，可能需要探测整个链表，所以最坏情况下的时间复杂度为O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或删除的数据。

二次探测：（Quadratic probing）
所谓二次探测，跟线性探测很像，线性探测每次探测的步长是1，那它探测的下标序列就是hash(key)+0、hash(key)+1、hash(key)+2…而二次探测探测的步长就变成了原来的“二次方”，其下标探测为hash(key)+0、hash(key)+1^2、hash(key)+2^2…。

双重散列：（Double hashing）
所谓双重散列，就是不进要使用一个散列函数，而是要使用一组散列函数hash1(key)、hash2(key)、hash3(key)…，先用第一个散列函数，如果计算得到的存储位置已经被占用，在用第二个散列函数，依次类推，直到找到空闲的存储位置。

装载因子（load factor）：不管使用哪种探测方法，当散列表中空闲位置不多时，散列冲突的概率就会大大提高，为了尽可能保证散列表的操作效率，要尽可能保证散列表中有一定比例的空闲槽位，其用装载因子来表示空位的多少。散列表的装载因子=填入表中的元素个数/散列表的长度。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能就会下降。

链表法

在散列表中，每个“桶（bucket)”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

当插入的时候，通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所有的插入的时间复杂度是O(1)。

当查找、删除一个元素时，同样通过散列函数计算出对应的槽，然后遍历链表查查找或者删除，需要查找到的项。

查找或删除操作的时间复杂度，跟链表的长度k成正比，也就是O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中n表示散列中数据的个数，m表示散列表中“槽”的个数。

散列表设计

提出问题：如何设计一个可以应对各种异常情况的工业级散列表，来避免散列冲突的情况下，散列表性能的急剧下降，并且能抵抗散列碰撞攻击？

设计散列函数关注点

散列函数的设计不能太复杂：过于复杂，会消耗计算时间，间接影响散列表的性能。

散列函数生产的值要尽可能随机并且均匀分布：用来避免或者最小化散列冲突。

综合考虑各种因素，包括长度、特点、分布、还有散列表的大小等。

装载因子过大处理策略

对于动态散列表来说，数据集合是频繁变动的，无法事先申请一个足够大的散列表，随着数据慢慢加入，装载因子会变大，散列表中的元素增多，空闲位置越少，散列冲突概率就越大。

解决办法：设置一个装载因子阈值，当装载因子大于此阈值，进行动态扩容，旧数据存储位置会变，将旧有数据通过散列函数重新计算每个数据的存储位置，进行搬移。

时间复杂度分析：键入一个数据，最好情况下，不需要扩容，最好时间复杂度是O(1)。最坏情况下，散列表装载因子过高，启动扩容，将重新申请内存空间，重新计算哈希位置，并搬移数据，所以时间复杂度为O(n)。用摊还分析法，均摊情况下，时间复杂度解决最好情况，O(1)。

避免低效扩容

当数据量比较大时，若动态扩容后，再将旧有数据重新计算搬移到新内存中，这时，插入数据会变得很慢，甚至无法接受。
解决办法：使用均摊思维，将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值后，申请新空间，但并不将老的数据版移到行散列表中。当有新数据插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，都重复上面的过程。经过多次插入操作之后，老散列表中的数据就一点点全部搬移到新散列表中。这样就没有集中一次性数据搬移，插入操作就都变得很快。

查询操作：对于查询操作，为了兼容新、老散列表中的数据，要用新散列函数从新散列表中查找，如果没有找到，再用旧散列函数去旧的散列表中查找。

时间复杂度：通均摊的方法，将一次性扩容的代价，均摊到多次插入操作中，避免了一次性扩容消耗过多的情况。这种实现方式，任何情况下，将插入一个数据的时间复杂度都是O(1)。

选择冲突解决方法

开发寻址法

优点：散列表中的数据都存储在数组中，可以有效地利用CPU缓存加速查询速度。而且，这种方法实现的散列表，数列化起来比较简单。

缺点：删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说冲突的代价更高。

总结：当数据量比较小、装载因子小的时候，适合采用开发寻址法。

链表法

优点：对内存的利用率要高。对装载因子的容忍度要高。

缺点：链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。链表中的结点是零散分布在内存中的，不是连续的，所以对于CPU缓存是不友好的。

优化：对于链表法稍加改造，可以实现一个更加高效的散列表。将链表法中的链表改造为其它高效的动态数据结构，比如跳表、红黑树。这样即便出现散列表，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是O(logn)。

总结：基于链表的散列冲突处理方法比较适合储存大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

工业级散列表分析

何为一个工业级的散列表？其具有那些特性？

支持快速的查找、插入、删除操作；

内存占用合理，不能浪费过多的内存空间；

性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。

如何实现这样一个散列表？

设计一个合适的散列函数；

设计一个装载因子阈值，并且设计动态扩容策略；

选择合适的散列冲突解决方法。

散列表与链表的配合使用

提出问题：散列表和链表是如何组合起来使用的，以及为什么散列表和链表会经常放在一块使用。

LRU缓存淘汰算法

一个缓存（cache)系统主要包含下面的几个操作：

往缓存中添加一个数据；

往缓存中删除一个数据；

在缓存中查找一个数据；

以上三个操作都涉及查找操作，如果单纯地采用链表的话，世界复杂度只能是O(n)。如果将散列表和链表两种数据结构组合使用，可以将这三个操作的时间复杂度降为O(1)。

用链表实现LRU缓存淘汰算法

维护一个按照访问时间从大到小有序的链表结构，其缓存大小有限。

当缓存空间不够，淘汰一个数据时，直接从链表头部删除一个结点。

当要存储某个数据时，先在链表中查找这个数据。如果没有找到，直接将数据放到链表的尾部；如果找到了，将它移动到链表的尾部。

查找需要遍历链表，时间复杂度很高，为O(n)。

用散列表和双向链表LRU缓存淘汰算法

使用散列表是为了让查找的时间复杂度降为O(1)，每次缓存一个数据，都要通过哈希函数计算其存储位置，若出现冲突用单向链表解决冲突；使用双向链表是为了将按照顺序缓存的数据从大到小缓存起来，双向为了更加方便的移动和删除数据节点。

对于使用的双向链表存储数据，其数据结构包括：存储数据的data、前驱指针prev、后继指针next，还有一个特殊字段hnext。
因为，设计的散列表是通过链表法解决冲突的，所以每个结点会在两条链中。一个是通过prev和next组成的双向链表，用来缓存数据；另一个链是散列表中的拉链，hnext指针是为了将结点串在散列表的拉链中。

时间复杂度分析：

查找数据，通过散列表查找数据的时间复杂度为O(1)。当找到数据之后，将其移动到双向链表的尾部。

删除数据，找到数据O(1)，在双向链表中，通过前驱指针O(1)时间复杂度获取前驱结点，所有在双向链表中，删除结点需要O(1)时间复杂度。

添加数据，先看数据存储是否已有，若有，将其移动到双向链表的尾部；若不在，还要看缓存是否已满，若满了，将双向链表头部的节点删除，然后再将数据放到链表的尾部；若没有满，就直接将数据放到链表尾部。整个操作过程其时间复杂度为O(1)。

散列表和链表一起使用的原因

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的，无法支持某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，需要将散列表中的数据拷贝到数组中，然后排序，再遍历。
因为散列表是动态数据结构，不停滴有数据的插入、删除，所以每当希望按照顺序遍历链表中的数据的时候，都需要排序，那效率势必会很低，为了解决这个问题，可以将散列表和链表（或者跳表）结合在一起使用。

哈希算法

哈希算法的应用非常多，常见的为：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。

哈希算法的定义与原理

将任意长度的二进制串映射为固定长度的二进制串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

优秀哈希算法要点

从哈希值不能反向推导出原始数据（哈希算法也叫作单向哈希算法）；

对输入数据非常敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也打不相同；

散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；

哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

安全加密

常用于加密的哈希算法是MD5(MD5 Message-Digest Algorithm，MD5消息摘要算法)和SHA(Secure Hash Algorithm，安全散列算法)。

没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也约长。

在实际开发中，要权衡破解难度和计算时间，来决定究竟使用哪种加密算法。

唯一标识

将大数据存储在计算机中的二进制码串，从前、中、后，各获取部分信息摘要，再组合后通过哈希算法（比如MD5），得到一个哈希字符串，用它作为唯一标识。

数据校验

对于BT下载，是通过哈希算法，对多个拆分的文件块分别取哈希值，并且保存在种子文件中。当文件块下载完成后，可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

散列函数

散列函数是设计一个散列表的关键，它直接决定了散列冲突的概率和散列表的性能。

负载均衡

提出问题：如何让同一个客户端，在一次会话中的所有请求都路由到同一个服务器上。

维护一张映射关系表，这种方法简单直观，但是存在弊端：

如果客户端很多，映射表可能会很大，比较浪费内存空间。

客户端上线、下线，服务器扩容、缩容都会导致映射表失效，这样维护映射表的成本就会很大。

借助哈希算法：通过哈希算法，对客户端IP地址或会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。

数据分片

将数据流大的数据，通过hash与n台机器计算取摸，这样将相同数据分片到不同的机器上进行出来，从而提高处理速度。

分布式存储

现在互联网面对的都是海量的数据，海量的用户。为了调高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。我们有海量的数据需要缓存，所以一个缓存机器肯定是不够的。于是，需要将数据分不到多台机器上。

假设我们有k个机器，数据的哈希值的范围是[0,MAX]。我们将整个范围划分成m个小区间（m远大于k）,每个机器负责m/k个小区间。当有新机器加入的时候，将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样既不用全部重新哈希、搬移数据，也保持了各个机器上数据量的均衡，这就是一致性哈希。

树

二叉树

树的基本概念

理解父节点、子节点、兄弟节点、根节点和叶子节点之间的关系。

节点的高度 = 节点到叶子节点的最长路径（从下到上，从0开始）。

节点的深度 = 根节点到这个节点所经历的变的个数（由上到下，从0开始）。

节点的层数 = 节点的深度 + 1。

树的高度 = 根节点的高度。

二叉树的定义

每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个节点，这样二叉树叫作满二叉树。

叶子节点都在最底层下两层，最后一层叶子节点都靠左排列，并且除了最后一层，其它层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

二叉树的存储

其有两种存储方式，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法：

链式存储法，每个节点有三个字段，其中一个存储数据，另外两个是执行左右子节点的指针。只要有根节点指针，就可以通过左右子节点的指针，把整棵树都串起来。

基于数组的顺序存储法，如果节点X存储在数组中下标为i的位置，下标为2i的位置存储的就是坐节点，下标为2i+1的位置存储的就是右子节点。反过来，下标为i/2的位置存储就是它的符节点。通过这种方式，只要知道更节点存储的位置，一般情况下，为了方便计算子节点，根节点会存储在下标为1的位置，这样就可以通过下标计算，把整个树串起来。
如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式，因为数组的存储方式不需要像链式存储那样，需要额外的左右子节点的指针。

二叉树的遍历

前序遍历、中序遍历和后序遍历，其中的前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

后续遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

实际上，二叉树的前、中、后序遍历就是一个递归的过程。

前序遍历的递推公式：
preOrder(r) = print r -> preOrder(r->left) -> PreOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r->left) -> print r -> inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->legt) -> postOrder(r->right) -> print r

三种遍历的伪代码：
void preOrder(Node* root){
    if(root == null) return;
    print root; //打印root节点
    preOrder(root->left);
    preOrder(root->right);
}

void preOrder(Node* root){
    if(root == null) return;
    preOrder(root->left);
    print root; //打印root节点
    preOrder(root->right);
}

void preOrder(Node* root){
    if(root == null) return;
    preOrder(root->left);
    preOrder(root->right);
    print root; //打印root节点
}
时间复杂度：每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数n成正比，所以二叉树遍历的实际复杂度是O(n)。

二叉查找树

定义

在树的任意一个节点，其左子树中的每个节点值，都要小于这个节点的值，而右子树节点值都大于这个节点的值。

特点

二叉查找树最大特点是，支持动态数据集合的快速插入、删除、查找操作。

查找操作

先取根节点，如果它等于要查找的数据，那就返回，如果要查找的数据比根节点小，那就在左子树中递归查找，如果要查找的数据比根节点的值大，那就在右子树中递归查找。

插入操作

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插入到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，若果插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；若果不为空，就再递归遍历左子树，查找插入位置。新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

删除操作

如果要删除的节点没有子节点，直接将父节点中，指向要删除节点的指针为NULL。
如果要删除的节点只有一个子节点，只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以。
如果要删除的节点有两个子节点，就比较复杂，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后删除掉这个最小节点，因为最小节点肯定没有左子节点，所以，应用上面两条规则来删除这个最小节点。

其它操作

中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n)，非常高效，因此二叉查找树也叫作二叉排序树。

支持重复数据的二叉查找树

方法一：二叉查找树中每一个节点不仅会存储一个数据，因此通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
方法二：每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点值，与要插入数据的值相同，就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当做大于这个节点的值来处理。

时间复杂度分析

对于退化成链表的二叉查找树，根节点的左右子树极度不平衡，所以查找的时间复杂度就变成O(n)。
最理想的情况是一棵完全二叉树或满二叉树，不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是O(height)。因此问题转化为如何求一棵包含n个节点的完全二叉树高度。
对于完全二叉树来说，最后一层的节点个数有点不遵守规律，它包含的节点个数在1到2^(L-1)个之间（假设最大层数是L）。如果把每一层的节点个数加起来就是总的节点个数n，其有如下关系：
```
n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)
```
借助等比数列的求和公式，L范围是【Log2(n+1), log2n +1】。完全二叉树的层数小于等于log2n + 1，也就是说，完全二叉树的高度小于等于log2n。

散列表与查找树

散列表的插入、删除、查找操作的时间复杂度可以做到常量级O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是O(longn)，相对散列表，好像并没有什么优势，那为什么还要用二叉查找树呢？

散列表中的数据是无序的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树，只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列。
散列表扩容耗时最多，而且当遇到散列冲突是，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉树的性能非常稳定，时间复杂稳定在O(logn)。
笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定比O(logn)快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
散列表的构造比二叉查找树要复杂，需要考虑的东西比较多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟和固定。
为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开发寻址法解决冲突的散列表，不然会浪费一定的存储空间。
综述：平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突，在实际开发中，需要结合具体的需求来选择使用哪一种。

参考链接：

转载请注明：HunterYuan的博客 » 数据结构与算法学习心得