【数据结构】零碎知识点(易忘 / 易错)总结回顾

一、数据结构的概念

数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。


二、算法

算法(Algorithm)就是定义良好的计算过程,它取一个或一组的值为输入,并产生出一个或一组值作为输出。算法就是一系列的计算步骤,用来将输入数据转化成输出结果。


1、算法的复杂度

衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。

  • 时间复杂度:一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。时间复杂度一般看最坏情况。
  • 空间复杂度:是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度算的是变量的个数。

函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。


三、顺序表&链表(重点)

1、线性表

  • 线性表(linear list)是 n 个具有相同特性的数据元素的有限序列。
  • 常见的线性表有:顺序表、链表、栈、队列、字符串...
  • 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。

2、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。

静态顺序表只适用于确定知道需要存多少数据的场景。


(1)缺点

  • 中间 / 头部的插入删除,时间复杂度为 O(N)。
  • 增容需要申请新空间,增容一般是呈 2 倍的增长。拷贝数据,释放旧空间,会有不小的消耗。
  • 增容一般是一次增长 2 倍,一定会造成空间浪费。
    例如当前的容量为 100,满了以后增容到 200,此时再继续插入 5 个数据,后面不再插入,那么就浪费了 95 个数据空间。

(2)越界

  • 越界读(读了不属于自己的数据),一般是检查不出来的,一般不会造成内存奔溃。
  • 越界写(缓冲区溢出),如果是修改到标志位才会被检查出来,会造成数据破坏,严重会造成内存奔溃。

3、链表

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。


(1)分类

A. 单向 / 双向


B. 带头 / 不带头


C. 循环 / 非循环


D. 无头单向非循环(常用)

结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。

如果用一级指针,则只能通过指针修改指针所指内容,却无法修改指针的值,也就是指针所指的内存块。所以创建链表和销毁链表需要二级指针或者一级指针引用。plist 是指向第一个节点的指针,想要在函数中改变 plist 的值(指向),必须要把 plist 指针的地址作为实参传过去,形参用二级指针接收,这样在函数中对二级指针解引用得到 plist 的值,就可以改变 plist 的值(指向)了

单链表在 pos 位置之后插入 x,为什么不在 pos 位置之前插入呢?

单链表不适合在 pos 位置之前插入元素,因为需要遍历链表找到 pos 位置的前一个节点,时间复杂度为 O(N)。

单链表更适合在 pos 位置之后插入,如果在后面插入,只需要知道 pos 位置即可。

C++ 官方库里面的单链表也是在之后插入。

单链表删除指定 pos 位置之后的结点,为什么不删除 pos 位置的结点呢?

删除 pos 位置同样需要传入单链表的二级指针。

因为需要遍历链表找到 pos 位置的前一个节点,以改变其指向,时间复杂度大。


E. 带头双向循环(常用)

  • 结构最复杂,一般用在单独存储数据。
  • 循环链表可以用来解决约瑟夫环问题。

4、顺序表和链表的区别

栈&队列(重点)

    • 栈是一种特殊的线性表。
    • 进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。
    • 栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
  • 队列
    • 队列可以用数组和链表的结构实现,使用链表的结构实现更优一些。如果使用数组删除队头数据,挪动数据效率为 O(N)。选择用单向链表来完成队列的实现更好,头删和尾插的效率都很高,而双向链表在这里发挥不出很大的作用。
    • 循环队列
      • 生产者消费者模型就会用到循环队列
      • 环形队列可以使用数组实现(推荐),也可以使用循环链表实现
        • front 指向数组第一个元素,初始值 front=0
        • rear 指向队列的最后一个元素后一个元素,初始值 rear=0
      • 空的循环队列:front == rear

      • 满的循环队列:(rear+1) % N == front(当循环队列中只剩下一个空存储单元,则表示队列已满,此时循环队列最多只能有 N-1 个队列元素)

队列内有效长度为:(rear - front + N) % N
这里加上数组长度起到类似绝对值的作用


四、树&二叉树(重点)

1、树

(1)结构

树是一种非线性的数据结构,它是由 n(n>=0)个有限结点组成一个具有层次关系的集合

子树之间不能有交集,否则就不是树形结构

每棵子树的根结点有且只有一个前驱

树是递归定义的


(2)相关概念

节点的度:一个节点含有的子树的个数称为该节点的度。

  • A 的度为 6

叶节点或终端节点:度为 0 的节点称为叶节点。

  • B 、C、H、I、P、Q、K... 节点为叶节点

非终端节点或分支节点:度不为 0 的节点。

  • D、E、F、G... 等节点为分支节点

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点。

  • A 是 B 的父节点

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点。

  • B 是 A 的孩子节点

兄弟节点:具有相同父节点的节点互称为兄弟节点。

  • B、C 是兄弟节点

树的度:一棵树中,最大的节点的度称为树的度。

  • 树的度为 6

