首页  思维导图  详情

数据结构与算法

2023-12-26 18:51:24   44  举报





AI智能生成

数据结构与算法

数据结构

算法

数据结构图

排序算法

作者其他创作

大纲/内容

图

概念

图是由结点的有穷集合V和边的集合E组成。 在图结构中常常将结点称为顶点， 边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

术语

定点

边

边上带权重的为带权图

按照顶点方向划分

有向图

无向图

图的表示

邻接矩阵

无向图

有向图

缺点

占用空间太大

邻接表

图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点

逆邻接表

每一个顶点作为链表的头节点，后继节点所存储的是能够直接达到该顶点的相邻顶点

十字链表

邻接表+逆邻接表=十字链表

十字链表

邻接多重表

边集数组

遍历

深度优先遍历

利用栈实现

广度优先遍历

利用队列实现

应用

最小生成树

最短路路径

无权图

广度优先算法

带权图

迪杰斯特拉算法

多源最短路径

佛洛依德算法

拓扑排序

关键路径

树

概述

定义

1.每个节点有零个或多个子节点 2.没有父节点的节点称为根节点； 3.每一个非根节点有且只有一个父节点； 4.除了根节点外，每个子节点可以分为多个不相交的子树；

术语

节点的度

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

叶节点/终端节点

度为0的节点称为叶节点

非终端节点/分支节点

度不为0的节点

节点的层次

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

树的高度或深度

树中节点的最大层次

森林

由m（m>=0）棵互不相交的树的集合称为森林

遍历方式

前序遍历

父左右

中序遍历

左父右

后续遍历

左右父

层序遍历

从根节点开始，一层层往下

常见树

二叉树

概述

定义

1.每个节点最多有两个子树，节点的度最大为2； 2.左子树和右子树是有顺序的，顺序不能颠倒； 3.即使某个节点只有一个子树，也要区分左右节点

第i层至多有2^(i-1)个结点; 深度为k的二叉树至多有2^k-1个结点

特点

二叉树是数组和链表的折中方案， 增加、删除速度都快，并且对查询也有算法优化； 在动态处理大批量数据的时候很有用

满二叉树

一棵深度为k且有2^k-1（2的k次幂减1）个结点的二叉树称为满二叉树

完全二叉树

深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应

二叉排序树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： <ol><li>若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；</li><li>若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；</li><li>它的左、右子树也分别为二叉排序树。</li></ol>

存在的问题

对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度O(log2n)同时也由此而决定； 在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。 原因：由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。 这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度

自平衡二叉搜索树

AVL树

概述

它或者是一棵空树，或者是具有下列性质的二叉树： 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。 （注：平衡二叉树应该是一棵二叉排序树）

n个结点的AVL树最大深度约1.44log2n

查找、插入和删除在平均和最坏情况下都是O(logn)

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树； 这个方案很好的解决了二叉查找树退化成链表的问题， 把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。 但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多

AVL树的自平衡操作——旋转

左左/右右

单旋转

左左情况，单旋转自平衡处理

左右/右左

多旋转

子主题

2-3树

性质

1.满足AVL树的性质； 2.节点可以存放1个或2个元素； 3.每个节点有两个或三个子节点。

2-3树本质上也是一棵搜索树，和二叉搜索树的区别在于，2-3的节点可能存放 2 个元素，而且每个节点可能拥有 3 个子节点。

2-3树存在以下两种节点：2-节点（存在两个子节点）和3-节点（存在3个子节点）

红黑树 （RB-tree）

概述

自平衡二叉查找

可以在O(logn)时间内做查找，插入和删除

性质

在二叉查找树强制的一般要求以外增加： 1.节点是红色或黑色； 2.根是黑色； 3.所有叶子都是黑色（叶子是NIL节点）； 4.每个红色节点下有两个黑节点（每个叶子到根的路径上不能有两个连续的红色节点）； 5.从任意节点到每个叶子节点的简单路径上有相同节点的黑色节点。

SBT

Splay

Treap （树堆）

B树 （B-树）

概念

是一种平衡的多路查找树。B-树的阶是所有结点的孩子结点树的最大值。 B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个）， 数据库索引技术里大量使用者B树和B+树的数据结构

