数据结构与算法学习心得


前言

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


基础知识

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

复杂度分析

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

大O复杂度

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

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

注释:

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

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

时间复杂度分析
  1. 只关注循环次数最多的一段代码。由于大O表示法只是表示一种变化趋势,因此会忽略掉公式中的常量、低级、系数。
  2. 将所有复杂度相加,总复杂度等于量级最大的那段代码复杂度。
  3. 对于嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
  4. 对于多规模要求多个规模复杂度之和。
常见时间复杂度分析
以下将列举几种常见时间复杂度量级,按数量级递增
  • 常量阶:O(1)
  • 对数阶:O(logn)
  • 线性阶:O(n)
  • 线性对数阶:O(nlongn)
  • 平方阶:O(n^2)、立方阶阶O(n^3)…K次方阶O(n^k)
  • 指数阶:O(2^n)
  • 阶乘阶:O(n!)
常见的复杂度级别

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

  1. O(1):只要代码的时间复杂度不随n的增长而增长,这样代码的时间复杂度表示常量级。
  2. 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是一个常量,忽略此系数。
  3. O(m+n):对于无法评估的m和n两个数据规模,要用此方法表示。
空间复杂度分析

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


常见数据结构

数组

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

改善数组低效的“插入”和“删除”
  • 当数组中存储的数据没有任何规律,数组只是当做一个存储数据的集合,侧可以直接将数组插入第K个位置,为了避免大规模数据搬移,可以将原来k位置的数据摆一道数组元素的最后。
  • 在默写场景下,并非要数组中数据连续性,这是可以考虑将多次删除操作集中在一起执行,从而每次删除操作并不是真正的搬移数据,而是记录数据已经被删除,当数组没有更大空间存储数据时,才触发一次真正的删除操作,这样可以大大减少删除操作导致的数据搬移。
  • 总结,不要去死记硬背某个数据结构或者算法,要学习它背后的思想和处理技巧,这些东西才是最有价值的。
用数组比高级数组更合适场景
  1. Java ArrayList无法存储基本类型,例如int、long,需要封装为Integer、Long类型,而Autoboxing、Unboxing则有一定的性能消耗,若是特别关注性能,或是希望使用基本类型,就可以选用数组。
  2. 数组大小事先已知,并且对数组的操作非常简单,用不到ArrayList提供的大部分用法,也可以直接使用数组。
  3. 多维数组用数组更加直观。
数组寻址公式
  • 一维数组寻址公式:

    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个问题:

  1. 如果链表为空时,代码是否能正常工作?
  2. 如果链表只包含一个节点时,代码是否能正常工作?
  3. 如果链表只包含两个节点时,代码是否能正常工作?
  4. 代码逻辑在处理头尾节点时是否能正常工作?
举例画图,辅助思考

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


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

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

什么场景下使用栈

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

栈复杂度

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


队列

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

队列应用场景

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

阻塞队列

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

并发队列

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

队列应用举例

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

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

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


核心算法

递归

什么是递归
  1. 递归是一种非常高效、简洁的编码技巧、一种应用非常广泛的算法,比如DFS深度优先搜索、前中后序二叉树遍历等。
  2. 方法或函数调用自身的方式称为递归,调用称为递,返回称为归。
  3. 基本上,所有的递归问题都可以用递推公式来表示,比如:
    • f(n) = f(n-1) + 1
    • f(n) = f(n-1) + f(n-2)
    • f(n) = n*f(n-1)
递归优缺点
  • 优点:代码的表达力很强,简洁。
  • 缺点:空间复杂度高、有栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。
什么样的问题采用递归解决

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

  1. 问题的解可以分解为几个子问题的解。
  2. 问题和分解后的子问题,除了数据规模不同,求解思路完全一样。
  3. 存在递归终止条件。
如何实现递归
  1. 递归代码编写
    写递归代码的关键就是找到如何将大问题分解为小问题的规则,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件转化为代码。
  2. 递归代码理解
    对于递归代码,若试图想清楚整个递和归的过程,实际上是进入一个思维误区,而具体做法为,如果一个问题A可以分解为若干个子问题B、C、D,可以假设子问题B、C、D已经解决。而且,只需要思考问题A和子问题B、C、D两层之间的关系即可,不需要一层层往下思考子问题与子子问题,子子问题与子子子问题之间的关系。屏蔽掉递归细节,这样理解起来就简单多了。
    因此,理解递归代码,就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。