节点的层次:从根开始定义起,根为第 1 层,根的子节点为第 2 层,以此类推。

树的高度或深度:树中节点的最大层次。

  • 树的高度为 4

堂兄弟节点:双亲在同一层的节点互为堂兄弟。

  • H、I 互为兄弟节点

节点的祖先:从根到该节点所经分支上的所有节点。

  • A 是所有节点的祖先

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

  • 所有节点都是 A 的子孙

森林:由 m(m>0)棵互不相交的树的集合称为森林。


2、二叉树

(1)概念

二叉树要么为空,要么就是由一个根节点加上两棵别称为左子树和右子树的二叉树组成

二叉树不存在度大于 2 的结点

二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树


(2)特殊的二叉树

满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,那么这个二叉树就是满二叉树

  • 如果一个二叉树的层数为 K,且结点总数是 2^K-1,那么它就是满二叉树

完全二叉树:对于深度为 K 且有 n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1~n 的结点一一对应时,称之为完全二叉树

  • 是效率很高的数据结构

满二叉树是一种特殊的完全二叉树


(3)二叉树的性质

若规定根节点的层数为 1,则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点

若规定根节点的层数为 1,则深度为 h 的二叉树的最大结点数是 2^h-1

任何一棵二叉树,如果度为 0 其叶结点个数为 n,度为 2 的分支结点个数为 m,则有 n=m+1

若规定根节点的层数为 1,具有 n 个结点的满二叉树的深度:h= log(n+1)

对于具有 n 个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号,则对于序号为 i 的结点

  1. 若 i>0,i 位置节点的双亲序号:(i-1)/2。i=0,i 为根节点编号,无双亲节点。
  2. 若 2i+1<n,左孩子序号:2i+1,2i+1>=n 否则无左孩子
  3. 若 2i+2<n,右孩子序号:2i+2,2i+2>=n 否则无右孩子

(4)二叉树的存储结构

A. 顺序结构

普通的二叉树不适合用数组来存储,因为可能会存在大量的空间浪费,而完全二叉树更适合使用顺序结构存储。通常把堆用顺序结构的数组来存储。

  • 这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段

二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树


B. 链式结构
  • 二叉树的链式存储结构:用链表来表示一棵二叉树,即用链来指示元素的逻辑关系
  • 链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址
  • 链式结构又分为二叉链和三叉链

(5)堆

A. 堆的概念和结构

堆(Heap)是计算机科学中一类特殊的数据结构的统称

堆通常是一个可以被看作一棵完全二叉树的数组对象

堆是非线性数据结构

最值总在 0 号位。堆中某个节点的值总是不大于或不小于其父节点的值

TopK 问题:在一堆数据里面找到前 K 个最大 / 最小的数

  • 1、用数据集合中前 K 个元素来建堆
    • 找前 K 个最大的元素(降序),则建小堆
      • 小根堆:根结点最小的堆,树中所有父亲都小于或等于孩子
    • 找前 K 个最小的元素(升序),则建大堆
      • 大根堆:根结点最大的堆,树中所有父亲都大于或等于孩子
  • 2、用剩余的 N-K 个元素依次与堆顶元素来比较,不满足则替换堆顶元素。将剩余 N-K 个元素依次与堆顶元素比完之后,堆中剩余的 K 个元素就是所求的前 K 个最小 / 最大的元素

使用堆排序效率也更高

使用堆排序,一般都使用最大堆


B. 堆的实现

堆的创建

a. 常用方式:堆向下调整算法

前提:左右子树必须是一个堆(包括大堆和小堆)才能调整

当根节点左右子树不是堆,怎么调整呢?

从最后一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆

为什么要倒着调整呢?

因为这样可以把最后一个非叶子节点的子树的左右子树看成是一个 (大 / 小) 堆,满足向下调整的前提条件,此时才能使用向下调整算法

建堆的时间复杂度为:O(N)


b. 扩展:堆向上调整算法

从上到下,从第一个节点(根节点)的左孩子开始,依次遍历完所有节点,分别对每个节点进行向上调整,一直到最后一个节点,就可以建成一个 (大 / 小) 堆

把数组中的第一个元素看作是一个堆,剩余的元素依次插入到这个堆中,这跟堆的插入接口原理相同,就是向上调整

建堆的时间复杂度为 O(nlog₂n)

使用向上调整算法建堆需要进行多次调整操作,而使用向下调整算法只需要进行一次调整操作。向下调整算法也更为直观,容易理解和实现,一般会选择使用向下调整算法来创建堆


c. 堆排序

利用堆删除的思想来进行排序

  • 建堆和堆删除中都用到了向下调整 ,因此掌握了向下调整,就可以完成堆排序