规则

一棵m阶B-树，或为空树，或为满足下列特性的m叉树： <ul><li>1）树中每个结点至多有m棵子树；</li><li>2）若根节点不是叶子节点，则至少有两棵子树；</li><li>3）除根之外的所有非终端结点至少有[m/2]（）向上取整）棵子树；</li><li>4）所有的非终端结点中包含下列信息数据：（n，A0，K1，A1，K2，A2，…，Kn，An），</li></ul>       n：为结点中的关键字树，        A：为指向子树根结点的指针，        K：为关键字，且Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn； <ul><li>5）所有的叶子结点都出现在同一层次上，并且不带信息</li></ul>   （可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）

多叉平衡查找树

参考

从B树、B+树、B*树谈到R 树

平衡二叉树、B树、B+树、B*树理解其中一种你就都明白了

B+树

概念

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找

规则

1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加； 2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样； 3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。 4）非叶子节点的子节点数=关键字数（来源百度百科） （根据各种资料这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)， 虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

分裂

当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针； 只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

应用场景

数据库索引

B*树

概念

规则

B*树是B+树的变种，相对于B+树他们的不同之处如下： （1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b*树的初始化个数为（cei(2/3*m)） （2）B+树节点满时就会分裂， 而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针）， 如果兄弟节点未满则向兄弟节点转移关键字， 如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

特点

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高， 而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

分裂

当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

B*树分配新结点的概率比B+树要低，空间使用率更高。

R树

哈夫曼树

概念

在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

结构

适用场景

典型运用

哈夫曼编码

trie 树（字典树）

前缀树，典型运用：关键字过滤

堆

定义

最大堆 （大根堆）

堆中某个节点总是不大于父节点

最小堆 （小根堆）

堆中某个节点总是不小于（最小堆）父节点

性质

堆的常用结构使用二叉树表示，不特指的话为一棵完全二叉树，通常不必用指针， 而是用数组来实现堆的存储堆： 数组起始单元为1，在数组中按照完全二叉树的层序存储， 根节点放在下标为1的位置中 对于下标为i的结点，其父结点的下标为i/2取整，反过来，i的左右结点分别是2i和2i+1

常用堆

二叉堆

斐波那契堆

注意

堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。

例如， 在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。 --唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

可以使用普通树来模拟堆，但是那对空间是极大的浪费。

并不是每一个最小堆都是一个有序数组！要将堆转换成有序数组，需要使用堆排序。

实现

堆仅仅使用一个数据来存储数组，且不使用指针

基本操作

shiftUp()

如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。 这样是这个节点在数组的位置上升

shiftDown()

如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”

常见应用

构建优先队列

因为堆有序，常用来做数组排序——堆排序

散列表

根据键值（key/value）进行访问的数据结构； 通过key/value来映射到集合中的元素，这样可以很快找到集合中的元素

高级数据结构

自顶向下伸展树

红黑树

确定性跳跃表

AA树

treap树

k-d树

配对堆

算法

排序

插入排序

直接插入排序

对于给定的一组记录，初始时假定第一个记录自成一个有序的序列，其余的记录为无序序列；

从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列为止。

希尔排序 （缩小增量排序）

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。 随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

交换排序

冒泡排序

快速排序

使用分治法策略

选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

选择排序

简单选择排序

对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮排序，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。

堆排序

将序列构造成一棵完全二叉树； 把这棵普通的完全二叉树改造成堆，便可获取最小值 ,输出最小值； 删除根结点，继续改造剩余树成堆，便可获取次小值 ,输出次小值； 重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序。

归并排序

是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之) 递归深度为log2n

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

基数排序

(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中 （比如53,个位为3，则放入3号桶中） (2)收集，再将放置在0~9号桶中的数据按顺序放到数组中

不从最高位开始排序的原因，主要是出于空间的考虑， 因为如果按照最高位开始排序，则之后的地位都需要创建一个完整的基数排序空间，空间占用量成指数增长

拓扑排序

将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

查找

概念

线性表查找

顺序查找

二分查找

分块查找

树形查找