递归常见问题及解决方案
  • 警惕堆栈溢出:可以声明一个全局变量来控制递归的深度,从而避免堆栈溢出。
  • 警惕重复计算:通过某种数据结构来保存已求解过的值,例如hash,从而避免重复计算。
将递归转为非递归

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


排序

经典排序

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

  • 冒泡排序、插入排序、选择排序: 时间复杂度为O(n^2),基于比较排序。
  • 快速排序、归并排序: 时间复杂度为O(nlogn),基于比较排序。
  • 计数排序、基数排序、通排序: 时间复杂度为O(n),不基于比较排序。
如何分析一个排序算法
  • 排序算法的执行效率。
    1. 最好情况、最坏情况、平均情况时间复杂度。有序度不同的数据,对于排序的执行时间肯定是有影响的,因此要知道排序算法在不同数据下的性能表现。
      2,时间复杂度的系数、常数、低阶。从实际软件开发中考虑,基本排序都是规模比较小的数据。
    2. 比较次数和交换(或移动)次数。以及比较的排序算法,会涉及两种操作,比较和交换或移动,分析执行效率时,应当考虑。
  • 排序算法的内存消耗。
    1. 原地排序算法,就是特质空间复杂度是O(1)的排序算法,即不用耗费额外的内存进行存储。
  • 排序算法的稳定性。
    1. 稳定性,指待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
冒泡排序
冒泡排序执行过程

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

冒泡优化方式

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

冒泡分析
  1. 是原地排序算法吗?
    冒泡过程只涉及相邻数据的交互操作,没有申请格外的临时空间,空间复杂度为O(1),因此是原地排序算法。
  2. 是稳定的排序算法吗?
    只有交互才改变两个元素的前后顺序,当相等的时候,不做交互,相同大小的数据在排序前后不会改变顺序,因此是稳定的排序算法。
  3. 时间复杂度是多少?
    • 最好时间复杂度:顺序排列,只需要进行一次冒泡操作,就可以结束,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)。
插入排序
核心思想

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

插入排序执行过程

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

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

插入排序分析
  1. 插入排序是原地排序算法?
    插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是O(1),因此是一个原地排序算法。
  2. 插入排序是稳定的排序算法?
    对于值相同的元素,可以选择将后面出现的元素,插入到前面出现元素的后面,从而保持书序不变,因此插入排序是稳定的排序算法。
  3. 插入排序时间复杂度?
    • 最好情况: 要排序的数据有序,此时不需要搬移任何数据,每次只需要比较一个数据就能确定插入的位置,这时最好时间复杂度为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 不用再继续分解    
归并排序性能分析
  1. 归并排序是稳定排序算法?
    归并排序稳不稳定关键要看merge()函数,也就是两个有序子数组合并成一个有序数组那部分代码,在合并的过程中,如果A[p…q]和A[q+1…r]之间有值相同的元素,先把A[p…q]中的元素放入tmp数组。这样就保证了值相同的元素,在合并前后的先后顺序不变。所以,归并排序是一个稳定排序算法。
  1. 归并排序时间复杂度?
    • 对于递归求解的问题可以写成递推公式,同时递归代码的时间复杂度也可以写成递推公式。
    • 对于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)。
  2. 归并排序的空间复杂度?
    递归代码的空间复杂度并不像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,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)的值表示经过散列函数计算得到的散列值
  • 如何构造散列函数:
    1. 散列函数计算得到的散列值是一个非负整数;
    2. 如果key1=key2,那hash(key1) == hash(key2);
    3. 如果key1!=key2,那hash(key1) != hash(key2);
  • 关于上述第三点,这个要求看起来比较合理,但是在真实情况下,要想找到一个不同的key对应的散列值都不一样的散列函数,几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法,也无法完全避免这种散列冲突,而且,因为数组的存储空间有限,也会加大散列冲突的概率。
散列冲突

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