升序 -- 建大堆 -- 每次选出一个最大的数放到最后

  • 首先对 N 个数建大堆。将最大的数(堆顶)和最后一个数交换,把最大的数放到最后。前面 N-1 个数的堆结构没有被破坏(最后一个数不看作在堆里面的),根节点的左右子树依然是大堆,所以进行一次向下调整成大堆即可选出第二大的数,放到倒数第二个位置,然后重复上述步骤。
  • 建堆时间复杂度为 O(N),向下调整时间复杂度为 O(log₂N),这里最多进行 N-2 次向下调整,所以堆排序时间复杂度为 O(Nlog₂N)
排升序,建小堆可以吗?

可以,但不推荐。

  • 首先对 N 个数建小堆,选出最小的数,接着对剩下的 N-1 个数建小堆,选出第二小的数,不断重复上述过程。
  • 建堆时间复杂度为 O(N),所以上述操作时间复杂度为 O(N²),且关系变得杂乱,尤其是当数据量大的时候,效率更低,同时堆的价值也没有被体现出来,还不如用直接排序。

降序 -- 建小堆 -- 每次选出一个最小的数放到最后

  • 首先对 N 个数建小堆。将最小的数(堆顶)和最后一个数交换,把最小的数放到最后。前面 N-1 个数的堆结构没有被破坏(最后一个数不看做堆里面的),根节点的左右子树依旧是小堆,所以进行一次向下调整成小堆即可选出第二小的数,放到倒数第二个位置,然后重复上述步骤。
  • 建堆时间复杂度为 O(N),向下调整时间复杂度为 O(log₂N),这里最多进行 N-2 次向下调整,所以堆排序时间复杂度为O(Nlog₂N)

d. 堆的插入

先插入一个 10 到数组的尾上,再进行 向上调整算法 ,直到满足堆


e. 堆的删除

删除堆是删除堆顶的数据 ,将堆顶的数据跟最后一个数据作交换,然后删除数组最后一个数据(尾删),再进行向下调整算法


(6)二叉树的链式结构

A. 二叉树的层序遍历

一般需要使用队列


(7)二叉搜索树(二叉排序树)

可以是一棵空树

它的左右子树也分别为二叉搜索树

对二叉搜索树进行中序遍历,正好是一个升序序列(左子树 --> 根 --> 右子树)

增删查的时间复杂度为 O(h),h 是树的高度,最坏情况是 h 是 N

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能

  • 最优情况:二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为 logN
  • 最差情况:二叉搜索树退化为单支树(或者类似单支),其平均比较次数为 N
    • 如果退化成单支树,二叉搜索树的性能就失去了。能否进行改进,不论按照什么次序插入关键码,二叉搜索树的性能都能达到最优?—— AVL 树和红黑树

A. 应用
a. K 模型(判断关键字在不在)

只有 key 作为关键码,结构中只需要存储 key 即可,关键码即为需要搜索到的值


b. KV 模型

每一个关键码 key 都有与之对应的值 Value,即 <Key, Value> 的键值对


B. AVL 树(高度平衡二叉搜索树)

向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过 1 (需要对树中的结点进行调整),即可降低树的高度(高度可保持在 O(log₂n)),从而减少平均搜索长度(时间复杂度 O(log₂n))

它的左右子树都是 AVL 树

左右子树高度之差(简称平衡因子)的绝对值不超过 1(-1/0/1)。更新以后,parent 的平衡因子可能有三种情况:0,正负 1, 正负 2

1、更新以后,parent 的平衡因子是 0(说明插入之前 parent 的平衡因子之前一定为 1/-1),说明父亲所在子树高度没变,此时满足 AVL 树的性质,插入成功,不需要继续往上更新

2、更新以后,parent 的平衡因子是 1/-1(说明插入之前 parent 的平衡因子一定为 0),说明父亲所在子树高度增加,需要继续往上更新(最坏情况:往上一直更新到根节点)

3、更新以后,parent 的平衡因子是 2/-2,说明父亲所在子树出现了不平衡,需要对其进行旋转处理


为什么左右子树高度差不规定成 0 呢?

因为在 2、4 等节点数的情况下,不可能做到左右高度相等的情况

AVL 树节点是一个三叉链结构,除了指向左右孩子的指针,还有一个指向其父亲的指针,数据域是键值对,即 pair 对象,还引入了平衡因子(用来判断是否需要进行平衡操作)


a. 旋转

旋转的本质:在遵循二叉搜索树的规则下,让左右均衡,降低整棵树的高度

  • 引发旋转的路径是直线就是单旋
  • 引发旋转的路径是折线就是双旋

新节点插入较高左子树的左侧 —— 左左:右单旋

parent 的平衡因子为 -2,parent 左孩子平衡因子为 -1。父亲左边高,右边低,所以要让父亲往右旋

观察发现:平衡因子都是负数,说明左边高,也说明了引发旋转的路径是一条直线,所以要右旋

操作:

1、让 subL 的右子树 subLR 成为 parent 的左子树(因为 subLR 的右子树根节点值 > 30,< 60)

2、让 parent 成为 subL 的右子树(因为 60 > 30)

3、让 subL 变成这个子树的根。这一步操作前需要先判断下:parent 是根节点,还是一个普通子树

  • 如果是根节点,旋转完成后,则更新 subL 为新的根节点
  • 如果是普通子树(可能是某个节点的左子树,也可能是右子树,这里作一个判断),然后更新 subL 为这个子树的根节点

4、根据树的结构,更新 parent 和 subL 的平衡因子为 0

在旋转过程中,更新双亲指针的指向,有几种情况需要考虑

  • 30 节点(subL)的右孩子(subLR)可能存在,也可能为空。当不为空时才更新 subL 右子树 subLR 的双亲指针指向
  • 60 可能是根节点,也可能是子树(旋转完成后,subL 的双亲节点可能是空,也可能是 parent 原先的父节点,要在更新 subL 的双亲指针前需要判断下。

新节点插入较高右子树的右侧 —— 右右:左单旋

parent 的平衡因子为 2,parent 左孩子平衡因子为 1。父亲右边高,左边低,所以要让父亲往左旋

观察发现:平衡因子都是正数,说明右边高,也说明了引发旋转的路径是一条直线,所以要左旋

操作:

1、让 subR 的左子树 subRL 成为 parent 的右子树(因为 subRL 的左子树根节点值 > 30,< 60)

2、让 parent 成为 subR 的左子树(因为 30 < 60)

3、让 subR 变成这个子树的根。这一步操作前需要先判断下 parent 是根节点,还是一个普通子树

  • 如果是根节点,旋转完成后,则更新 subR 为新的根节点
  • 如果是普通子树(可能是某个节点的左子树,也可能是右子树,这里作一个判断),然后更新 subR 为这个子树的根节点

4、根据树的结构,更新 parent 和 subR 的平衡因子为 0

在旋转过程中,更新双亲指针的指向,有几种情况需要考虑

  • subR 的左子树 subRL 可能存在,也可能为空
  • 旋转完成后,subR 的双亲节点可能是空,也可能是 parent 原先的父节点

新节点插入较高左子树的右侧 —— 左右:先左单旋再右单旋(左右双旋)

需要的是先对 parent 的左孩子进行一次左旋,再对 parent 进行一次右旋

parent 的平衡因子为 -2,parent 左孩子的平衡因子为 1

观察发现:平衡因子是一负一正,说明左孩子右边高,父亲左边高,也说明了引发旋转的路径是一条折线,所以要先对左孩子进行左旋操作,再对父亲进行右旋操作

插入新节点的位置不同,经过左右双旋后,得到树的结构也会有所不同,平衡因子也会有所不同,有 3 种情况

新节点插入到了 parent 左孩子的右子树的左边

新节点插入到了 parent 左孩子的右子树的右边

新节点就是 parent 左孩子的右孩子

节点 60 的左右子树被分走了,左子树最终成为了节点 30 的右子树,右子树最终成了节点 90 的左子树


新节点插入较高右子树的左侧 —— 右左:先右单旋再左单旋(右左双旋)

需要的是先对 parent 的右孩子进行一次右旋,再对 parent 进行一次左旋

parent 的平衡因子为 2, parent 右孩子平衡因子为 -1

观察发现:平衡因子是一正一负,说明右孩子左边高,父亲右边高,也说明了引发旋转的路径是一条折线,所以先对右孩子进行右旋操作,再对父亲进行左旋操作

插入新节点的位置不同,经过右左双旋后,得到树的结构也会有所不同,平衡因子也会有所不同,有 3 种情况

新节点插入到了 parent 右孩子的左子树的左边

新节点插入到了 parent 右孩子的左子树的右边

新节点就是 parent 右孩子的左孩子

节点 60 的左右子树被分走了,左子树 b 最终成了节点 30 的右子树,右子树 c 最终成了节点 90 的左子树


假如以 parent 为根的子树不平衡(parent 的平衡因子为 2/-2),则分情况考虑

1、parent 的平衡因子为 2,说明 parent 的右子树高,设 parent 的右子树的根为 subR

  • 当 subR 的平衡因子为 1 时,执行左单旋
  • 当 subR 的平衡因子为 -1 时,执行右左双旋

2、parent 的平衡因子为 -2,说明 parent 的左子树高,设 parent 的左子树的根为 subL

  • 当 subL 的平衡因子为 -1 时,执行右单旋
  • 当 subL 的平衡因子为 1 时,执行左右双旋

旋转完成后,原 parent 为根的子树个高度降低,已经平衡,不需要再向上更新


b. 验证
  • 验证其为二叉搜索树:如果中序遍历可得到一个有序的序列,就说明为二叉搜索树
  • 验证其为平衡树:每个节点子树高度差的绝对值不超过 1(注意节点中如果没有平衡因子),以及节点的平衡因子是否计算正确

如果要对 AVL 树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,最差的是在删除时有可能一直要让旋转持续到根的位置

  • 如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(不会改变),可以考虑 AVL 树。但如果一个结构经常修改,就不太适合

C. 红黑树

红黑树,是一种二叉搜索树,近似平衡(控制最长路径不超过最短路径的 2 倍,不包括 NIL),变了一种方式来控制树的平衡,相较于 AVL 树而言,舍弃平衡二叉树的严格平衡,换取节点插入时尽可能少的调整

  • 因为红黑树的旋转情况少于 AVL 树,使得红黑树整体性能略优于 AVL 树
  • 通过对任何一条从根到叶子的路径上各个结点着色(Red / Black)方式的限制,红黑树确保没有一条路径会比其他路径长出 2 倍,因而是接近平衡的
a. 性质
  • 每个结点不是红色就是黑色
  • 根节点是黑色的
  • 如果一个结点是红色的,则它的两个孩子结点是黑色的(红黑树里面没有连续的红色节点)
  • 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点 (即每条路径都有相同数量的黑色节点,路径是走到 NIL 空节点)
  • 每个 NIL 叶子结点都是黑色的(此处的叶子结点指的是空结点)

b. 结论推导

最长路径刚好是最短路径的 2 倍的原因

当某条路径最短时,这条路径必然都是由黑色结点构成的

当某条路径最长时,这条路径必然是由红色和黑色节点交替构成的

  • 又因为不能出现两个连续的红色节点且从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点,那么说明最长路径上黑节点的数目和最短路径上黑节点的数目是相等的
在节点的定义中,为什么要将节点的默认颜色给成红色的?
  1. 假如任意插入的节点是黑色节点,则连续插入两个黑色节点后,就不满足 “每条路径的黑色节点数量相等” 这个性质,肯定有一边的黑色节点多于另外一边
  2. 连续插入两个红色节点可能不满足 “树中不能出现两个连续的红色节点” 这个性质,但是因为连续两个红色节点可以根据红黑树的变换规则进行变色或者旋转的调整,以达到标准的红黑树

c. 结构

为了实现关联式容器简单,红黑树的实现中增加一个头结点。因为根节点必须为黑色,又为了与根节点进行区分,所以将头结点给成黑色,并且让头结点的 parent 域指向红黑树的根节点,_left 域指向红黑树中最小的节点,_right 域指向红黑树中最大的节点


d. 插入操作

当插入红色新节点 cur 后,如果父亲 p 存在且为红,说明破坏红黑树性质了,需要平衡化操作

记录 cur 的父亲 p 和祖父 g 的位置,然后判断父亲 p 的位置:

1、如果父亲 p 是祖父 g 的左孩子(说明叔叔 u 是祖父 g 的右孩子,先判断叔叔的状态)

如果叔叔 u 存在且为红,则直接先变色处理,然后再往上调整

1)先调整颜色:父亲 p 和叔叔 u 变黑,祖父 g 变红