开放寻址法

  • 开放寻址的核心思想是,如果出现了散列冲突,就重新探测一个空闲位置,将其插入。
    1. 线性探测:Linear Probing 当往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。
      在散列表中查找元素的过程有点类似插入过程,通过散列函数求出要查找元素的键值对应的散列值,然后比较数组下标为散列值的元素和要查找的元素。如果相等,则说明就是我们要找的元素;否则就顺序依次查找。如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中。
      使用线性探测法解决冲突的散列表,删除操作稍微有些特别,因为不能单纯地把删除的元素设置为空,因为在查找的时候,一旦我们通过线性探测方法,找到一个空闲位置,就可以认定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在,解决办法为:将删除的元素,特殊标记为deleted。当线性探测查找的时候,遇到标记为deleted的空间,并不停下来,而是继续往下探测。
      线性探测存在的最大问题:当散列表中插入的数据越来越多时,散列冲突发送的可能性就会越来越大,空闲位置会越来越少,线性探测的时间就会越来越久。极端情况下,可能需要探测整个链表,所以最坏情况下的时间复杂度为O(n)。同理,在删除和查找时,也有可能会线性探测整张散列表,才能找到要查找或删除的数据。
    2. 二次探测:(Quadratic probing)
      所谓二次探测,跟线性探测很像,线性探测每次探测的步长是1,那它探测的下标序列就是hash(key)+0、hash(key)+1、hash(key)+2…而二次探测探测的步长就变成了原来的“二次方”,其下标探测为hash(key)+0、hash(key)+1^2、hash(key)+2^2…。
    3. 双重散列:(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下载,是通过哈希算法,对多个拆分的文件块分别取哈希值,并且保存在种子文件中。当文件块下载完成后,可以通过相同的哈希算法,对下载好的文件块逐一求哈希值,然后跟种子文件中保存的哈希值比对。如果不同,说明这个文件块不完整或者被篡改了,需要再重新从其他宿主机器上下载这个文件块。

散列函数

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

负载均衡
  • 提出问题:如何让同一个客户端,在一次会话中的所有请求都路由到同一个服务器上。
  • 维护一张映射关系表,这种方法简单直观,但是存在弊端:
    1. 如果客户端很多,映射表可能会很大,比较浪费内存空间。
    2. 客户端上线、下线,服务器扩容、缩容都会导致映射表失效,这样维护映射表的成本就会很大。
  • 借助哈希算法:通过哈希算法,对客户端IP地址或会话ID计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。
数据分片

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

分布式存储
  • 现在互联网面对的都是海量的数据,海量的用户。为了调高数据的读取、写入能力,一般都采用分布式的方式来存储数据,比如分布式缓存。我们有海量的数据需要缓存,所以一个缓存机器肯定是不够的。于是,需要将数据分不到多台机器上。
  • 假设我们有k个机器,数据的哈希值的范围是[0,MAX]。我们将整个范围划分成m个小区间(m远大于k),每个机器负责m/k个小区间。当有新机器加入的时候,将某几个小区间的数据,从原来的机器中搬移到新的机器中。这样既不用全部重新哈希、搬移数据,也保持了各个机器上数据量的均衡,这就是一致性哈希。


二叉树
树的基本概念
  • 理解父节点、子节点、兄弟节点、根节点和叶子节点之间的关系。
  • 节点的高度 = 节点到叶子节点的最长路径(从下到上,从0开始)。
  • 节点的深度 = 根节点到这个节点所经历的变的个数(由上到下,从0开始)。
  • 节点的层数 = 节点的深度 + 1。
  • 树的高度 = 根节点的高度。
二叉树的定义
  • 每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只有左子节点,有的节点只有右子节点。
  • 叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个节点,这样二叉树叫作满二叉树
  • 叶子节点都在最底层下两层,最后一层叶子节点都靠左排列,并且除了最后一层,其它层的节点个数都要达到最大,这种二叉树叫作完全二叉树
二叉树的存储

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

  1. 链式存储法,每个节点有三个字段,其中一个存储数据,另外两个是执行左右子节点的指针。只要有根节点指针,就可以通过左右子节点的指针,把整棵树都串起来。
  2. 基于数组的顺序存储法,如果节点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)。

二叉查找树
定义

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

特点

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

查找操作

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

插入操作

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

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

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

支持重复数据的二叉查找树
  1. 方法一:二叉查找树中每一个节点不仅会存储一个数据,因此通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上。
  2. 方法二:每个节点仍然只存储一个数据。在查找插入位置的过程中,如果碰到一个节点值,与要插入数据的值相同,就将这个要插入的数据放到这个节点的右子树,也就是说,把这个新插入的数据当做大于这个节点的值来处理。
时间复杂度分析
  • 对于退化成链表的二叉查找树,根节点的左右子树极度不平衡,所以查找的时间复杂度就变成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),相对散列表,好像并没有什么优势,那为什么还要用二叉查找树呢?

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


参考链接:


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

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