2)再往上调整:原先祖父 g 当成新的 cur,判断新 cur 的父亲 p

  • 若父亲 p 不存在,说明调整到头了,停止调整,然后将根节点变黑
  • 若父亲 p 存在且为黑,没有破坏性质,停止调整
  • 若父亲 p 存在且为红,继续调整,要一直调整到根节点或者父亲 p 存在且为黑时,才停止调整

如果叔叔 u 不存在 / 叔叔 u 存在且为黑,此时先判断 cur 的位置

1)如果 cur 是父亲 p 的左孩子(此时 cur、p、g 是一条直线)

  • 进行右单旋 + 变色处理(父亲 p 变黑,祖父 g 变红)

2)如果 cur 是父亲 p 的右孩子(此时 cur、p、g 是一条折线)

  • 进行左右双旋 + 变色处理(cur 变黑,祖父 g 变红)

3)上述情况处理完成后,当前子树的根节点为黑 (p / cur),没有连续红节点了,则停止调整


2、如果父亲 p 是祖父 g 的右孩子(说明叔叔 u 是祖父 g 的左孩子,先判断叔叔的状态)

如果叔叔 u 存在且为红,则直接先变色处理,然后再往上调整

1)先调整颜色:父亲 p 和 叔叔 u 变黑,祖父 g 变红

2)再往上调整:原先祖父 g 当成新的 cur,判断新 cur 的父亲 p

  • 若父亲 p 不存在,说明调整到头了,停止调整,然后将根节点变黑
  • 若父亲 p 存在且为黑,没有破坏性质,停止调整
  • 若父亲 p 存在且为红,继续调整,要一直调整到根节点或者父亲 p 存在且为黑时,才停止调整

如果叔叔 u 不存在 / 叔叔 u 存在且为黑,此时先判断 cur 的位置

1)如果 cur 是父亲 p 的右孩子(此时 cur、p、g是一条直线)

  • 进行左单旋 + 变色处理(父亲 p 变黑,祖父 g 变红)

2)如果 cur 是父亲 p 的左孩子(此时 cur、p、g是一条折线)

  • 进行右左单旋 + 变色处理(cur 变黑,祖父 g 变红)

3)上述两种情况处理完成后,当前子树的根节点为黑 (p / cur),没有连续红节点了,则停止调整

停止调整是循环的出口,否则就要一直调整到根节点或者父亲 p 存在且为黑时


e. 验证

1、检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2、检测其是否满足红黑树的性质

  • 根节点是否为黑色
  • 是否存在连续红节点
  • 统计每条路径上的黑节点数是否相等

五、排序(重点)

1、排序的相关概念

  • 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变
  • 内部排序:数据元素全部放在内存中的排序
  • 外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序


2、插入排序

(1)直接插入排序(InsertSort)

  • 平均时间复杂度为:O(n²)(元素集合越接近有序,直接插入排序算法的时间效率越高)
  • 插入排序算法的运行并不需要额外的存储空间,所以空间复杂度:O(1),这是一个原地排序算法

对于值相同的元素,可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法


(2)希尔排序(ShellSort)(缩小增量排序)

先选定一个整数,把待排序文件中的所有记录分成若干个组,所有距离为 gap 的记录分在同一组内,并对每一组内的记录进行排序,然后重复上述分组和排序的工 作。当到达 gap=1 时,所有记录在统一组内排好序。

最初希尔提出的增量是 gap=n/2,每一次排序完让增量减少一半 gap/=2,直到 gap=1 时,排序相当于直接插入排序。

后来有人提出了 gap=(gap/3)+1,每次排序让增量成为原来的 1/3,+1 是防止 gap<=3 时 gap/=3 结果为 0 情况的发生,导致 gap 最后不为 1,无法完成插入排序

选择 gap=(gap/3)+1 更稳定,能够尽可能地减少比较和交换的次数,以提高排序的效率。通过采用这种递减的方式,可以更好地分组元素,使得在每一轮排序中能够更快地将较小的元素移动到前面。序列被划分为较小的子序列,并通过插入排序的方式对每个子序列进行排序。这样做的好处是在初始阶段,较大的元素可以更快地向后移动,从而减少了后续比较和交换的次数。

当 gap>1 时都是预排序,目的是让数组更接近于有序。当 gap==1 时,数组已经接近有序了,相当于直接插入,这样就会很快

  • 希尔排序是对直接插入排序的优化
  • 希尔排序在越大的数组上相较于直接插入排序更能发挥优势,因为步子迈的更大,减少插入排序的移动次数更多

希尔排序的时间复杂度并不好计算,因为 gap 的取值方法很多,官方给出的时间复杂度是 O(N^1.3)

  • 空间复杂度:O(1)
  • 稳定性:不稳定

2、选择排序

(1)直接选择排序(SelectSort)

选择排序的最好情况的时间复杂度为 n+(n-2)+(n-4)+...(优化后的做法:同时找 max 和 min)相当于 n²,最坏情况和平均情况时间复杂度都为 O(n²)

空间复杂度为 O(1) ,是一种原地排序算法

是一种不稳定的排序算法,比如:4,9,4,1,8,第一次找到最小元素 1 ,与第一个 4 交换位置,那第一个 4 和中间的 4 顺序就变了


(2)堆排序(HeapSort)

通过堆来进行选择数据

  • 时间复杂度:O(NlogN)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

3、交换排序

(1)冒泡排序(Bubble Sort)

一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作

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

最好情况下,要排序的数据已经是有序的了,只需要进行一次冒泡操作就可以结束 了,所以最好情况时间复杂度是 O(n)。而最坏的情况下,要排序的数据刚好是倒序排列的,需要进行 n 次冒泡操作,所以最坏情况时间复杂度为 O(n²)

冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以空间复杂度为 O(1) ,是一个原地排序算法

在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法

在相对有序的情况下,选择插入排序更好。比如 1 2 3 5 4 6 这个排序,冒泡排序需要 ((N-1)+(N-2)) 比较(因为冒泡排序排好后,还需要再排多一次,才能确定排好序了),插入排序需要 N 次比较。


(2)快速排序法(Quicksort)

分治思想:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右子序列重复该过程,直到所有元素都排列在相应位置上为止 。

快速排序是一种二叉树结构的交换排序方法

快排的处理过程是由上到下 的,先分区,然后再处理子问题

时间复杂度:O(NlogN),空间复杂度:O(logN)

快排在有序的情况下时间复杂度最坏:n+(n-1)+(n-2)+... 时间复杂度为 O(n²),空间复杂度为 O(n)。

快速排序优化:三数取中法

  • 基本思想:从待排序数组中随机选择三个元素(一般选取首、尾和正中三个数),并将它们按升序排列,然后选择中间位置的元素作为 mid
  • 三数取中法依然无法完全解决针对某种特殊序列(比如元素全部相同)复杂度最坏的情况
A. 将区间按照基准值划分为左右两半部分的常见方式有 3 种
1)hoare 版本

选出一个关键字 key,一般是头 / 尾。经过一次单趟后,key 放到了正确的位置,key 左边的值比 key 小,key 右边的值比 key 大。再让 key 的左边区间有序、key 的右边区间有序。

如何保证相遇位置的值小于 key ?

这个算法右边先走可以保证相遇位置小于 key。


2)挖坑法


3)前后指针版本

  • 稳定性:不稳定

当快速排序递归到较小区间时,可以切换到插入排序,这样可以减少递归调用的次数,降低开销,并利用插入排序的优势来提高整体性能


B. 快速排序非递归

递归在极端场景下,如果栈帧深度太深,栈空间不够用,会出现栈溢出

递归改成非递归一般有 2 种方法

  1. 直接改循环(简单)
  2. 借助数据结构栈模拟递归过程(复杂):快速排序的非递归遍历可以使用栈模拟二叉树的前序遍历的方式实现,也可以使用队列模拟二叉树的层序遍历的方式实现。

快排的非递归是在模拟递归的过程,所以时间复杂度并没有本质的变化,但可以减少栈空间的开销

快速排序整体的综合性能和使用场景都比较好,所以才敢叫快速排序


4、归并排序

(1)归并排序(MergeSort)

将已有序的子序列合并,得到完全有序的序列:先使每个子序列有序,再使子序列段间有序

执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最好 / 最坏 / 平均情况,时间复杂度都是 O(nlogn)

尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用,临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)

是一个稳定的排序算法


5、非比较排序

(1)计数排序(CountSort)

又称为鸽巢原理,是对哈希直接定址法的变形应用

A. 操作步骤

1、统计相同元素的出现次数

2、根据统计的结果将序列回收到原来的序列中

  • 时间复杂度:O(max(N,range))
  • 空间复杂度:O(range)
  • 稳定性:稳定

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/445166.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

二分图算法总结 C++实现

总体概念 染色法 基本思路步骤 将所有的边及其相接的边用邻接表存储起来&#xff1b;遍历所有的点&#xff0c;找到未上色的点&#xff1b;用BFS将该点及其相接的点迭代上色&#xff1b;在上述染色步骤中&#xff0c;如果相邻点的颜色相同则无法形成二分图&#xff1b; 题目…

数据结构:单链表OJ题

目录 相交链表解题思路代码 环形链表&#xff08;I&#xff09;解题思路代码 环形链表&#xff08;II&#xff09;解题思路代码 随机链表的复制&#xff08;深拷贝&#xff09;解题思路代码 相交链表 题目描述&#xff1a; 案例&#xff1a; 题目链接&#xff1a;https://l…

FunASR离线文件转写服务开发指南-debian-10.13

FunASR离线文件转写服务开发指南-debian-10.13 服务器环境 debian10.13 64位 第一步 配置静态网卡 auto eth0 iface eth0 inet static address 192.168.1.100 netmask 255.255.255.0 gateway 192.168.1.1 dns-nameservers 8.8.8.8 8.8.4.4/etc/init.d/networking restart第…

【JVM】JMM

文章目录 前置的硬件知识什么是JMMJMM的三大特性JMM中定义的原子操作happens-before先行发生原则 前置的硬件知识 硬件存储体系: 运行速度从上到下依次减慢. 由于CPU的计算速度远超与内存的处理速度,所以CPU不会直接从内存中读写,而是将内存中的变量拷贝一份副本放到CPU高速…

2022年下真题(案例分析)

一、数据流图 二、数据库设计 - ER图 三、面向对象设计 - 用例图、类图 四、算法

【人工智能】AI人工智能的重要组成部分,深入解析CNN与RNN两种神经网络的异同与应用场景和区别

文章目录 一、卷积神经网络&#xff08;CNN&#xff09;详解1. 特征与结构CNN的基本结构 2. 应用场景3. 代码示例 二、循环神经网络&#xff08;RNN&#xff09;详解1. 网络结构与特点RNN的基本结构 2. 应用场景3. 代码示例 三、CNN与RNN的异同点1. 相同点2. 不同点 四、CNN与R…

基于YOLOv8-deepsort算法的智能车辆目标检测车辆跟踪和车辆计数

关于深度实战社区 我们是一个深度学习领域的独立工作室。团队成员有&#xff1a;中科大硕士、纽约大学硕士、浙江大学硕士、华东理工博士等&#xff0c;曾在腾讯、百度、德勤等担任算法工程师/产品经理。全网20多万粉丝&#xff0c;拥有2篇国家级人工智能发明专利。 社区特色…

Vue使用@别名替换后端ip地址

1. 安装 types/node types/node 包允许您在TypeScript项目中使用Node.js的核心模块和API&#xff0c;并提供了对它们的类型检查和智能提示的支持。 npm install types/node --save-dev 比如安装之后&#xff0c;就可以导入nodejs的 path模块&#xff0c;在下面代码 import path…

闪电麦昆 语音控制齿轮行进轨迹,ESP32搭配语音控制板,串口通信,附视频演示地址

演示地址 https://www.bilibili.com/video/BV1cW421d79L/?vd_sourceb8515e53f6d4c564b541d98dcc9df990 语音控制板的配置 web展示页面 esp32 程序 #include <ESP8266WiFi.h> #include <ESP8266WebServer.h> #include <LittleFS.h> #include <WebSo…

STL之set、map的使用

STL之set、map 1. 序列式容器和关联式容器2. set系列的使⽤参考文档链接&#xff1a;2.1 set的介绍&#xff08;2&#xff09;set的增删查2.2 multiset的介绍 3 map3.1 参考文档3.2 map类的介绍3.3 pair类型介绍3.4 map的构造3.6 map的数据修改3.7 multimap和map的差异 1. 序列…

openpdf

1、简介 2、示例 2.1 引入依赖 <dependency><groupId>com.github.librepdf</groupId><artifactId>openpdf</artifactId><version>1.3.34</version></dependency><dependency><groupId>com.github.librepdf</…

python+yaml+pytest+allure接口自动化框架

建议想学自动化的同学&#xff0c;先花半个月一个月的时间&#xff0c;去b站极限学习一下有关python的基础内容&#xff0c;比如各种数据类型的特点&#xff0c;创建 转换等&#xff0c;还有面向对象的一些知识&#xff0c;否则直接看自动化框架&#xff0c;很难看懂理解&#…

根据请求错误的状态码判断代理配置问题

SafeLine&#xff0c;中文名 “雷池”&#xff0c;是一款简单好用, 效果突出的 Web 应用防火墙(WAF)&#xff0c;可以保护 Web 服务不受黑客攻击。 雷池通过过滤和监控 Web 应用与互联网之间的 HTTP 流量来保护 Web 服务。可以保护 Web 服务免受 SQL 注入、XSS、 代码注入、命…

2024顶级一区idea:多模态图像融合!

在图像处理的前沿领域&#xff0c;多模态图像融合技术正成为研究的热点&#xff0c;它通过整合来自不同来源的图像数据&#xff0c;为我们提供了更丰富的信息维度&#xff0c;从而显著提升图像处理的精确度和效率。 这项技术的核心优势在于能够捕捉并融合各种图像数据中的互补…

3D渲图软件推荐:打造高质量渲染效果

在现代设计领域&#xff0c;3D渲图已经成为展示设计方案和产品外观的重要手段。无论是建筑设计、产品设计还是影视动画&#xff0c;都需要借助专业的3D渲染图软件来实现逼真的视觉效果。 本文将为您介绍几款备受好评的3D渲染图软件&#xff0c;帮助您在项目中选择合适的工具。…

户外防火值守:太阳能语音监控杆的参数及技术特点

随着假期旅游的热潮日渐高涨&#xff0c;我们游览各大景区、公园或森林区域时&#xff0c;经常会与各种智能设备不期而遇。这些高科技产品不仅提升了旅游体验&#xff0c;更在无形中保障了游客的安全与景区的环境保护。在我最近的旅行经历中&#xff0c;尤其是在深圳大鹏旅游景…

开放式蓝牙耳机排行榜10强?分享值得安利的开放式耳机

​开放式耳机目前非常流行&#xff0c;它们以时尚、美观和舒适著称&#xff0c;迅速赢得了众多用户的喜爱&#xff0c;成为了耳机市场的新宠。与传统的入耳式耳机相比&#xff0c;开放式耳机佩戴更稳固&#xff0c;对耳朵也更为温和。尽管有些人认为它们价格不菲&#xff0c;甚…

项目_C_Ncurses_Flappy bird小游戏

Ncurses库 概述 什么是Ncurses库&#xff1a; Ncurses是一个管理应用程序在字符终端显示的函数库&#xff0c;库中提供了创建窗口界面、移动光标、产生颜色、处理键盘按键等功能。 安装Ncurses库&#xff1a; sudo apt-get install libncurses5-dev 头文件与编译&#xf…

Springboot自定义starter注入到第三方项目IOC容器里

一 Bean扫描 Springboot项目&#xff0c;我们不加ComponentScan注解&#xff0c;但是也能扫描到Controller、Service标记的类&#xff0c;为什么呢&#xff1f;关键在于启动类的SpringBootApplication注解&#xff0c;该注解由以下三个注解组成&#xff1a; SpringBootConfig…

关于BSV区块链覆盖网络的常见问题解答(下篇)

​​发表时间&#xff1a;2024年9月20日 在BSV区块链上的覆盖网络服务为寻求可扩展、安全、高效交易处理解决方案的开发者和企业家开辟了新的视野。 作为开创性的曼达拉升级的一部分&#xff0c;覆盖网络服务提供了一个强大的框架&#xff0c;用于管理特定类型的交易和数据访问…