首页  思维导图  详情

数据结构与算法汇总

2022-05-12 15:25:15   0  举报





AI智能生成

数据结构与算法，你掌握了吗？

算法

数据结构

算法与程序

数据结构与算法

作者其他创作

大纲/内容

算法简介、概述、绪论、导论

什么是算法？算法定义

在有限步骤内解决数学问题的程序

为解决某项工作或某个问题，所需要有限数目的机械性或重复性指令与计算步骤

问题求解步骤描述

对特定问题求解步骤的一种描述

算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，在有限时间内被机械的求解。

算法是对特定问题求解步骤的一种描述

图解算法和算法评价

综合题

例1

答1

答2

例2

答1

答2

答3

答4

选择题

例1

答

例2

答

例3

答

例4

答

例5

答

例6

答

例7

答

例8

答

例9

答

例10

答

例11

答

例12

答

例13

答

导图

算法分析
算法效率的度量

算法分析目的

提高算法效率

算法的设计原则
算法的设计要求、评定

正确性

正确性:算法至少具备输入、输出和加工处理的无歧义性，能够正确的反应问题的需求并正确得到答案。

算法没有于法的错误。

算法对于一个合法的输入必须有一个满足要求的输出结果。

对于不合法的输入要提供满足规格的输入要求。

算法对于故意刁难的输入测试都有满足要求的输出结果。

对于合法的输入产生符合要求的输出；

易读性、可读性

可读性

算法应该易读、便于交流，这也是保证算法正确性的前提；

健壮性

健壮性：当输入数据不合理时，也能做出相应的处理，而不产生异常、崩溃等莫名其妙的结果。

当输入非法时，算法还能做出适当的反应而不会崩溃

时空性

时间效率高和存储量低

时间复杂度

时间复杂度和空间复杂度

空间复杂度

算法效率的度量方法

事后统计法（不推荐）

事先分析法

时间复杂度

推导大O的攻略

忽略常数的相加。

只保留最高项。

去掉与最高项相乘的常数。

常见的时间复杂度

最坏情况：就是一个算法的最长时间。也就是算法最长时间的保证。

平均情况：就是期望的运行时间

公式：T（n）=O(f(n))

空间和时间是可以转换的。

空间复杂度

公式：S(n）=O(f(n));

影响算法效率因素

算法采用的方法和策略。

编译产生的代码质量。

问题的输入规模。

机器执行指令的速度。

复杂度计算、复杂度分析

时间复杂度

算法运行时需要的总步数

如何确定算法的计算量

默认以赋值语句-->标准操作

执行多少次标准操作-->次数-->算法的计算量。

所有输入下的计算量的最大值-->算法的最坏情况时间复杂度

加权平均值-->平均情况时间复杂度

时间复杂度按数量级

常数O(1),对数阶O(log2n),线性阶O(n),线性对数阶 O(nlog2n),平方阶O(n2),多项式阶O(nC),指数阶O(Cn)

规则

加法规则

乘法规则

T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

T(n)=T1(n)xT2(n)=O(f(n))xO(g(n))=O(f(n)xg(n))

常见渐近时间复杂度

O(1)<O(log2(n))<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

时间复杂度

最好时间复杂度

最坏时间复杂度

最坏情况

平均时间复杂度

平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

均摊时间复杂度

通过摊还分析得到的时间复杂度

函数渐近增长

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

等差等比公式

利用等差等比公式，计算具体的次数公式

大O记法

常见的大O阶

函数调用的时间复杂度分析

算法时间复杂度

算法的时间复杂度分析

空间复杂度

S(n)=O(g(n))

算法执行时所占用的存储空间-->一般只分析辅助变量所占用的空间

空间构成

程序代码所占用的空间；

输入数据所占用的空间；

辅助变量所占用的空间；

定义
辅助空间大小与原数据量之间的关系

原地工作

算法的空间复杂度分析

复杂度主要是以当 n->∞ 时的等阶无穷大来进行判断
而阶大小的主部，主要是根据时间渐近复杂度作为比较依据

求解问题

递归算法

递推公式

递归调用

递归公出口

列方程法

复杂度分析

常数阶O(1)
对数阶O(logn)
线性阶O(n)
线性对数阶O(nlogn)
平方阶O(n^k)|O(n^2)
指数阶O(k^n)|O(2^n)
阶乘阶O(n!)

算法的五大基本特征
算法的五个必要条件

【输入】零个或多个输入

一个算法有零个或者多个输入, 这些输入取自于特定的对象集合。

有零个或多个输入

输入：最少有0个或者多个输入。

【输出】一个或多个输出

一个算法有一个或者多个输出，它们是与输入有特定关系的量。

有一个或多个输出

输出：至少有一个输出。

有穷性、有限性

一个算法总是在执行有穷步后结束。

算法必须总是执行有穷步之后结束且每一步都在有穷时间完成

有穷性：算法的步骤必须是有限的，不能出现无限的循环，并且每个步骤的执行时间也是再可接受的范围。

确定性

算法的每一步都必须是明确地定义的

每一条指令必须有确切含义

确定性:算法的每个步骤必须都有确定的意义既无歧义，在一定条件下只能有一条执行路径。

可行性、有效性

算法是可行的

算法中的每一步都是可以通过已经实现的操作来完成的

可行性：算法的每一步必须都是可行的，每一步都能通过有限的执行次数完成。

常用的算法描述工具
算法及描述

简单文字描述

伪代码

介于自然语言和程序设计语言的伪代码

表格或图形

框图(N-S图)

流程图

程序设计语言

程序

非形式算法（自然语言）

常用、基本算法思想

贪心、贪婪算法

跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标

确定最大覆盖范围

加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1

分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果

一次是从左到右遍历，只比较右边孩子评分比左边大的情况。一次是从右到左遍历，只比较左边孩子评分比右边大的情况

多个维度时，可以先按一个维度贪心计算，再在前者基础上进行另一个维度的贪心计算

用最少数量的箭引爆气球

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数

先按气球起始位置排序，如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭

贪心

跳跃游戏

确定最大覆盖范围

加油站

分发糖果

一次是从左到右遍历，只比较右边孩子评分比左边大的情况。一次是从右到左遍历，只比较左边孩子评分比右边大的情况

多个维度时，可以先按一个维度贪心计算，再在前者基础上进行另一个维度的贪心计算

用最少数量的箭引爆气球

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数

先按气球起始位置排序，如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭

分治算法、分治思想

定义：当一个问题规模较大不宜求解时，就可以考虑将问题分成几个小的模块，逐一解决。

动态规划

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额

dp[i]=max(dp[i−2]+nums[i],dp[i−1])

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合

过滤条件：如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号

每一个括号序列可以用 (a)b 来表示，递归调用 generate(i) 即可计算 a 的所有可能性；
递归调用 generate(n - i - 1) 即可计算 b 的所有可能性

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

状态方程：f(x)=f(x−1)+f(x−2)

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

f(i)=max{f(i−1)+nums[i],nums[i]}

三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1

f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0

字符相等 dp[i][j] = dp[i-1][j-1] +1
字符不相等 dp[i][j] = max(dp[i-1][j],dp[i][j-1])

凑硬币

给你 k 种⾯值的硬币，⾯值分别为 c1, c2 ... ck ，每种硬币的数量⽆限，再给⼀个总⾦额 amount ，问你最少需要⼏枚硬币凑出这个
⾦额

回溯算法

指的是遇到问题或者麻烦的时候就回到前面再继续往前进。

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回

套用回溯模板

类型

组合

排列

子集

分割

棋盘问题

枚举算法

摊还分析

递归思想

定义：递归，就是在运行的过程中调用自己。

注意：必须有结束的条件，不能无限的执行下去。

缺点：效率较低。

常用算法分类

排序算法

交换类排序

冒泡排序

冒泡排序算法

（1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。

（2）这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。

（3）N=N-1，如果N不为0就重复前面二步，否则排序完成。

子主题

冒泡排序

每次循环都比较前后两个元素的大小，如果前者大于后者，则将两者进行交换。这样做会将每次循环中最大的元素替换到末尾，逐渐形成有序集合。将每次循环中的最大元素逐渐由队首转移到队尾的过程形似“冒泡”过程，故因此得名。

一个优化冒泡排序的方法就是如果在一次循环的过程中没有发生交换，则可以立即退出当前循环，因为此时已经排好序了。

冒泡排序

7.3.1 冒泡排序

1.基本思想

算法

算法分析

通过两两比较相领的数据,大的往后放，最后一个就是数组里面最大的，剩下的数里面依此执行此过程
public static int [] bubbleSort(int [] arr){
        for(int j=0;j<arr.length;j++) {
            for (int i = 0; i < arr.length - j - 1 ; i++) {
                if (arr[i] > arr[i + 1]) {
                    DataGenerate.swap(arr, i, i + 1);
                }
            }
            DataGenerate.show(arr,"每次排完的");
        }
        return arr;
    }

可以改进，使用一个交换的boolean值，如果已经排好序了就不用去比较跳出循环

冒泡排序

从后往前(或从前往后)两两比较相邻元素的值，若为逆序则交换位置
经过第n躺冒泡排序后，前n项(或后n项)一定是全局有序的

时间复杂度

稳定

适用于顺序存储、链式存储

交换一次位置需要移动元素3次

冒泡排序

算法描述【最大泡泡冒起来】
每一次排序将最小/最大的元素，通过依次遍历比较交换，放到序列末尾/队首最终位置

时间复杂度

空间复杂度

稳定排序

特点

前i位或者后i位(根据顺序或逆序)为最终有序排序

快速排序

递归算法，初始定义low、high指针
以low指针所指元素作为枢轴(基准)元素
一次划分后，将枢轴元素移动到其最终位置上
并且左边元素均小于它，右边元素均大于它
然后对左右子序列继续进行快速排序

时间效率与递归深度有关，即划分是否对称
划分越对称，深度越浅
时间复杂度最坏

不稳定

每次划分都会将枢轴(基准)元素放到其最终位置上

所有内部排序算法中平均性能最优

使用分治法策略

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

快速排序算法/快排

快速排序的原理：

选择一个关键值作为基准值。

比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。

一般选择序列的第一个元素。

一次循环：

从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。

找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。

直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

算法案例

子主题

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序

快速排序

基于分治思想【二分】

时间复杂度【与递归栈的深度有关】

空间复杂度【栈深】

特点

某个值的左边均为小于它的值，右边均为大于它的值

当序列基本有序或者逆序情况下，效率最低：受不平衡划分影响

插入类排序

直接插入排序

插入排序

插入排序的精髓在于每次都会在先前排好序的子集合中插入下一个待排序的元素，每次都会判断待排序元素的上一个元素是否大于待排序元素，如果大于，则将元素右移，判断再上一个元素与待排序元素；否则该处就应该是该元素的插入位置。

插入排序算法

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。

如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是(n2)。

图解

子主题

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

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

插入排序原理：将一个待排序的数插入到已经按大小排好序的合适位置
   public  static  int [] InsertSort(int [] arr){
        if(arr==null||arr.length ==0)
            return arr;

        for(int i =1;i<arr.length;i++){//默认第一个有序
            int value = arr[i];//保存待插入的数据
            int index = i;//待插入的index
            while (index>0&&value<arr[index-1]){
                     arr[index] = arr[index-1];
                    index--;
            }
            arr[index] = value;
        }
        return arr;
    }

直接插入排序 O(n^2)

不带监视哨

带监视哨

是稳定的排序方式

直接插入排序

将元素与前面已排好序的子序列中的元素进行比较，然后移动位置
即：第n次排序后，前n项子序列一定是局部有序的

时间复杂度

稳定

适用于顺序存储与链式存储的线性表

1.过程

算法分析

直接插入

时间复杂度

稳定排序

特点

每一次排序完后，前i位有序，i位以后也可能存在使得原i位发生改变的值

算法

希尔排序 / 缩小增量排序 / Shell

希尔排序

实际上是缩小增量的直接插入排序

是不稳定的排序方式

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

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

希尔排序算法

基本思想

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

图解希尔排序

子主题

希尔排序代码

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

是插入排序的一种、冲破O(n2）的第一批算法之一。

区别

它会优先比较距离较远的元素

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

* 插入排序的高效版本也称为缩小增量排序，把数组按下标分成一定增量的分组，然后对分组进行
* 简单插入排序，当增量为1的时候数组被分成一组也即排序完成。
* 增量数值有两层含义：1、分组的组数；2、分组的时候下标的间隔是增量数值   private static  int [] ShellSort(int [] arr){
        if(arr==null||arr.length ==0)
            return arr;

        //定义初始增量gap
        for(int gap = arr.length/2;gap>0;gap /=2){//gap为1结束循环  看那个动态图或者解析图很好理解 gap要有一层循环，分组完的数组会进行插入排序需要2层循环一共三层循环
            for(int i = gap;i< arr.length;i++){
                int value = arr[i];//待插入的数据保存
                int index = i;     //待插入下标标记出来
                while (index>0&&index-gap>=0&&value<arr[index-gap]){
                    arr[index] = arr[index-gap];
                    index-=gap;
                }
                arr[index] = value;
            }
            DataGenerate.show(arr,"分为"+gap+"组：");
        }
        return arr;
    }

希尔排序

通过设置步长(增量)d，将待排序表划分为多个子表
每轮在子表内进行直接插入排序，然后取下一个更小的d
常用的方法是

时间复杂度未知，但优于直接插入排序，最坏情况是

不稳定

希尔排序

算法描述
选定增量d，将原序列分成几个部分，然后对每个部分进行插入排序

时间复杂度

空间复杂度

不稳定排序【分组原因】

折半插入排序

通过折半查找确定元素插入子序列的位置，然后统一移动
注：直到low>high才停止折半查找
元素最终插入位置为low所指位置(即high+1)

时间复杂度

稳定

折半插入

对已排好序列查找部分使用折半搜索

顺序存储

时间复杂度

稳定排序

选择类排序

简单选择排序
直接选择排序

每次循环都会找出当前循环中最小的元素，然后和此次循环中的队首元素进行交换。

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

选择排序

简单选择排序：
static  int [] selectSort(int [] arr){
        if(arr==null||arr.length == 0)
        return  arr;
        for(int i= 0 ;i<arr.length-1;i++){
            int minPos = i;//第一个作为最小值
            for(int j = i+1;j<arr.length;j++){
             minPos = arr[j] < arr[minPos] ? minPos = j : minPos;
            }
            DataGenerate.swap(arr,i,minPos);
            DataGenerate.show(arr,"每次排完");
        }
        return  arr;
    }

二元选择排序(每次找出最大和最小值)

简单选择排序

每一趟选择最小的的元素加入有序子列中
即每一趟可以确定一个元素的最终位置

时间复杂度

不稳定

适用于顺序存储与链式存储

元素间比较次数与序列初始状态无关

简单选择

算法描述
每趟找到后n-i个元素中，关键字最小的元素，并与第i个元素进行交换

时间复杂度

空间复杂度

不稳定排序【多个最小取最后遍历位置】

特点

前i位或者后i位(根据顺序或逆序)为最终有序排序

堆排序

树形选择排序

堆排序

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

堆排序

堆排序的过程是首先构建一个大顶堆，大顶堆首先是一棵完全二叉树，其次它保证堆中某个节点的值总是不大于其父节点的值。

因为大顶堆中的最大元素肯定是根节点，所以每次取出根节点即为当前大顶堆中的最大元素，取出后再重新构建大顶堆，再取出根节点，再重新构建…重复这个过程，直到数据都被取出，最后取出的结果即为排好序的结果。

堆排序算法

（英语:Heapsort）

是指利用堆这种数据结构所设计的一种排序算法。

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序

时间复杂度
其中初始建堆O(n)
之后堆排序调整堆

不稳定

对大根堆进行堆排序得到递增序列
对小根堆进行堆排序得到递减序列

基本概念

堆

插入

插入元素放在堆的末端，然后进行上升调整操作
每上升一层，会进行1次关键字对比（与父结点进行对比）

删除

用堆底元素替代删除的位置，然后进行调整
元素每下坠一层，关键字对比次数最多为2次
（第1次左右孩子比较出最大的，第2次最大的与父结点进行比较）
（若只有一个孩子，则只需比较1次）

大根堆：根结点左右孩子

小根堆：根结点左右孩子

建堆

从最后一个非终端结点开始建堆

算法思想
以大根堆为例

用含n个元素的序列建立大根堆，关键字的比较总次数不超过4n

输出堆顶元素，并由堆的最后一个元素代替其位置
（即此时输出的堆顶结点确定了最终位置）

重新建立大根堆

步骤2、3重复n-1次

堆排序

算法描述
二叉堆：完全二叉树，左右子树
均小于/大于根结点【小/大顶堆】

时间复杂度

空间复杂度

建堆时间【计算补充】

特点

最后一个非叶子结点位置为len/2【根结点下标为1】

不稳定排序【调整时可能调节后面位置到根】

锦标赛排序

归并排序

归并排序算法

是什么？

归并（Merge）排序法

将两个（或两个以上）有序表合并成一个新的有序表，

即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

图解过程

代码讲解

比较复杂

https://www.cnblogs.com/shudonghe/p/3302888.html

归并排序

归并排序使用的是分治的思想，首先将数组不断拆分，直到最后拆分成两个元素的子数组，将这两个元素进行排序合并，再向上递归。不断重复这个拆分和合并的递归过程，最后得到的就是排好序的结果。

合并的过程是将两个指针指向两个子数组的首位元素，两个元素进行比较，较小的插入到一个temp数组中，同时将该数组的指针右移一位，继续比较该数组的第二个元素和另一个元素…重复这个过程。最后temp数组保存的便是这两个子数组排好序的结果。最后将temp数组复制回原数组的位置处即可。

归并排序

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

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

private  static  int [] MergeSort(int [] arr,int left,int right,int [] temp){
        if(arr==null||arr.length ==0)
            return arr;

        System.out.println("左边："+left+"  "+"右边："+right+"  "+"中间："+(left+right)/2);
        if(left < right){ //如果左边的一直小于右边的数组一直分解直到左边的索引大于等于右边的索引
            //定义中间索引
            int mid = (left + right) / 2 ;
            MergeSort(arr,left,mid,temp);            //左递归分解
            MergeSort(arr,mid + 1,right, temp);  //右递归分解
            //每次分解一轮   合并一轮
            //合并的结束条件是  两边 left 和  right的索引相等  或者  left> right
            Merge(arr,left,right,mid,temp);
        }
        return arr;
    }

    private static void Merge(int [] arr,int left,int right,int mid,int [] temp) {

    }

归并排序

k路归并

构造辅助空间，将k个有序表和为1

每选出一个最小关键字需要对比k-1次

归并趟数

算法思想

若low<high，将序列从中间mid=(low+high)/2分开

对左右子序列递归地进行归并排序

将左右有序子序列进行2路归并为1个

时间复杂度

稳定

本章算法中，占辅助空间最多

归并排序

算法描述
二路归并算法：初始每个子表长度为1，然后不断两两合并排序，最终合并成长为n的有序序列

时间复杂度【与序列初始状态无关】

空间复杂度

稳定排序

特点

当有足够大到内存装不下的文件进行排序时，采用分治的归并排序

桶排序

桶排序算法

基本思想

把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。

1.找出待排序数组中的最大值max、最小值min
2.使用动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序

计数排序

计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

桶排序算法代码

桶排序

桶排序(Bucket sort)是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。

基数排序

算法描述
基于关键字位上数字大小进行逐一排序

时间复杂度

空间复杂度

常见关键字排序

最高位优先 MSD

最低位优先 LSD

稳定排序

基数排序算法

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

代码

代码1

代码2

基数排序

算法思想

将数据元素的关键字拆分为d组(位)

若关键字位可能取得r个值，则建立r个队列

按照关键字位的权重递增（如个十百）的次序，做d躺分配和收集

分配

顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列

收集

将各个队列中的结点依次出队并链接
若想获得递减序列，则应从当前处理的关键字位，大的开始收集
递增则反之

时间复杂度

稳定

适用于

数据关键字方便拆分位d组，且d较小

每组关键字取值范围不大，即r较小

数据元素个数n较大

不基于比较和移动进行排序

基数排序（卡片排序）

基数排序也是非比较的排序算法

对每一位进行排序，从最低位开始排序，复杂度为O(kn), n为数组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

基数排序基于分别排序，分别收集，所以是稳定的。

基数排序

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

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

计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

拓扑排序

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

数据排序基本概念

对任意n个关键字进行基于比较的排序，至少要进行次关键字之间的两两比较

将一个文件的记录按关键字不减（或不增）次序排列，使文件成为有序文件，此过程称为排序。

大部分排序算法都仅适用于顺序存储的线性表

基本概念

关键字有序过程

至少要进行的关键词比较次数

趟

排序过程中，对尚未确定最终位置的所有元素进行一遍处理

排序的稳定性

稳定排序

若待排序表中有两个值相同的元素，在使用某一排序算法后，两者的相对位置不变，则称该排序算法是稳定的

若排序后，相同关键字的记录保持它们原来的相对次序

不稳定排序

算法稳定性

稳定性

排序的目的

排序是为了方便查找

排序类型

内部排序

除了外部排序的都是内部排序

分配类排序

多关键字排序

链式基数排序

外部排序

外部排序的方法

根据内存缓冲区大小，生成初始归并段

磁盘排序

磁带排序

置换-选择排序

增大归并段长度，减少初始归并段个数
此方法的每个初始归并段长度可能互不相同

多路平衡归并与败者树

败者树

减少归并时关键字比较次数

多路归并排序

最佳归并树

若(初始归并段数-1)%(归并路数-1)=u不为0
则需要添加长度为0的虚段
添加个数为k-1-u个

权值为归并段长度，仿照哈夫曼树
减少归并过程中的读写次数

排序的分类

简单排序

冒泡排序

选择排序

插入排序

高级排序

希尔排序

归并排序

快速排序

排序算法对比
各种内部排序算法的比较及应用

排序比较、排序的衡量标准

排序的时间复杂度

有序情况下

直接插入、冒泡排序

快排

无序情况下【平均】

简单选择、直接插入、冒泡排序

堆排，快排、归并

O(nlogn)

堆排序

快速排序

归并排序

O(n^2)、O(n²)

冒泡排序

插入排序

选择排序

希尔排序

O(n)

计数排序

基数排序

桶排序

排序的空间复杂度

简单选择、插入、冒泡、希尔、堆排

快排

归并

算法过程特征

【每趟结束能够确定一个元素最终位置】
堆排序，快速排序、简单选择

【比较次数与初始序列】

无关
二路归并排序、简单选择排序、基数排序

有关
快速排序、直接插入排序、冒泡排序、堆排序、希尔排序

【排序趟数与初始序列】

无关
直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序

有关
冒泡排序、快速排序

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念

基数排序：根据键值的每位数字来分配桶

计数排序：每个桶只存储单一键值

桶排序：每个桶存储一定范围的数值

排序算法整合（冒泡，快速，希尔，拓扑，归并）

https://blog.csdn.net/onceing/article/details/99838520

程序员那些必须掌握的排序算法(上)

https://blog.csdn.net/qq_42453117/article/details/99680831?ops_request_misc

超详细十大经典排序算法总结

https://blog.csdn.net/weixin_41190227/article/details/86600821?ops_request_misc

查找/查询算法、搜索算法
常见查找算法、常见查询算法

查找的基本概念

查找

根据给定的某个k值，在查找表寻找一个其键值等于k的数据元素。

查找表/查找结构

用于查找的数据结构

操作

查找特定元素

检查满足条件元素属性

插入元素

删除元素

关键字

数据元素中唯一标识该元素的某个数据项的值

主关键字

冲突/碰撞

同义词之间冲突

不可能避免

聚集/堆积

同义词与非同义词发生冲突

主要与冲突探测方法有关

查找算法的评价指标
查找算法的效率指标

查找长度

在查找运算中，对比关键字的次数

平均查找长度ASL

查找成功

查找失败

平均查找长度

装填因子

区别静态和动态查找

对查找表无需进行动态地修改，则称为静态查找表，否则称为动态查找表

静态查找

顺序查找法、顺序查找

二分查找、折半查找法

分块查找法

动态查找

二叉排序树

AVL树查找

树表查找

二叉树查找
二叉树法

红黑树【new】

B树和B+树

查找的三大分类

线性结构
线性表查找
基于线性表的查找

顺序查找法、顺序查找

6.2.1顺序表的查找

算法

过程

从表中最后一个记录开始顺序进行查找，若当前记录的
关键字=给定值，则查找成功

算法分析

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

从表中第一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功

带哨兵的顺序查找

在查找表的尽头放置哨兵，免去每次比较值后还要判断下标是否越界

顺序查找

通常用于线性表

由于失败结点是虚构的空结点，故到达失败结点时所查找的长度等于它上面一个圆形结点所在的层数

若有n个结点，则有n+1个失败结点(空链域)

顺序查找(链式限制)

一般顺序表查找

有序表顺序查找

二分查找、折半查找法

6.2.2有序表的查找

二分查找算法

算法分析

log2n +1

又叫折半查找，

要求待查找的序列有序。

每次取中间位置的值与待查关键字比较，

如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，

如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。

直到查找到了为止，否则序列中没有待查的关键字。

二分法

要求数据必须有序

o（n）

参考代码

二分查找

折半查找

仅适用于有序的顺序表

基本思想

指针low指向最小元素，high指向最大元素，mid指向

若查找元素大于mid，令low=mid+1
若查找元素小于mid，令high=mid-1

重复(1)(2)，直到查找成功或high小于low

判定树

若mid为向下取整，则对应的折半查找判定树，右子树结点数-左子树结点数=0或1

一定是平衡的二叉排序树

只有最下面一层会出现不满的情况

若有n个关键字，则失败结点有n+1个

树高
(不包括失败结点)
树的高度也是折半查找时进行关键字的比较最多的次数

时间复杂度

说明：元素必须是有序的，如果是无序的则要先进行排序操作。

基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

　注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》

折半查找（二分查找）

前提线性表中记录是有序的，每次比较时取线性表的中间值比较，若相等则查找成功，若小于，则在线性表左半区查找，若大于则在线性表右半区查找，不断重复上述过程，直到成功，或所有查找区域无记录，查找失败

折半(二分)查找

适用于有序顺序存储结构

判定树

平衡二叉树

最多查找次数

最少查找次数

分块查找法、索引顺序查找法

分块查找

说明：分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

索引顺序表的查找

过程

算法分析

平均查找长度：1/2(n/s+s)+1
s:每块元素个数

1.先建立最大（或小）关键字表；
2.查找索引表，以确定所查元素所在块号；
3.在相应块中按顺序查找关键字为k的记录。

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

分块查找

块内无序，块间有序

索引表

每个元素含有每块的最大（或最小）的数据

基本思想

在索引表中确定待查记录所在的块，可顺序查找或折半查找

使用折半查找时，若索引表中没有与待查记录相等的关键字，则当low大于high后，在low所指分块中进行查找

在块内顺序查找

平均查找长度

若顺序查找索引表，并将长度为n的查找表均匀分为b块，每块有s个记录
则

若，则取到最小值

拓展：若查找表是动态查找表，则可用链式存储来建立索引表以及查找表

分块(索引顺序)查找

理想块长

顺序分块查找

最优优化

树形结构
树形查找
树结构查找
基于树的查找
索引结构/树表

二叉排序树

什么是二叉排序树

性质

中序遍历一棵二叉排序树所得的结点访问序列是键值的递增序列

查找算法

二叉排序树的插入和生成★

查找分析

平均查找长度是介于O(n)和O(log2n)之间的，
其查找效率与树的形态有关

AVL树查找

二叉平衡树

平衡二叉排序树

AVL平衡二叉树

树表查找

二叉树查找算法

基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
　　1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
　　2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
　　3）任意节点的左、右子树也分别为二叉查找树。

二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

平衡查找树之2-3查找树（2-3 Tree）

2-3查找树的性质：
　　1）如果中序遍历2-3查找树，就可以得到排好序的序列；
　　2）在一个完全平衡的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）性质，从根节点到叶子节点的距离都相等）。

二叉树查找
二叉树法

需要先建索引

o（logn/2)

红黑树【new】

B树和B+树

B树/多路平衡查找树

属性

B树的阶

非叶结点结构

平衡因子=0

高度

最高

最低

关键字数

最多

最少

性质

非根结点关键字个数

非根结点子树个数

根节点为非终端结点时，至少有两个孩子.

严格平衡查找树，所有节点子树高度一致
叶子处于同一层且用NULL表示

非叶结点的结构

操作

查找

插入

分裂

删除

合并

图示

计算

已知阶、层数、某层关键字数，求最多结点数

B+树

图示

B与B+树区别

B树

B-树

B+树

B树和B+树

B树

基本概念

结点的孩子个数最大值称为B树的阶，记作m

终端结点

叶结点

核心特性

对任一结点，其所有子树高度都相同（绝对平衡）

结点中关键字的值是有序的（升序或降序）

关键字总会大于它左子树上的值，小于它右子树上的值

含有n个关键字的m叉B树的高度满足，

最小高度
每个结点关键字数量最大，子树数量也最大，则

最大高度
每个结点关键字数量最小，则每层结点数量也最少
则第一层有1个结点，第二层有2个结点，第3层有个，第h层有个
则叶结点数量大于等于高度+1层的最少数量即

基本操作

查找

插入

插入后的结点关键字个数大于m-1时，需进行结点分裂
将中间位置的关键字插入原结点的父结点中，右部分放新结点中
若此时父结点也超出了上限，则继续分裂

删除

被删关键字k在非终端结点

用关键字k的前驱或后继来替代k的位置

被删关键字k在终端结点

若删除后，结点中关键字个数仍满足B树特性，则直接删除

若删除后不满足B树特性

兄弟够借，结点的双亲结点关键字替代k的位置，兄弟的关键字顶替双亲的位置

兄弟不够借，则将结点与双亲结点中的关键字和兄弟结点结合起来
若双亲结点的关键字又不满足特性，则继续合并

B+树

与B树主要差异

每个非叶结点中，关键字数等于子树数，即满足关键字数

所有叶结点包含了全部关键字及指向相应记录的指针，所有非叶结点仅起索引作用
非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针

叶结点中将关键字按大小顺序排序，并将相邻叶结点按大小顺序相互链接起来

B+树有两个头指针，一个指向根结点，一个指向关键字最小的叶结点。
因此可以对B+树进行从最小关键字开始的顺序查找和从根结点开始的多路查找

无论查找成功与否，都最走到最后一层

B+树

散列表查找
计算式查找
哈希法、哈希表
哈希查找
散列结构查找

散列表

散列函数

直接定址法

除留余数法

数字分析法

平方取中法

折叠法

性能分析

散列地址的计算

冲突处理

开放定址法

线性探测法

平方探测法

再散列法

伪随机序列法

拉链法

构造

数字分析法

平方取中法

分段叠加法

除留余数法

伪随机数法

哈希查找

哈希表

　我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
　　总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。

哈希函数

哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。

算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

散列表查找

定义：散列技术是在记录的存储位置和它的关键字之间建立一个确定的关系f，使得每个关键字key对应一个存储位置f(key)

散列冲突：key1≠key2，但却有f(key1)=f(key2),这种现象我们称为冲突

散列函数构造方法

直接定址法

数字分析法

平方取中法

折叠法

除留余数法

随机数法

处理散列冲突的方法

开放定址法

再散列函数法

链地址法

公共溢出区法

散列表

概念

散列函数

冲突（碰撞）

同义词

装填因子

常见散列函数

除数留余法

直接定址法

数字分析法

设关键字是r进制数，取数码分布较为均匀的若干位作为散列地址

平方取中法

取关键字平方值的中间几位作为散列地址

冲突的处理

拉链法（链地址法）

将同义词串成一个链表

插入关键字时，保持链表有序，可以略微提高效率

开放定址法

线性探测法

会造成“聚集”（或堆积）现象
即大量元素在相邻的散列地址上，降低查找效率

平方探测法

散列表长度必须是一个可以表示为4k+3的素数，才能探测到散列表上的所有单元

伪随机序列法

di为一个伪随机序列

使用开放定址法时，不能随便物理删除表中的已有元素，而是要做一个删除标记，进行逻辑删除
因为用开放定址进行散列查找时，会按照所选方法进行查找，一旦找到位置上无记录，则认为查找失败

再散列法

准备多个散列函数，一个发生冲突了就用下一个

查找效率

取决于散列函数，处理冲突的方法，装填因子

平均查找长度ASL的计算

使用拉链法时，与空链域的比较不算入对比次数
使用开放定址法时，与空位置的比较需要算入对比次数

散列函数

直接定址法

除留余数法

数字分析法

平方取中法

散列结构

散列表

散列函数

直接定址法

除留余数法

数字分析法

平方取中法

折叠法

性能分析

散列地址的计算

冲突处理

开放定址法

线性探测法

平方探测法

再散列法

伪随机序列法

拉链法

散列结构

散列表

散列函数

直接定址法

除留余数法

数字分析法

平方取中法

折叠法

性能分析

散列地址的计算

冲突处理

开放定址法

线性探测法

平方探测法

再散列法

伪随机序列法

拉链法

散列表（哈希表）

1、基本概念

散列函数（哈希函数）

散列地址——由散列函数决定数据元素的存储位置

散列查找

冲突

k1≠ k2 但 H（k1） =H（k2）的现象称为冲突

2、常用散列法

1、数字分析法

2、除留余数法

函数算法：H(key)= key mod p （p≤n ）

方法关键——如何取p ？

3、平方取中法

4、基数转换法

3、散列表的实现

链地址法

线性探测法

思想：计算出的散列地址已被占用，
则按顺序找“下一个” 空位

★要点

二次探测法

多重散列法

公共溢出区法

散列法的优缺点

优点：直接由关键字通过哈希函数计算出哈希地
址，查找效率高

缺点：常发生冲突，影响查找效率

冲突处理

开放定址法

线性探测再散列

二次探测再散列

伪随机探测再散列

链地址法

再哈希(散列)法

处理冲突
冲突解决

拉链法

开放定址法

再哈希法

链地址法

建立公共溢出区

搜索算法

深度优先搜索

广度优先搜索

A*启发式搜索

查找

有序表查找

插值查找

插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找

　基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

斐波拉契查找

基本思想：也是二分查找的一种提升算法

通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。

同样地，斐波那契查找也属于一种有序查找算法。

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1;
开始将k值与第F(k-1）位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种
1）相等，mid位置的元素即为所求
2）> ,low=mid+1,k-=2;说明:low=mid+1说明待查找的元素在[mid+1,hign]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-（F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找
3)< ,high=mid-1,k-=1;说明:low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找

回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，

主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

剪枝算法

在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，

形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。

应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

图解剪枝算法

线性索引查找

定义:所谓线性索引就是将索引项集合组织为线性结构，也称索引表

稠密索引：稠密索引是指在线性索引中，将数据集的每个记录对应一个索引项，对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列

分块索引

倒排索引

数据结构：七大查找算法

https://blog.csdn.net/jekcai/article/details/80357294

模式匹配算法

KMP算法（看毛片算法）

就是要减少不必要的回溯

不必要的回溯是由模式串（就是去要匹配的字符串）决定的，不是由目标（被匹配的字符串）决定的。

BF(BoyFriend）算法

最简单的反模式匹配算法

需要反复的回溯到前面进行再次匹配

定义：查看字符长1中有没有和字符串2相同的字符串片段。

字符串匹配算法

字符串模式匹配

简单的模式匹配算法

KMP算法

next数组

字符串匹配

朴素

KMP

Robin-Karp

Boyer-Moore

AC自动机

Trie

后缀数组

字符串匹配

朴素

KMP

Robin-Karp

Boyer-Moore

AC自动机

Trie

后缀数组

工作沉淀的算法

LRU算法

负载均衡算法

一致性哈希算法

Snowflake算法

蓄水池抽样算法

大数据算法

Top K算法

其他

什么是可执行程序

算法+数据结构

算法的主要目的

程序与算法的根本区别

程序中可以允许无限循环的产生

堆排

二叉树

双指针法

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组

排序+三指针，一个指针当做目标值，左指针和右指针向中心逼近

盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水

利用双指针，分别从左边界和右边界向中心移动

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

利用双指针，右指针移动，遇到非0的数据，左右指针数据交换，左指针移动一步

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度

跟移动零是一个逻辑

双指针法

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组

排序+三指针，一个指针当做目标值，左指针和右指针向中心逼近

盛最多水的容器

利用双指针，分别从左边界和右边界向中心移动

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

利用双指针，右指针移动，遇到非0的数据，左右指针数据交换，左指针移动一步

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度

跟移动零是一个逻辑

随机化算法

图论算法

跳楼梯

环节点

成环

链表反转

最短路径算法

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。

解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。

最小生成树算法

现在假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
于是我们就可以引入连通图来解决我们遇到的问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。

构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST性质（假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树），

下面就介绍两种使用MST性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法。

子主题

最长公共子序算法

最大子数组算法

数据结构简介、概述、绪论、导论

数据结构的基本概念

导图

综合题

例1

答

例2

答

选择题

例1

答

例2

答

例3

答

例4

答

例5

答

例6

答

例7

答

认识程序设计

程序开发流程

评判程序设计好坏的四项原则

可读性高

平均成本低

可靠度高

可编写性高

程序的产生过程，程序设计的五大步骤

需求认识

设计规划

分析讨论

编写程序

测试验证

数据类型简介

基本数据类型

物理数据类型

基本的数据实体

每种语言都拥有略微不同的基本数据类型

结构型数据类型

虚拟数据类型

比物理数据类型更加高级

一个数据结构中包含其他的数据类型

字符串

集合

数组

抽象数据类型

ADT

比结构型数据更高级

无需考虑制作细节，只需知道如何使用

只针对数据的运算，不需关心这个对象的类型是否哪种？

实例

堆栈

队列

结构化程序设计

传统的程序设计的方法

以“由下而上”与“由上而下”方法为主

由下而上

将整个程序需求中最容易的部分先编写，再逐步扩大来完成整个程序

由上而下

将整个程序需求，从上而下、由大到小逐步分解成较小单元

模块化设计

结构化程序设计的核心精神

由上而下设计

模块化设计

面向过程的设计无法有效使用程序代码的原因

每个模块会完成特定功能，主程序则组合每个模块后，完成最后要求的功能，

数据结构的概念，什么是数据结构？

数据结构(Data structure）是指一组存在特定关系的数据的组
织方式和它们在计算机内的存储方式，以
及定义在该组数据上的一组操作

多种特点关系的数据元素的集合；

元素的关系被称为结构

计算机解决问题的步骤

建立数学模型

设计算法

编程实现算法

数据结构主要研究

1）数据（计算机加工对象）的逻辑结构

2）实现各种基本操作的算法

学习数据结构的目的

掌握常用的数据结构及其应用

学会合理地组织数据，有效地表示数据和处理数据

掌握算法设计技术和分析技术。

掌握使用计算机解决问题的方法和技能，提高程序设计水平

数据与信息

什么是数据、数据（Data)

数据

数据是一种信息载体

被计算机处理的符号集合

未经过处理的，文字+数字+符号+图形

数据元素（Data Element）

数据的基本单位

(个体)基本单位

是数据集合中的基本单位

数据项（Data Item）

(个体)属性

构成数据元素的最小单位

数据元素分为若干个数据项，具有意义的最小单位。

数据对象

具有相同性质的数据元素集合

数据类型

值的集合与操作的总称
例如整数能够增加减少操作

原子类型

结构类型

抽象数据类型(ADT)

(数据对象，数据关系，基本操作集）

数据与信息

什么信息

以特定方式系统地整理，归纳甚至进行分析的结果

数据与信息之间的关系

数据，经过处理（整理算法+分析数据结构），变成信息

数据与信息角色之间在不同场景下可以相互转换

美伊战争中的死亡人数报告

数据结构分类

线性数据结构

线性表

数组

栈

特殊的线性结构，只能在一端进行操作

特点

先进先出

适用场景

常用于实现递归方面的操作；如：斐波那契数列

队列

特殊的线性结构，一端操作数据入队，一端操作数据出队

特点

先进先出

适用场景

先进先出特点，多线程阻塞队列中，常使用

链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现

根据指针指向分类

单向链表

双向链表

循环链表

优点

不需要初始化容量，可以任意加减元素；
加减元素只需要更改前后指针

缺点

含有大量指针域（每个节点数据都有），内存消耗高；
遍历元素需要遍历链表，比较耗时

适用场景

数据量少，频繁增删元素

串

概念

结构

匹配算法
（字符串匹配算法）

BF算法

KMP算法

高级数据结构

自顶向下伸展树

红黑树

确定性跳跃表

AA树

treap树

k-d树

配对堆

数据结构（三要素）

数据的逻辑结构

逻辑结构

（Logical Structure）

数据元素之间逻辑关系，独立于计算机

指数据元素之间的结构关系

逻辑结构与数据元素本身形式、内容无关

逻辑结构与数据元素的相对位置无关

逻辑结构与所含结点个数无关

逻辑结构：是指数据对象中数据元素之间的关系。

线性结构

线性结构定义

除起始节点和终端结点d1、 dn外，每个节点有一个前驱和一个后继

线性结构：其中的数据元素都是一对一的关系（就好像一条线）。

线性表：

说明

具有相同数据类型的n个数据元素有限序列

一般线性表

顺序存储

顺序表：第一个元素存储在线性表起始位置
第 i 个元素后面紧跟第 i+1个元素

选择：求移动节点平均次数王道P14

综合应用题：实现对顺序表的增删查改 P17

链式存储

指针实现

单链表

双链表

循环链表

数组实现

静态链表

受限线性表

栈

队列

串

线性表推广

数组

广义表

循环单链表：每一个元素都有直接前驱和直接后继

非线性结构

集合

数据元素同“属于一个集合”

集合结构：其中的数据元素除了属于同一个集合外，没有其他任何的关系。

树形结构

(D, {R}) 构成树, 即每个元素最多有一个前驱, 可以有多个后继。

树形结构：其中的数据元素存在一对多的层次关系。

一般树

二叉树

多叉树

森林

图状结构、图/网

(D, {R})构成一个图

图形结构：其中的数据元素存在多对多的关系。

无向图

有向图

数据的存储结构（物理结构）

物理结构/存储结构

（Physical Structure）

物理结构：数据的逻辑结构在计算机中的存储形式。

OS中文件的存储结构便包括顺序，链式，索引存储

包括数据元素的表示和关系的表示

指数据结构在机内的表示，数据的逻辑结构在计算机中的实现

4种存储结构

顺序存储结构

借助数据元素的相对存储位置来表示数据的逻辑结构

顺序的方法：将元素存储到一片连续的存储区

顺序存储：逻辑相邻、物理位置相邻

顺序存储结构：就是把数据元素存储在地址连续的存储单元中，其数据间的逻辑结构和物理结构是一致的。

特点

1.预先分配好长度，需要预估存储数据需要的存储空间

2.插入和删除需要移动其他元素

3.存取快捷，是随机存取结构

优点：1.实现随机存取 2.元素占用最少的存储空间
PS：存储和存取不同，存取分为随机存取和顺序存取，王道P3记录笔记

缺点：1.只能使用相邻的一整块存储单元，可能产生较多的外部碎片

链式存储结构

借助数据元素地址的指针表示数据的逻辑结构

存储单元分为：数据项和指针项

链式存储结构：

就是把数据元素存储再任何的存储单元中，

存储单元可以是连续的也可以是不连续的，

但是为了保持数据间的逻辑结构，就通过指针的方式来保持关系。

链式存储：物理位置不需相邻

特点

动态分配，不需要预先确定内存分配；

插入和删除不需要移动其他元素

非随机存取结构

优点：1.不会出现碎片现象 2.能充分利用所有存储单元

缺点：1.每个元素因存储指针还需要额外存储空间 2.只能实现顺序存储

索引存储方式

借助索引表中的索引指示各存储节点的存储位置

索引存储：存储元素同事，建立附加索引表
PS：索引表中每一项称作索引项，其一般形式（关键字，地址）

优点：检索速度快

缺点：1.附加的索引表占用存储空间 2.增删数据需要修改索引表

散列存储/哈希存储方式

用散列函数指示各节点的存储位置

散列存储（哈希存储）：根据元素关键字直接计算出该元素存储地址

优点：增、删、查速度快

缺点：如果散列函数不好，会出现存储单元冲突，解决冲突耗时大

存储

数据元素的存储

逻辑关系的存储

存储结构的主要部分

存储结点（每个存储结点存放一个数据元素）

数据元素之间关联方式的表示

逻辑结构与存储结构的关系

逻辑结构

数据结构定义中的关系，指数据间的逻辑关系，故数据结构也称逻辑结构

存储结构

数据结构在计算机中的表示，称物理结构或存储结构

数据的运算（操作）

定义

运算就是指在某种逻辑结构上施加的操作，即对逻辑结构的加工

加工型运算

其操作改变原逻辑结构的

如：结点个数，结点内容等

引用型运算

其操作不改变原逻辑结构的值

增

删

改

查

排序

数据结构

线性表(List)

线性表(List)的定义/概念

零个或多个数据元素的有限序列

是线性结构，由 n(n≥0)个数据元素组成的有穷序列，数据元素又称结点

线性表(List)

广义表(Lists)

Linear List 线性表

定义：有零个或者多个数据元素组成的有序序列。

零个就代表时空表。

有序的说的是数据元素是由顺序的。

有限个

存储空间大小相同

表头元素；表尾元素；位序；前驱；后继

基本特征

一对一的关系，起始结点没前驱，终端结点没有后继，一前一后

前驱和后继：a的前驱是a-1，a的后继就是a+1；并且有且只有一个前驱和后继。

基本运算

1.初始化

2.求表长

3.读表元素

4.定位

5.插入

6.删除

区分引用型和加工型操作

如何选取？

基于存储考虑

表的长度和存储规模难以估计时不宜采用顺序表

基于运算考虑

运算按序号访问元素时，顺序表优于链表；但在做插入、删除操作时链表优于顺序表

基于环境考虑

顺序表容易实现；链表操作基于指针

操作

创建/销毁

静态分配

动态分配

C/C++
malloc , new[]

增删改查

属性获取

数据类型

定义：是指一组性质相同的值的集合及定义在着个集合上的一些操作的总称。

抽象数据类型

定义：是指一个数据模型及定义在该模型上的一组操作，有一组特定的特性。

按照取值的不同可分为

原子类型：就是不可再分割的一些数据类型。如：整形、浮点型、字符型等。

结构类型：由若干个类型组成的，是可以在分开的类型。

线性表的存储结构
线性表的存储结构的定义

顺序存储结构
sequential mapping

SqList
顺序表

顺序表

定义：就是再物理地址中申请连续的存储单元，然后把这些相同的数据类型有序的放入到这些存储单元中。

顺序存储的特点

顺序表最主要的特点是随机访问

连续的存储空间

随机存取，查找方便

基本操作

插入

删除

查找

特性

随机存取[物理顺序和逻辑顺序相同]

删除和插入时间复杂度高

分配方式

静态

C语言数组方式分配

动态

C语言指针方式分配

操作

初始化

插入

实现逻辑

健壮性判断

移动

属性修改

返回函数状态

时间复杂度

最好
O(1)

最坏
O(n)

平均 = 概率移动次数 = 期望

删除

实现逻辑

健壮性

移动

属性修改

返回函数状态

时间复杂度

最好
O(1)

最坏
O(n)

平均

按值查找

实现逻辑

顺序寻找

返回位序

时间复杂度

最好
O(1)

最坏
O(n)

平均

合并

特点：再存，读数据时不管在那个位置时间复杂度都为O(1)；再插入和删除时不管在什么位置时间复杂度都是O(n);
所以比较适合数据元素稳定，不经常进行插入和删除操作，反而适合更多读取和存储操作的应用。

优点

不需要为表之间元素之间的逻辑关系而增加存储容量；

可以快速存取表中任何位置的元素。

缺点

插入和删除操作需要移动大量元素；

当线性表的长度变化大时，就难以确定存储空间的容量；

容易造成空间碎片

数组

例子：数组。

类型定义

表中的结点在计算机内存连续的存储单元，邻接关系决定存储位置，逻辑相邻=存储相邻

特点

1.逻辑结构与存储结构一致

2.可以随机读取

线性表的基本运算的实现

3.基本运算

4.定位

5.插入

6.删除

优点

无需为表示结点间的逻辑关系而增加额外存储空间

可以方便地随机存取表中的任一结点

缺点

插入和删除运算不方便

要求占用连续的空间，存储分配只能预先进行

顺序表实现算法的分析

分析数据元素的比较和移动的次数

插入算法

最坏时间复杂度O(n)

元素比较和移动的次数为 n-i+1 次

平均移动次数约为 n/2

删除算法

最坏情况下元素移动次数为 n-1

一般比较和移动次数是n-i次

平均移动次数约为（n-1）/2

时间复杂度为 O(n)

定位算法

时间复杂度为 O(n)

求表长和读表元素算法的时间复杂度为 O(1)

链式存储结构

相关概念

头指针

头指针：链表中第一个结点存储的位置称为头指针，如果单链表有头结点，则头指针指向头结点，如果单链表没有头结点，则头指针指向第一个首元结点

头结点

头节点：在单链表的一个结点前附设一个结点称为头结点，数据域可以不存任何信息，指针域指向单链表第一个元素的结点

链表头

尾指针

首元结点

首元结点：单链表中第一个有数据元素的结点，如果单链表有头结点，则首元结点为头结点的下一个结点，如果单链表没有头结点，则首元结点就是单链表的第一个结点

定义：是用任意一组存储单元来存储线性表的数据元素，这一组存储单元可以存在于内存中任何空闲的位置。

特点：每个存储单元（节点）除了存储数据（数据域）还要存储其后继元素的位置信息（指针域，里面的信息被称为指针或者链）。

单链表

定义

单链表：包含一个数据域和一个指针域

操作

插入

头插法

尾插法

时间复杂度
O(n)

删除

按值查找

判空

类型定义

1、结点结构

数据域

指针域或链域

任意存储

特点

首结点

head头指针

实现

3.基本运算

1.初始化

产生新节点-->动态分配内存函数malloc函数
（数据类型*） malloc（sizeof（数据类型））
如： int *p;p=（int *） malloc（sizeof（int））

2.求表长

3.读表元素

4.定位

5.插入

q=GetLinklist (head, i-1); //找到第 i-1个数据元素结点

p=malloc(sizeof (Node) );p->data=x; //生成新结点

p->next=q->next; //新结点链域指向*q的后继结点

q->next=p; //修改*q的链域

6.删除

p = q->next;

q->next = p->next;

free(p);

其他运算在单链表上的实现

2.4.1建表

2.4.2删除重复节点

单链表

基本操作

建立

头插法

尾插法

查找

按序号查找

按值查找

插入

前插

后插

删除

双链表

定义

双向链表：在单链表中的每个结点中，再设一个指向其前驱结点的指针域

操作

插入

实现逻辑

时间复杂度

删除

双链表

基本操作

插入

删除

循环链表

将单链表中终端结点的指针域由空指针改为指向头结点，使单链表形成一个环

终端结点的next指向头结点

rear指针指向尾结点

单向循环链表

双向循环链表

在链表中设置两个指针域，
一个指向后继结点
一个指向前驱结点

插入

删除

循环链表

循环单链表

循环双链表

静态链表

借助数组实现

静态链表：用数组描述(数据域，指针域)的链表叫静态链表

数组存储下表跳转信息，建立链接逻辑
【数组模拟的链式结构】

相关概念

顺序表和链表的比较

存取方式

顺序表

可以顺序存取也可以随机存取

链表

只能从表头顺序存取

逻辑结构和物理结构

顺序存储

逻辑上相邻的元素物理上也相邻

链式存储

逻辑上相邻的元素物理上不一定相邻

基本操作

查找

按值查找

顺序表无序的情况下，两者时间复杂度均为O(n)

顺序表有序的情况下，采用折半查找则时间复杂度为O(log2(n))

按序号查找

顺序表

支持随机访问，时间复杂度O(1)

链表

平均时间复杂度O(n)

插入、删除

顺序表

平均移动半个表的长度

链表

只需修改相关节点的指针域计科

空间分配

顺序存储

静态存储

一旦空间装满就不能扩充

动态存储

虽然存储空间可以扩村，但需要移动大量元素，效率降低

链式存储

节点空间只在需要的时候申请分配，操作灵活、高效

顺序实现与链表实现的比较

优缺点比较

时间性能的比较

顺序存储和单链表（链式结构）的优缺点

优缺点

顺序

随机访问，链式则只能顺序访问

链式

分配灵活，无需占用连续空间，插入删除时间复杂度低

存储分配方式

顺序存储结构用一段连续的存储单元，一次存储线性表的元素。

单链表是链式存储结构，用任意一组存储单元存储线性表的元素。

时间性

查找

顺序存储是O(1)。

单链表是O(n)。

插入和删除

顺序存储需要平均移动一半所以时间复杂度为O(n)。

单链表在计算出某个位置时时间复杂度为O(1),在没有计算出来时为O(n)。

空间分配

顺序存储结构需要预先分配空间大小，分小了溢出，分多了空间浪费。

单链表是链式的存储结构，可以不预先分配大小，灵活方便，只要有空间就行。

逻辑结构

数组（Array）

栈（Stack）

队列（Queue）

串(string)

串，字符串（string）

串的定义、基本概念

子串

主串

位置

串是由零个或多个字符组成的有限序列，又叫字符串

本质上是一种线性表扩展，只不过针对内容做出了限制

与线性表区别在于只存储子串(字符)类型

串的存储结构

顺序存储

数组实现

顺序存储：以一段连续的存储空间

链式存储

链串：
与线性表类似，不过一个结点对应一个字符，会存在很大的空间浪费
一般一个结点存放多个字符(即块链结构)，若一个结点未被占满时，可以用"#"或其他非串值字符补全

链式存储结构----块链结构

链式存储:可以一个结点对应一个字符，也可以一个结点对应多个字符，若结点未占满可用其他非串值字符填满

定长顺序存储

堆分配存储

块链存储

C默认串默认增加'\0'以表示结尾

串的操作

与线性表相比，线性表更关注的是单个元素的操作，比如查找、插入、删除一个元素
但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作

串的比较

采用按位比较ASCII码

给定两个串：s=,t= 当满足以下条件之一时，s < t
1、n < m,且 = (i =1,2,,n)
例：s=“hap”，t=“happy”
2、存在某个k≤min(m,n), 使得 = (i =1,2,,k-1), <

例：s=“happen”，t=“happy”

模式匹配

朴素的模式匹配算法(BF)

KMP模式匹配算法

模式匹配算法

暴力匹配

KMP模式匹配算法

KMP算法

next数组

概念：子串与主串不匹配时，子串下一个开始匹配的索引的值取决于与子串当前失配字符之前的字符的最大前后缀的相似度

当j=0时，next[j]=-1
当0<k<j时，且'p0...p(k-1)'='p(j-k)...p(j-1)',next[j]=Max(k)
其他情况时，next[j]=0

注意：对于短的字符串匹配，KMP算法效率可能不如朴素模式匹配算法，因为KMP算法要首先生成next数组

朴素模式匹配算法

导图

图1

图2

字符串相关API

search and replace

find

rfind

index

rindex

count

endwitn

startwith

replace

formatting

capitalize

lower

upper

swapace

title

splitting

partition

rpartition

split

rsplit

splitlines

padding

center

ljust

lstrip

rjust

rstrip

zfill

strip

expandtabs

checking

isalnum

isalpha

isdigit

islower

isspace

istitle

issupper

栈（Stack）

栈的基本概念

定义

栈是限定仅在表尾进行插入和删除操作的线性表

栈是只能在表的一端（表尾）进行
插入和删除的线性表

定义：是一种线性结构，先进后出，后进先出，他要求删除（出栈，弹栈）和插入（进栈、压栈）操作在栈尾完成。

表头称为栈底，表尾称为栈顶。当栈中没有任何数据时被称为空栈。

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶（top）。

栈顶(top)

栈顶指针：指向栈顶结点的指针

栈低(Bottom)

空栈(Empty)

栈的判空判满都根据实际情况进行分析
主要掌握逻辑【数据结构其实可以视为某种物理/逻辑模型(在现实中都能找到)】
只要选择好类比的逻辑，就好自己理解这个部分

数学性质 [ 卡特兰数 ]
n 个不同元素进栈，出栈元素不同的排列个数为

特性、特点

特性
LIFO 后进先出

LIFO（后进先出）

它是后进先出（LIFO）的。

后进先出（Last In First Out，LIFO）

先进后出

吃多了吐

栈：先进后出

栈的基本操作

删除和插入

都是在栈顶进行。

清空：就是将栈中的数据清空，就是将栈顶指向栈尾，不改变数据的物理结构。

销毁：就是将栈中数据占物理内存进行清空。

销毁
Destroy(&S)

（1）初始化栈：InitStack(S);

初始化
Init (&S)

（2）判栈空：EmptyStack (S);

isEmpty——如果栈为空，则返回true

（3）进栈：Push (S,x);

Push——在顶部插入一个元素

相当于插入

push（进栈）

进栈(Push)
Push(&S,&e)

（4）出栈：Pop (S);

Pop——返回并移除栈顶元素

相当于删除最后的元素

pop（出栈）

出栈
Pop(&S,&e)

（5）取栈顶： GetTop(S);

Top——返回顶部元素，但并不移除它

读取栈顶
GetTop(S,&e)

栈的存储结构、类型

时间复杂度均为O(1)

顺序存储结构（常用）

计算栈的当前容量

s.top-s.base(两个数据必须是同一个数据类型、指针不能加)

顺序存储

顺序栈

基本运算

初始化

判栈空

进栈

出栈

读取栈顶元素

顺序栈

共享栈

两栈共享空间

应用

通常当两个栈的空间需求有相反关系时(一个栈增长时另一个栈在缩短的情况)，
就像买卖股票一样，你买入时，一定有一个你不知道的人在做卖出操作，有人赚钱就一定有人赔钱

前提：相同数据类型的栈

操作

栈满：top1+1=top2

入栈：需要插入元素和栈号参数(指定入哪个栈)

出栈

代码

数组实现

栈顶top指针从0开始(看个人习惯)

链式存储结构

计算栈的当前容量

计数器中会有一个指针指向栈顶，一个int类型的Count变量记录栈的当前容量。

链式存储

链栈、链式栈

栈顶放在单链表头部，无需头结点
top指针就是头指针

操作

链栈

链式

栈的实现

栈的顺序实现

常用名词

顺序栈—— 即栈的顺序实现

栈容量——栈中可存放的最大元素个数

栈顶指针

栈空

栈满

下溢——当栈空时，再要求作出栈运算，则称“下溢”；

上溢——当栈满时，再要求作进栈运算，则称“上溢”

顺序栈的类型定义

顺序栈的运算

（1）初始化栈：InitStack(S);

（2）判栈空：EmptyStack (S);

（3）进栈：Push (S,x);

（4）出栈：Pop (S);

（5）取栈顶： GetTop(S);

栈的链接实现

1、链栈的定义

栈的链式存储结构称为链栈，它是运算受限的单链表，
插入和删除操作仅限制在表头位置上进行。栈顶指针就是链
表的头指针

基本操作

（1）初始化栈：InitStack(S);

（2）判栈空：EmptyStack (S);

（3）进栈：Push (S,x);

（4）出栈：Pop (S);

（5）取栈顶： GetTop(S);

栈的简单应用、用途、适用场景、案例

暂时保存有待处理的数据

递归调用

实现递归功能

(1)递归的定义

函数在完成之前又调用自身，则称之为
递归函数

(2)递归的一般形式

递归

斐波那契数列

例如斐波那契数列

递归调用

时间复杂度计算

dfs广搜

出栈序列

不可能序列

序列种类数

可能序列

两栈共享空间

四则运算表达式求值

四则运算

表达式计算

表达式求值

前缀/波兰表达式

中缀

后缀/逆波兰表达式

转换方法

计算方法

表达式树

逆波兰表达式（RPN）

逆波兰表达式求值问题

就是不用任何括号的后缀表达式。每遇到一个运算符就取该运算符的前面两个数据进行运算。

例如：（1-2）*（4+5）=1 2-4 5+*（数字的顺序不能改变）

中缀表达式转换为后缀表达式（逆波兰表达式）

利用栈的特性进行转化，当遇见一对括号时就要先将里面的完成，因为括号内的是独立运算是独立的。当运算符进栈时要根据运算符的优先级进行排序，优先级高的在栈顶，优先级低的在栈底。

中缀表达式转后缀表达式

函数调用栈

浏览器前进后退

浏览器的后退键、编辑软件的撤销键(undo)

括号匹配问题

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效

利用栈

括号匹配

单调栈

单调递增栈：从栈顶到栈底递增

单调递减栈：从栈顶到栈底递减

应用场景：找到每一个数左边(右)离它最近且比它小(大)的数

原理：剔除一些永远用不到的元素(逆序关系)，剩下单调的元素

代码

栈的最小深度

数值转换

函数局部变量存储

栈的存储结构示意图

优先队列

最大优先队列

最小优先队列

索引优先队列

数组（Array）

数组的定义

数组(Array)

顺序存储：数组

类型都是数字

特殊的线性表，表中的数组元素本身也是一种线性表

线性表的扩展，表中数据元素也可以是一个数据结构

是线性表的推广，其每个元素由一个值和一组下标组成，其中下标个数称为数组的维数

线性表推广，多维=数组矩阵

C语言存储默认下标为0

广义表的定义

类型不相同

链式存储

数组的基本操作

Insert——在指定索引位置插入一个元素

Get——返回指定索引位置的元素

Delete——删除指定索引位置的元素

Size——得到数组所有元素的数量

数组的缺点

大小固定，创建后无法扩容

只能存储一种类型数据

添加删除速度慢

查询时需要进行全表扫描，获取数据

数组数据查询时，需要将数据全部加载到内存，如果数据量较大，占据大量内存。

数组的优点

索引

按照索引，查询/遍历速度快

数组的特点

内存空间连续

扩容麻烦

时间复杂度

增删

查询

支持下标查询

结构固定：
定义后维数和维界不再改变
因此对数组的操作通常不做插入和删除，只做读取和修改

数组的适用场景

频繁查询

查询频繁而增删减较少的场景

对存储空间要求不大

很少增加和删除

频繁查询，数据量不大，少增删操作

类型

一维数组

LOC(ai)=LOC(a0)+(i)xL

存储结构关系式

定义

一维数组：线性表中的数据元素为非结构的简单元素

逻辑结构

线性结构。定长的线性表

多维数组

二维数组

一维数组中的数据元素又是一维数组结构

逻辑结构

严格上来说多维数组不是线性结构，
也可以说线性表结构是数组结构的一个特例(一维)
而数组结构又是线性表结构的扩展(扩展到二维三维等)

顺序存储结构

以行序为主序

以列序为主序

存储位置推算式
LOC = LOC + (n*(i - 0) + （j - 0）)*c

三维数组按页/行/列存放

n维地址计算

存储结构

行优先

先行后列

存储关系式

......

先行后列
行号 i = x // col(列数);
列号 j = x % col;

列优先

先列后行

存储关系式

先列后行
列号 j = x // row(行数);
行号 i = x % row;

由于计算机存储数据元素内存单元地址是一维的，所以多维数组需要将多维结构映射到一维结构

数组矩阵

矩阵元素下表与一位数组下标换算

地址求行长

矩阵的压缩存储

指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间

特殊矩阵
特殊矩阵的压缩
特殊矩阵的压缩存储

对称矩阵

下标转换公式

定义

在n × n的矩阵a中，满足 = （1 ≤ i ，j ≤ n）

存储方法

以行序为主序将元素存放在一个一维数组中SA[n*(n+1)/2]中

n*n个存储单元 --> n*(n+1)/2个存储单元

访问

的一维索引k值：i×(i - 1)/2+(j-1)

如果需要访问上三角的元素，因为 = ，把i=j ，j=i带入上式，即
k = j×(j - 1)/2+(i-1)

三角矩阵

定义

主对角线以上(或者以下)的数据元素(不包括主对角线)均为常数c

存储方法

非常数三角存储与对称矩阵一样存储到一个一维数组中，重复元素c共享一个元素存储空间
SA[n*(n+1)/2+1]

n*n个存储单元 --> n*(n+1)/2+1个存储单元

访问

下三角矩阵

上三角矩阵

这里数组索引从0开始，常数c放在最后一位

三角矩阵

下标转换

对角矩阵
三对角矩阵

三对角矩阵

下标转换

带状矩阵

稀疏矩阵
稀疏矩阵的压缩存储

稀疏矩阵定义

矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，

通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵(sparse matrix)，

该比值称为这个矩阵的稠密度；

与之相区别的是，如果非零元素的分布存在规律（如上三角矩阵、下三角矩阵、对角矩阵），则称该矩阵为特殊矩阵。

存储方式

三元组
三元组顺序表法

三元组：(行号，列号，非零元素值)

三元组表：将非零元素对应对的三元组所构成的集合，以行序为主序排列成一个线性表

代码

若要唯一标识一个稀疏矩阵，还需要在存储三元组表的同时存储该矩阵的行数、列数和非零元素个数
为了方便操作，这一组数据存在索引0的位置(也可以存在末位)

优缺点

三元组顺序表又称有序的双下标法。

优点：非零元在表中按行序存储，因此便于进
行依行顺序处理的矩阵运算。

缺点：不能随机存取。若按行号存取某一行中的非
零元，则需从头开始进行查找。对于矩阵的加法、乘法等操作，非零元素个数和位置都会发生变化，则在表中就要进行插入和删除操作，顺序存储十分不方便

十字链表
十字链表法

在三元组的基础上增加了两个域
right：指向同一行中的下一个三元组结点
down：指向同一列中的下一个三元组结点

代码

优点

能够灵活地插入或删除因运算二产生新的非零元素，实现矩阵的各种运算

数组

3.3.1数组的逻辑结构和基本运算

读

写

3.3.2数组的存储结构

顺序存储结构

寻址公式

3.3.3矩阵的压缩存储

特殊矩阵

1、对称矩阵

元素总数

∑(i)=n(n+1)/2

下标变换公式

2、三角矩阵

上三角矩阵

下三角矩阵

稀疏矩阵

三元组(i,j,aij)

三元组表结构：

数组

旋转数组

将数组中的后k位，移到数组的开头

利用首尾交换实现，先全部翻转，然后分别翻转0到k-1和k到数组末尾

二分查找

滑动窗口

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0

链表（Linked List）

概念

链表（Link）

比如，Java中我们使用的ArrayList，其实现原理是数组。

而LinkedList的实现原理就是链表了。

链式存储：链表

链表(Linked List)

链表是一种数据结构，和数组同级。

链表不使用大内存，查询时仍然需要进行全表扫描

链表在进行循环遍历时效率不高，但是插入和删除时优势明显。

链表是另一个重要的线性数据结构

链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。

链表的特点

内存空间不连续

时间复杂度

增删

查找

结点

数据

指针

链表的基本操作

删除

根据值删除

根据node删除

Delete - 从链接列表中删除指定元素

DeleteAtHead - 删除链接列表的第一个元素

插入

中间插入

头部插入

InsertAtHead - 在链接列表的开头/头部插入指定元素

尾部插入

InsertAtEnd - 在链表的末尾插入指定元素

查找

根据值查找

根据node查找

Search - 从链表中返回指定元素

遍历

长度

isEmpty - 如果链表为空，则返回true

链表的高级操作

检测环

链表反转

两个有序的链表合并

求链表的中间结点

删除链表的倒数第n个结点

判断链表是否符合回文结构

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

链表的分类

动态链表

单向链表

循环链表

静态链表

创建

注意

优点和缺点

动态链表和静态链表的区别

静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。

静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。

动态链表是用内存申请函数（malloc/new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。

链表的种类、类型

单向链表

单链表

定义：就是每个节点只有一个指针域。

单链表

空链表

头指针和头节点

头指针

是链表指向第一个节点的指针，如果该链表有头节点，那么该指针就是指向头节点的指针。

头指针具有标识的作用，所以常以头指针冠以链表的名字（指针变量的名字）。

无论链表是否为空，头指针均不为空。

头指针时链表的必要元素。

头节点

头节点是为了操作的统一和方便而设立的，放在第一个节点之前，数据域一般无意义（可以存储链表的长度）。

有了头节点再第一个节点前插入或者删除第一个节点都会和其他的节点操作一致。

头节点不是必要的元素。

C语言代码节点定义示例

特点：读取的时间复杂度为O(n);插入和删除的复杂度O(1);

插入思路

删除思路

整表删除

优点：对于每次插入和删除操作越频繁越多的操作单链表的优势就会更加明显。

头插法：就是新插入的元素插在最前面。优点：插入简单。缺点：插入的顺序和逻辑顺序不同。

尾插法：就是新插入的元素插在最后面。

单链表

一个指针域

单链表（单向）

单链表

双向链表

两个指针域

双向链表（双向）

双向链表

循环链表

单循环链表

定义：单链表得最后一个节点指向头节点。

注意：判断空表是Head的Next是否为head。

双向循环链表

定义：就是有两个指针指向前驱节点和后继节点。

插入

删除

注意：循环链表不一定有头节点

循环链表

单链表只能向后指，而循环链表可以向前向后

一个指针域

循环链表

图解三种链表

适用场景、应用、作用

增删频繁而查询较少的场景

计算机内存连续片段较少的场景

邻接表

哈希表

文件系统

数据量较小

需要频繁增加删除

链表的复杂度分析

其他

双向循环链表

相交链表

编写一个程序，找到两个单链表相交的起始节点

利用双指针，当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB到达链表的尾部时，将它重定位到链表 A 的头结点

环形链表

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况

利用hash表判重，还可以使用快慢指针

反转链表

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null

链表反转

两两交换链表中的节点

虚拟头节点

删除链表的倒数第N个节点

快慢指针+虚拟头节点

快慢指针

中间值问题

单向链表是否有环问题

有环链表入口问题

队列（Queue）

队列的定义、基本概念？队列是什么？

队列(Queue)

队列（queue）

队头指针

头结点

队尾指针

队列是一种特殊的线性表

先进先出的线性表

只允许在表的一端进行插入，而在另一端进行删除的线性表

在队头弹出，在队尾插入

定义：是在一端进行插入操作，在另一端进行删除操作的一个线性表。

队列是只允许在一段进行插入操作，而在另一端进行删除操作的线性表

特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

和栈一样，队列是一种操作受限制的线性表。

进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的基本操作

队列初始化 InitQueue(Q)

初始化

销毁

入队列 EnQueue(Q,x)

Enqueue()——在队列尾部插入元素

插入在尾部进行

入队

出队列 OutQueue(Q)

出队

Dequeue()——移除队列头部的元素

出队在头部进行

判队列空 EmptyQueue(Q)

isEmpty()——如果队列为空，则返回true

判空

取队列首元素GetHead(Q)

Top()——返回队列的第一个元素

读取队头元素

适用场景、用途、队列应用

二叉树层次遍历

出队序列计算

做题时可标注左右进入的序列

FIFO性质

OS缓冲区

CPU资源分配

页面替换算法

多线程阻塞队列管理

常用于暂时保存有待处理的数据

单调队列

应用场景：窗口滑动

原理和单调栈一致
都是去除一些永远用不到的元素
使得整个队列(栈)为单调递增(递减)

思想

代码

思考的问题

为什么队列储存元素的索引而不是数值本身

为什么四行代码的顺序不能颠倒

为什么队列存储了窗口内从最小值到队尾元素的一个升序子序列

为什么维持窗口长度的那行代码使用了if，而不是whlie

使用STL库

线程池队列

消息队列

kafka

rabbitmq

队列的特性、特点

先进先出

先进先出（FIFO）

先进先出（First In First Out，FIFO）

FIFO（先进先出）

队列：先进先出

先进先出FIFO（First In First Out）

先进先出

吃多了拉

队列的存储结构

顺序存储结构

1、顺序队列

普通队列

数组实现

算法上一般队列装的是索引值，而不是元素值
而且写算法时我们只考虑移动指针，不用考虑元素出队后真正的删除
这样出队入队时间复杂度都是O(1)

普通队列，习惯tail从-1开始，head从0开始，head==tail时，队列内有一个元素

在上面两点的基础下
当前队列的长度就为tail-head+1

如果head，tail都从0开始，队长为tail-head

这里队列存放的是元素值，如果队头出队后，队列中所有元素都得向前移动，时间复杂度为O(n)

——只能从数组的一头插入、另一头删除。
SeqQue sq ；
·上溢条件：sq.rear = = maxsize-1 ( 队满 )
·下溢条件：sq.rear = = sq.front (队列空

顺序存储

2、循环队列

循环队列

如果普通队列队头出队后不将后续元素往前移动，那么会出现"假溢出"现象
如果还想要O(1)的时间复杂度，又不想出现这种情况，那么就需要循环队列来实现

定义：头尾相接的顺序存储结构称为循环队列

循环队列出现head==tail的情况会有两种
1、队列为空
2、队列满

如何处理：
方法一：设置一个标志变量flag，当head==tail，且flag==0，队列为空
当head==tail，且flag==1，队列满
方法二(重点)：修改队列满条件，保留一个元素的空间

操作

初始化

注意：head指针指向队头，tail指针指向队尾元素的下一位
指针指的是索引值

入队

出队

队长

通用的计算队列长度公式
(tail-head+QueueSize)%QuqueSize

队满

条件：(tail+1)%QueueSize==head
因为head可能比tail小，可能比tail大，可能是相差一个位置为满，但也可能相差整整一圈
如上图(4+1)%5==0,(1+1)%5==2

队列的顺序实现—循环队列

定义

队列容量

队头指针front

队尾指针 rear

初始： front=rear=0

进队： rear增1，元素插入尾指针所指位置

出队： front增1，取头指针所指位置元素

假溢出

循环队列

实际上不存在环形的存储结构，可以用顺序表模拟出来。

基本运算

队列初始化 InitQueue(Q)

判队列空 EmptyQueue(Q)

入队列 EnQueue(Q,x)

出队列 OutQueue(Q)

取队列首元素GetHead(Q)

区分队空还是队满

牺牲一个单元来区分队空和队满

队满

(Q.rear+1)%MaxSize==Q.front

队空

Q.front==Q.rear

队列元素个数

(Q.rear-Q.front+MaxSize）%MaxSize

类型中增设表示元素个数的数据成员

队满

Q.size==MaxSize

队空

Q.size==0

两种情况都有

Q.front==Q.rear

类型中增设tag数据成员

队满

tag=1

因插入导致Q.front==Q.rear

队空

tag=0

因删除导致Q.front==Q.rear

将一块存储空间(数组表示)看成头尾相连接的队列
typedef struct Cycqueue
{
DataType data[maxsize];
int front,reat; }CycQue;
CycQue CQ;
★规定：循环队列CQ
下溢条件即队列空： CQ.front==CQ.rear
上溢条件即队列满：尾指针从后面追上头指针
即：(CQ.rear+1)%maxsize==CQ.front （尾赶头）
（浪费一个空间，队满时实际队容量=maxsize-1）

当队头为0时

在出队操作时，每个元素都要往前进行移动，时间复杂度高，不太实用。

当队头是指针时

可能会造成越界（越过最大值）。

链式存储结构（常用）

链队列：其实就是线性表的单链表，只不过只能尾进头出
带头结点

操作

队空

入队

出队

队长

链队列和循环队列比较

销毁队列：因为队列一般是动态的存储在内存，所以一般不使用时要进行及时的清除所占用的内存。

队列的链式实现

定义

用链表表示的队列，即它是限制仅
在表头删除和表尾插入的单链表
附设两指针：
头指针front——指向表头结点；队头元素结点为front->next
尾指针 rear——指向链表的最后一个结点（即队尾结点）
▲链式队的上溢：可不考虑；（因动态申请空间）
▲链式队的下溢：即链式队为空时，还要求出队
规定：链队列空时，令rear指针也指向表头结点。
链队列下溢条件：
LQ.front->next==NULL 或
LQ. front==LQ. rear；

类型

typedef struct LinkQueueNode
{DataType data;
struct LinkQueueNode *next;
} LkQueNode；
typedef struct LkQueue
{ LkQueue *front ,*rear;
} LkQue;
LkQue LQ ;

基本操作

队列初始化 InitQueue(Q)

判队列空 EmptyQueue(Q)

入队列 EnQueue(Q,x)

出队列 OutQueue(Q)

取队列首元素GetHead(Q)

队空

Q.front==NULL 且 Q.rear==NULL

链式存储

链式队列

双端队列

图解队列结构

队列的分类、类型

顺序队列

链式队列

普通队列

环形队列

双端队列

两端都可以进行入队和队

阻塞队列

并发队列

并发加锁队列

并发无锁队列

阻塞并发队列

循环顺序队列

循环队列包含的属性

front(队首指针)

rear(队尾指针)

Object[] queueElem (队列储存空间)

flag（标记）

num（计数器）

构造方式

少用一个存储单元

判空：front==rear

判满：front==(rear+1)%maxSize

求队列长度：(rear-front+length) % length

入队

修改队尾指针：rear=(rear+1) % length

出队

修改队首指针：front= (front+1) % length

设置一个标志变量(flag)

判空: front==rear && flag==0

判满：front==rear && flag==1

入队

修改队尾指针：rear=(rear+1) % length

修改标志（flag=1）

出队

修改队首指针：front= (front+1) % length

设置标志（flag=0）

设置一个计数器（num）

判空：num=0

判满：num>0 && front==rear

入队

修改队尾指针：rear=(rear+1) % length

++num

出队

修改队首指针：front= (front+1) % length

--num

循环队列

front指针：指向对头元素

rear指针：指向队尾元素的下一个位置

单调队列

单调递增队列：从队头到队尾递增

单调递减队列：从队头到队尾递减

应用:滑动窗口问题

其他

第2章线性表

2．1 线性表的定义和基本操作

导图

2．2 线性表的顺序表示

导图

2．3 线性表的链式表示

导图

上

中

下

一般线性表

类型定义

逻辑结构

抽象数据类型

顺序存储

顺序表

链式存储

单链表

双向链表

循环链表

静态链表（借助数组实现）

非受限线性表

顺序结构

数组

支持O(1)的随机访问

平均为O(n)的插入和删除

警惕数组越界错误，导致stack over flow

链式结构

单链表

不支持随机访问，需要遍历去访问节点

插入和删除只需要移动节点，时间复杂度为O(1)

每个节点需要额外的内存存储指针地址，需要的空间比数组大

双链表

在单链表的基础上，除了头节点，其余每个节点，多了一个存储前驱节点内存地址的指针

循环链表

尾节点指针指向头节点

静态链表

借助数组，伴随指向后继节点的指针

受限线性表

堆

大顶堆

小顶堆

实际应用

找第K大的元素

栈

顺序和链式都可以实现，先进后出

实际应用

浏览器的前进和后退

括号匹配

表达式计算

栈

抽象数据类型

顺序栈

多栈共享

链栈

多栈运算

应用

括号补全

表达式求值

栈与递归的实现

汉诺塔递归算法

斐波那契数列的非递归算法

队列

普通队列

顺序和链式都可以实现，先进先出

双边队列

入口和出口都可以进队和出队

优先级队列

根据优先级来出队

实际应用

LRU Cache

队列

抽象数据类型

链队列

循环队列

应用举例

打印杨辉三角

键盘输入缓冲区问题

串

抽象数据类型

定长顺序串

布鲁特福斯算法

堆串

快链串

串的应用

简单的行编辑器

顺序表

顺序表的实现

顺序表的遍历

顺序表的容量可变

顺序表的时间复杂度

Java 中 ArrayList 实现

特殊矩阵的压缩存储

基本方法（函数）

栈与队列

都是特殊的线性表，只不过对插入和删除操作做了限制

图（Graph）

图的入门、基本概念及定义

图是由什么组成

结点的有穷集合V

边的集合E

图是一组以网络形式相互连接的节点。

由集合V和E组成

V — 顶点集

在图结构中常常将结点称为顶点

例：V(G1)={ 1， 2， 3， 4 }

节点也称为顶点。

E — 边集

边是顶点的有序偶对

若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系

例：E(G1)={ (1,2)， (1,3)， (1,4)， (2,3)， (2,4)， (3,4) }

一对节点（x，y）称为边（edge），表示顶点x连接到顶点y。

G=（V， E）

图的基本概念及相关术语

简单图、多重图

简单图：无自环，无重复边

简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图

多重图：有自环，重复边

完全图

简单图的边数达到上限

无向

边数=n*(n-1)/2

有向

边数=n*(n-1)

子图

边和顶点均为子集且能够形成一张图

子图：假设有两个图G=(V,{E}),G'=(V',{E'})，如果G'⊆G且E'⊆E,则称G'为G的子图

距离

定点

顶点

<Vi,Vj>

邻接

关联

边(Vi,Vj)关联于顶点Vi和Vj; 是指边与顶点间的关系

边的权和网

权

权：与图的边或相关的数称为权

网

网：带权图

带权的图通常称为网

边上带权重的为带权图

顶点度，入度和出度

顶点的度

顶点度：无向图中顶点所连边数

度：与顶点相关联的边的个数

有向图

出度OD(Vi)

入度ID(Vi)

无向图

稠密图、稀疏图

稀疏图：有很少边或弧的图

稠密图：有很多边或弧的图

连通、连通图和连通分量

连通

从顶点Vi到Vj顶点有路径

无向图

连通：u,v之间存在路径

连通图

每对顶点间都连通

连通图：图中任意两点均连通

连通分量

极大的连通子图

连通分量：无向图中极大连通子图

有向图

强连通:有向图中的u,v互相可达

强连通图

每对顶点间都连通

强连通图：有向图中任意两点互相可达

强连通分量

极大的连通子图

强连通分量：有向图中极大墙连通子图

生成树、生成森林

生成树

极小连通子图
若连通图G的顶点个数为n，则G的生成树的边数为n-1。

生成树：包含图中全部顶点的一个极小连通子图

生成森林

生成森林：非连通图中连通分量的生成树构成了生成森林

极小连通子图：保持图的联通性，又使得边数尽可能少

路径、路径长度和回路

路径

顶点序列【由顶点和相邻顶点序偶构成的边所形成的序列】

路径长度

路径上边或弧的数目

路径长度：路径上边或弧的数目

回路/环

有环（可多个）

回路(或环)：第一个顶点到最后一个顶点相同的路径称为回路

路径中第一个和最后一个顶点相同

简单路径、简单回路

简单路径

除第一个和最后一个外，其余各顶点均不相同的路径

序列中顶点不重复出现的路径

在路径序列中，顶点不重复出现的路径

简单回路

只有一个闭环

出第一个顶点和最后一个顶点外，其他顶点不重复出现的回路

在路径序列中，除第一个和最后一个顶点外，其余不重复出现的回路

无向

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi,Vj)表示

无向图：图中任意两顶点的边都是无向边，则称该图为无向图

无向完全图：在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图

顶点的度：顶点v的度是和顶点v相关的边的数目(记为TD(v))。边数等于各顶点度之和的一半

连通图：如果从顶点v到v'有路径，则称v和v'是连通的，如果图中任意两个顶点都是连通的，则称图是连通图

连通分量

无向图中的极大连图子图称为连通分量

连通分量要求：
1.要是子图
2.子图要是连通的
3.连通子图含有极大顶点数
4.具有极大顶点数的连通子图包含依附于这些顶点的所有边

生成树：无向图中连通且n个顶点和n-1条边的叫生成树

无向图森林：n个顶点，e条边的无向图森林树的个数

有向

有向边：若顶点Vi到Vj之间的边有方向，则称这条边为有向边，也称为弧，用有序偶对<Vi,Vj>,Vi称为弧尾，Vj称为弧头

有向图：图中任意两顶点的边都是有向边，则称该图为有向图

有向完全图：在有向图中，若任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图

入度：以顶点V为头的弧的数量称为，顶点V的入度(记为ID(v))

出度：以顶点V为尾的弧的数量称为，顶点V的出度(记为ID(v))

强连通图：是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。

定理：一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次

强连通分量：有向图中的极大强连通子图称做有向图的强连通分量

有向树：有向图中一个顶点入度为0的，其余顶点入度为1的称为有向树

生成森林：一个有向图的生成森林由若干个有向树组成，含有图中所有顶点，但只有足以构成若干棵不相交的有向树的弧

图的分类、类型

有向图

有向图的定义及相关术语

例：
V(G3)={ 1， 2， 3 }
E(G3)={ <1,2>， <2,1>， <2,3> }

有向图 API 设计

有向图实现

拓扑排序

检测有向图中的环

基于深度优先的顶点排序

带权有向图

最短路径

求某顶点到其他各顶点的最短路径

Dijkstra(迪杰斯特拉)算法

dist[]

记录所求点v0到其他各顶点的当前最短路径长度

path[]

记录所求点v0到其他各顶点的最短路径的前驱结点

步骤

初始化dist数组，若v0到其他各点有弧，则将dist对应位置赋与对应的权值，否则设为∞（无穷可自己约定一个数字代表无穷）

从dist中选择数字最小且未被选择过的点vj，则此时认为已找到v0到vj的最短路径

已vj为中转点计算v0到其余各点距离，若小于dist中的值，则更新

重复2，3操作

与Prim普里姆算法类似，时间复杂度也为

边上带有负权值时不适用

求所有顶点间的最短路径

Floyd(弗洛伊德)算法

递推产生n阶方阵序列，存储顶点之间的最短路径长度

步骤

初始化，将该图的邻接矩阵赋值给方阵序列

依次将各顶点加入中间顶点，并更新方阵序列的值

时间复杂度

允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路

Dijkstra和Floyd同样能求解带权无向图的最短路径，因为带权无向图可视为权值相同往返二重边的有向图

加权有向图

加权有向图边的表示

加权有向图的实现

有向图

强连通图

强连通分量

弧头(顶点)

弧尾(顶点)

无向图

连通图

连通分量

加权无向图

加权无向图边的表示

加权无向图的实现

带权无向图

最小生成树

Prim(普里姆)算法

每次选点

初始任选一点加入树T，之后选择一个与当前T中顶点集合距离最近的顶点

时间复杂度

适合求解边稠密的图

Kruskal(克鲁斯卡尔)算法

每次选边

选择权值最小且未被选取过的边，若加入该边后形成回路则舍弃该边

时间复杂度

适合求解点稠密边稀疏的图

无向图

例：
V(G1)={ 1， 2， 3， 4 }
E(G1)={ (1,2)， (1,3)， (1,4)， (2,3)， (2,4)， (3,4) }

图的存储及基本操作
图的表示、图的基本存储结构

邻接矩阵法

邻接矩阵表示法

表示图的各顶点之间关系的矩阵

无向图

对称矩阵

顶点和度的关系

无向图

有向图

矩阵

顶点和度的关系

有向图

带权图(网)

缺点

占用空间太大

邻接矩阵

性质

图的邻接矩阵就是用两个数组来表示图，一个一维数组存储图中顶点集合，一个二维数组(邻接矩阵)存储图中边或弧的关系

邻接矩阵（顺序存储）使用两个数组分别保存顶点集和边集

邻接表法

邻接表

邻接表法

利于稀疏图的存储
寻找是否存在 u->v的边时需要遍历，复杂度为O(n), 而邻接矩阵为O(1)

邻接表法

邻接表表示法

邻接表是将数组和链表结合起来的存储方法

1.图中的顶点用一个一维数组存储，对于顶点数组中，每个元素还需要存储指向第一个邻接点的指针，以便查询边的信息

2.图中每个顶点Vi的邻接点构成一个线性表，由于邻接点个数不定，所以用单链表存储，无向图称为顶点Vi的边表，有向图称为以顶点Vi为弧尾的出边表

邻接表（链式存储）（不唯一）

示例图

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

结论

无向图

n个顶点、 e条边，链表结点2e

i链结点数=Vi的度

有向图

i链结点数=Vi的出度

3.省单元

4.效率高

邻接多重表

邻接多重表（无向图）

无向图存储结构

重新定义邻接表的边表结点,

结构为(ivex,ilink,jvex,jlink)

其中ivex和jvex表示依附某条边的两个顶点在顶点数组中的下标

ilink指向依附顶点ivex的下一条边

jlink指向依附顶点jvex的下一条边

逆邻接表

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

十字链表

十字链表（有向图）

1.顶点数组中每个元素包含，data，firstin，fristout

2.单链表中每个结点包含：tailvex，headvex，headlink，taillink

十字链表

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

十字链表

边集数组

由两个一维数组组成

一个一维数组存储图中顶点集合

另一个数组存储边的信息

这个边数组的每个元素由一条边的起始下标，终点下标和权重组成

图的搜索与遍历

图的搜索

深度优先搜索

广度优先搜索

图的遍历

遍历算法、方法

广度优先遍历（BFS）

广搜bfs

广度优先BFS

广度优先遍历（BFS）

性能分析

求解最短路问题

广度优先生成树

利用队列实现

广度优先遍历

广度优先搜索法

广度优先搜索

广度优先BFS

性能分析

求解最短路问题

广度优先生成树

分析

重复标志向量
visited [n];

邻接矩阵或邻接表表示

队列

先进先出

深度优先遍历（DFS）

深度优先遍历

利用栈实现

性能分析

生成树

深度优先搜索法

深度优先搜索

性能分析

生成树

深搜dfs

深度优先DFS

深度优先（DFS）

算法分析

标志向量visited [n]

邻接矩阵或邻接表表示

栈

递归性

时间复杂度

邻接表

O(n+e)

邻接矩阵

O(n2)

遍历

从图G中某一顶点v出发，顺序访问各顶点一次。

连通图搜索法

辅助数组visited[n]

图的实际应用

拓扑排序

定义

有向图

无回路

有序序列个数

有向无环图（DAG图）

一个有向图中不存在环

Directed Acyclic Graph

有向无环图描述表达式

有向无环图表达式

描述含有公共子式的表达式的有效工具

共享相同子式，节省存储空间

所得有向无环图操作数不会重复

得到对应有向无环图的步骤

AOV网

AOV网络

AOV-网

AOV网：顶点表示活动的网（有向无环图）

拓扑排序

不断删除入度为0的顶点

拓扑排序算法可用于判断一个图是否有环

DFS实现

拓扑排序
1）找到没有前驱结点/入度为0结点输出
2）删除其相关联的有向边
3）重复 1）、2）

逆拓扑排序

不断删除出度为0的顶点

DFS实现

逆拓扑排序
1）找到没有后继结点/出度为0结点输出
2）删除其相关联的有向边
3）重复 1）、2）

时间复杂度

邻接矩阵存储时为

邻接表存储时为

小结

若图有环则不存在拓扑排序、逆拓扑排序

若图的邻接矩阵是三角矩阵，则存在拓扑序列，反之不一定成成立。

若图的邻接矩阵为三角矩阵，且对角线以上的元素均为1，以下的均为0，则拓扑序列唯一。

每个顶点出入度最多唯一，则该图拓扑序列唯一，反之不一定成立

拓扑序列唯一，不能唯一确定该图

AOE网

开始顶点（源点）

表示工程的开始

结束顶点（汇点）

表示工程的结束

关键路径

求解步骤

求事件最早发生时间ve(k)

从源点出发，令ve(源点)=0，按拓扑排序求其余顶点ve()

求事件最晚发生时间vl(k)

从汇点出发，令vl(汇点)=ve(汇点)，按拓扑排序求其余顶点ve()

求活动最早开始时间e(i)

等于活动弧的起点事件的最早发生时间ve(k)

求活动最晚开始时间l(i)

等于活动弧的终点事件的最迟发生事件vl(k)减去该活动的权值

求活动的差额d()，d()=0的活动即为关键活动

用l(i)-e(i)

小结

工程完成的最短时间是关键路径的长度

可通过加快关键活动来缩短工期，但不能任意缩短，因为缩短到一定程度，关键活动可能变成非关键活动

若有几条关键路径，则加快包括在所有关键路径上的关键活动才能缩短工期
或者说只有所有关键路径上的活动时间同时减少时，才能缩短工期

例图

时间复杂度

邻接表

O(n2)

O(n+e)

关键路径

AOE网

有向图的边表示活动的网，具有最大长度的路径叫关键路径

事件最早发生时间

拓扑序求最早事件发生时:
即**前驱任务最晚完成后**立刻开始
max(ve(j)+W(vj,vk))

事件最迟发生时间

逆拓扑序求最晚事件发生时
即后继时间固定，**前驱时间最迟开始**时间

活动最早开始事件

活动最晚开始时间

时间余量

时间余量为0的边，则为关键活动

最短路径

无权图

广度优先算法

带权图

迪杰斯特拉算法

多源最短路径

佛洛依德算法

最短路径定义及性质

松弛技术

算法

Dijkstra算法

迪杰斯特拉

Dijkstra

贪心，维护点集合，类似Prim算法

迪杰斯特拉算法

最短路径（dijkstra算法）

Dijkstra算法

算法实现

缺点：不能求解负权图

Floyd算法

费洛伊德

弗洛伊德算法

Floyd

算法思想：对于图(邻接矩阵)而言，选择起点i,终点j,遍历寻找是否有中间结点k能够使得 (i->k->j) < (i->j)的长度，这样就可以更短

缺点：时间复杂度高

生成树

深度

广度

最小生成树（MST）

最小生成树定义

n点，n-1边

带权

边的权总和最小

包含图中所有顶点，并且只含尽可能少的边，所形成的树(特殊的图)

最小生成树（不唯一但权值和相同）

最小生成树相关约定

最小生成树原理

树的性质

最小生成树不是唯一的

最小生成树的边和权值之和总是唯一的

最小生成树的边数为顶点数减1

切分定理

最小生成树的构造算法

Prim算法

普里姆算法

普里姆

Prim法

示例图

邻接矩阵图

算法图

Prim算法

Kruskal算法

kruskal 算法

克鲁斯卡算法

克鲁斯卡尔

Kruskal法

Kruskal算法

贪心算法

无向图的连通分量

求简单路径

二分图

最大流

其他

抽象数据类型

图的基本运算

路径查找

漫画：什么是 “图”？（修订版）

位图

位图的原理就是用一个bit来标识一个数字是否存在，采用一个bit来存储一个数据，所以这样可以大大的节省空间。 bitmap是很常用的数据结构，比如用于Bloom Filter中；用于无重复整数的排序等等。bitmap通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。
https://www.cnblogs.com/polly333/p/4760275.html

散列表（Hash）

什么是散列

将关键字映射到存储位置的过程称为散列

什么是哈希法

哈希法（Hashing）是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“键（key）”）中的过程。

组成部分

散列表(Hash)

哈希表

Hash table，也叫哈希表，是一种查找算法

与链表、树等算法不同的是，散列表算法在查找时，不需要进行一系列和关键字的比较操作。

（关键字是数据元素中某个数据项的值，用以标识一个数据元素）

根据键值（key/value）进行访问的数据结构；

通过key/value来映射到集合中的元素，这样可以很快找到集合中的元素

散列函数

散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素，

因而必须要在数据元素的存储位置和它的关键字（可用key表示）之间建立一个确定的对应关系，

使每个关键字和散列表中一个唯一的存储位置相对应。

因此在查找时，只要根据这个对应关系找到给定关键字在散列表中的位置即可。

这种对应关系被称为散列函数(可用h(key)表示)。

冲突

冲突解决技术

链表法

分离链接法

开发寻址、开放寻址

线性探测法

二次探测法

非线性搜索

双重散列法

使用两个散列函数

其他

散列表

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词

排序、hash表

动态扩容

位图

布隆过滤器

布隆过滤器是一种概率数据结构，

用来判断一个元素是否存在于某一个集合中，较好的空间和时间效率。

该方法可以判断一个元素要么肯定不在一个集合中，要么可能在集合中，其基本的数据结构是一个位相量。

直接寻址：给定关键字K，仅通过查看数组的第K个位置就可以找到该元素，这称为直接寻址。

通用惯例：当关键字实际存储数目相对于给关键字的取值范围较小时可以使用散列表(存储位置少，关键字数目多)。

负载因子(体现散列表是否均匀分布)：
散列表中元素个数/散列表长度

用的构造散列函数的方法有

（1）直接定址法

取关键字或关键字的某个线性函数值为散列地址。

即：h(key) = key 或 h(key) = a * key + b，其中a和b为常数。

（2）数字分析法

（3）平方取值法

取关键字平方后的中间几位为散列地址。

（4）折叠法

将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址。

（5）除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址，

即：h(key) = key MOD p p ≤ m

（6）随机数法

选择一个随机函数，取关键字的随机函数值为它的散列地址，

即：h(key) = random(key)

散列表（Hash Table）、Hash、Hash算法

hash函数,散列分布

复杂度O(1)

精确查找快, 不支持范围查找

hash、hash算法

类似于Java中的HashMap，字段的值通过hash函数进行散列，然后使用链地址法解决hash冲突

可以快速进行等值查询，但是涉及到范围查找，只能进行全表扫描

在特定使用常见下合适，不适合大规模使用

性能因素

哈希函数

哈希表的大小

碰撞处理方法

树（Tree）

树Tree和森林Forest

树的定义

树是n(n>=0)个结点的集合，n=0时是空树。对于任意非空树：
1.有且仅有一个特定的称为根的结点；
2.当n>1时，其余结点可分为m(m>=0)个互不相交的有限集，其中每一个集合本身又是一棵树，并称为根的子树

树和森林的前根遍历和后根遍历结果，与将树和森林转化为二叉树后的前序遍历和中序遍历结果相同

树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。

区分树和图的重要特征是树中不存在环路。

递归是树的固有特性

该思维导图就是一个树形结构

N(N>=0)个结点的有限集合

空树

N=0

非空树

N!=0

有且仅有一个特定的称为根的结点

N>1时，其余结点可分为m(m>0)个互不相交的有限集合，其中，一个集合本身又是一棵树，并且称为根结点的子树

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

定义：树（Tree）是n(n>=0)个节点的有限集。n=0时成为空树。在任意一颗非空树中：
（1）有且只有一个特定的成为根（Root）的节点；
（2）当n>=1时，其余节点可分为m（m>0）个互不相交的有限集合T1、T2、T3、...、Tm,其中每个集合本身又是一颗树，并且称为根的子树（SubTr ee）。
注意：1、n>0时根节点是唯一的，不可能存在多个根节点。2、m>0时，子树没有数量限制，但是不能相交。

n(n>=0)个结点的有限集T
(1)当n=0时，称为空树；
(2)当n>0时，有且仅有一个根结点，m(m>=0)个互不相交的子集

树的基本术语、相关术语、相关概念、基本概念

度

度：结点拥有的子树数称为节点的度

结点的度

树中一个结点的子节点个数

结点的度

节点的度

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

树的度

树中结点的最大度数

树的度：树的度是树内各结点度的最大值

树的度

结点

除根结点以外各结点只有唯一前驱

节点分类

节点是一个包含数据元素和若干指向其子树的分支。节点所拥有的子树数成为节点的度（Degree）。

度为0的节点被称为叶节点（Leaf）或者终端节点。

度不为0的节点称为非终端节点或者分支节点。除了根节点外，分支节点也被称为内部节点。

树的度是树内个节点的度的最大值。

分支结点（非终端结点）

度大于0的结点

度不为0的节点

每个结点的分支数就是该结点的度

分支结点(非终端结点)：度不为0的节点称为分支结点(非终端结点)，除根结点外，分支节点也称内部结点

分支结点

非终端节点/分支节点

非终端结点

叶子结点（终端结点）

度为0的结点

叶结点(终端结点)：度为0的节点称为叶结点(终端结点)

叶子结点

度为0的节点称为叶节点

叶节点/终端节点

叶子（终端结点）

结点层次、结点的层次

节点的层次

结点的层次（Level）

从树根开始定义，根节点为第1层...

从根开始定义起为第一层，其孩子结点为第二层，孩子的孩子结点为第三层，以此类推。

:从跟开始定义起，根为第一层，根的孩子为第二层

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

深度

从跟结点开始自顶向下逐层累加

高度

从叶结点开始自底向上逐层累加

层数/深度

结点深度

树的深度

高度

结点高度

树的高度

树的高度或深度
树的高度（深度）

树中节点的最大层次

树中结点的最大层数

树的深度（高度）: 树中结点的最大层次称为树的深度或高度

深度（Depth）或者高度

树中结点的最大层次被称为树的深度

节点间关系

Root - 根节点

孩子和双亲

孩子和双亲：结点的子树的根称为该结点的孩子。相应的该结点称为孩子的双亲

结点的子树的根成为该结点孩子节点（Child）。相应的该结点也称为孩子节点的双亲（Parent）节点。

双亲（父结点）

Parent - 父节点

孩子（子结点）

Child - 子节点

Leaf - 叶子节点

兄弟

兄弟：同一个双亲的孩子之间互称为兄弟

同一个双亲的结点成为兄弟（Sibling）节点。

Sibling - 兄弟节点

祖先

祖先：结点的祖先是从根到该结点所经分支上的所有结点

结点的祖先是从根到该结点所经分支上的所有结点。相应的以某结点为根的子树中的所有结点都是该结点的子孙节点。

子孙

子孙：以某结点为根的子树中的任意结点都称为该结点的子孙

堂兄弟

堂兄弟结点

双亲在同一层的结点被称为堂兄弟结点。

树的分类：有序树与无序树

有序树和无序树

如果将树中结点的各个子树看成从左至右是有次序的，不能交换，则称为有序树，否则就是无序树。

有序树

树中结点的子树从左到右是有次序的，不能交换

无序树

树中结点没有次序，若交换结点位置，则变成一棵不同的树

路径和路径长度

路径

树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的

路径长度

路径长度是路径上所经过的边的个数

森林（Forest）

森林是m(m>=0)棵互不相交的树的集合。

森林：m(m>=0)棵互不相交的树的集合

m(m>=0)棵互不相交的树的集合。例如把树根结点删除变形成一个森林

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

是m（m>=0）棵互不相交的树的集合。

树的相关术语

结点的度

叶结点

分支结点

结点的层次

结点的层序编号

树的度

树的高度(深度)

森林

孩子结点

双亲结点(父结点)

兄弟结点

适用场景

是链表和数组的优化方案

处理大批量动态数据

性质

结点与度数

结点数 = Σ 度 x 个数 + 1【根】

结点个数

高 h 的 m 叉树结点至多 = (m^h-1)/(m-1)

一般的高 h 的二叉树结点至多为

偶数个结点的二叉树，其 度数为1 的结点个数必然为奇数

最小高度

m阶树的最小高度 = m叉树的最小高度 = 完全 m 叉树的高度【必背】

最大高度

n个结点，度为m的树最大高度

树中的结点数等于所有结点的度数加1

度为m的树中第i层上至多有m^(i-1)个结点(i>=1)

高度为h的m叉树至多有(m^h -1)/(m-1)个结点

具有n个结点的m叉树的最小高度为[logm(n(m-1))+1)]

操作

与二叉树的转换

树转换二叉树

森林转换二叉树

二叉树转换森林

遍历、树和森林的遍历方式

先根遍历

树非空，先访问根节点，再按从左到右的顺序遍历根节点的每一棵子树

后根遍历

先序遍历

根—第一棵树—除去第一棵后的树

先序遍历

中序遍历

第一棵树—根—除去第一棵后的树

左父右

前序遍历

父左右

后续遍历

左右父

层序遍历

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

层次遍历

辅助队列

BFS广度优先搜索

复杂度分析

生成树与生成森林

DFS深度优先搜索

遍历与连通性

递归与非递规转换

递归 = 栈

遍历序列构造二叉树

中序(必须)+先序/后续

线索树遍历需要栈

后序遍历

求祖先到子孙的路径可以使用先/中序遍历

树的基本运算

求根Root(T)

求双亲Parent(T,X)

求孩子Child(T,X,i)

建树Create(X,T1,…,Tk),k>1

剪枝Delete(T,X,i)

遍历TraverseTree(T)

树的存储结构

一、双亲表示法

连续空间存储树的结点，即一维数组

结点构成：数据域和双亲域

类型定义

双亲表示法

双亲表示法：以一组连续的空间存储树的结点，同时在每个结点中，附设一个指示器，指示其双亲结点到链表中的位置

在每个结点中除了数据外，附设一个指针指示器指向其双亲结点在数组中的位置

二、孩子链表表示法

孩子表示法

双亲孩子表示法：就是在孩子表示法的基础上加上双亲指针（不要单链表）。

孩子表示法：把每个结点的孩子结点排列起来，以单链表作为存储结构。则n个结点有n个孩子链表，叶结点的单链表为空，然后n个头指针又组成一个线性表存放进一个一维数组中

把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点就有n个单链表，叶结点的单链表为空表。然后n个头指针又组成一个线性表，采用顺序存储的结构，存放在一个一维数组中。

双亲孩子表示法

三、孩子兄弟链表表示法

孩子兄弟表示法

孩子兄弟表示法：任意一棵树，它的结点第一个孩子如果存在，就是唯一的，它的右兄弟如果存在也是唯一的,因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。（孩子兄弟表示法可以将任意树转化为二叉树的存储结构，只是解释不一样）

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟结点。

孩子兄弟链表的结构形式与二叉链表完全
相同，但结点中指针的含义不同

存储结构的设计是一个非常灵活的过程。一个存储结构设计的是否合理，取决于基于该存储结构的运算是否合适，是否方便，时间复杂度好不好等等。

多重链表表示法：就是在每个结点中除了数据域外，还要有很多的指针域，其中每一个指针域指向一棵子树的根节点。

线性结构和树结构的不同

线性结构

第一个数据元素：无前驱

最后一个数据元素：无后继

中间元素：一个前驱一个后继

树结构

根结点：无双亲，唯一。

叶结点：无孩子，可以多个

中间节点：一个双亲多个孩子。

树结构

树有关的算法-Leecode

617. 合并二叉树

题解1

题解2

938. 二叉搜索树的范围和

题解1

题解2

题解3

题解4

题解5

226. 翻转二叉树

题解1

题解2

题解3

104. 二叉树的最大深度

题解1

590. N叉树的后序遍历

题解1

题解2

700 二叉搜索树中的搜索

题解1

题解2

108. 将有序数组转换为二叉搜索树

题解1

589. N叉树的前序遍历

题解1

897. 递增顺序查找树

题解1

559. N 叉树的最大深度

题解1

题解2

1022. 从根到叶的二进制数之和

题解1

扩展到N杈树

637. 二叉树的层平均值

题解1

题解2

965. 单值二叉树

题解1

子主题

常见树的类型

平衡树

2-3 查找树

2-3树

2-3 查找树的定义

查找

插入

2-3 树的性质

2-3 树的实现

2-3 查找树

2-3 查找树的定义

查找

插入

2-3 树的性质

2-3 树的实现

红黑树

定义

1. 每个结点要么是红的，要么是黑的

2. 根结点是黑的

3. 每个叶结点，即空结点（NIL）是黑的

4. 如果一个结点是红的，那么它的俩个儿子都是黑的

5. 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点(黑高平衡)

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。

红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树存在的问题和AVL树类似，在于当数据量很大的时候，树的高度太高，IO的次数太多，效率较低

红黑树的特性

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

左旋

对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)！。

因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。

子主题

LEFT-ROTATE(T, x)
y ← right[x] // 前提：这里假设x的右孩子为y。下面开始正式操作
right[x] ← left[y] // 将 “y的左孩子” 设为 “x的右孩子”，即将β设为x的右孩子
p[left[y]] ← x // 将 “x” 设为 “y的左孩子的父亲”，即将β的父亲设为x
p[y] ← p[x] // 将 “x的父亲” 设为 “y的父亲”
if p[x] = nil[T]
then root[T] ← y // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
else if x = left[p[x]]
then left[p[x]] ← y // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else right[p[x]] ← y // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
left[y] ← x // 将 “x” 设为 “y的左孩子”
p[x] ← y // 将 “x的父节点” 设为 “y”

子主题

右旋

对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为y的右孩子)！

因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。

子主题

RIGHT-ROTATE(T, y)
x ← left[y] // 前提：这里假设y的左孩子为x。下面开始正式操作
left[y] ← right[x] // 将 “x的右孩子” 设为 “y的左孩子”，即将β设为y的左孩子
p[right[x]] ← y // 将 “y” 设为 “x的右孩子的父亲”，即将β的父亲设为y
p[x] ← p[y] // 将 “y的父亲” 设为 “x的父亲”
if p[y] = nil[T]
then root[T] ← x // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点
else if y = right[p[y]]
then right[p[y]] ← x // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”
else left[p[y]] ← x // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
right[x] ← y // 将 “y” 设为 “x的右孩子”
p[y] ← x // 将 “y的父节点” 设为 “x”

添加

第一步: 将红黑树当作一颗二叉查找树，将节点插入。
第二步：将插入的节点着色为"红色"。
根据被插入节点的父节点的情况，可以将"当节点z被着色为红色节点，并插入二叉树"划分为三种情况来处理。

① 情况说明：被插入的节点是根节点。
处理方法：直接把此节点涂为黑色。

② 情况说明：被插入的节点的父节点是黑色。
处理方法：什么也不需要做。节点被插入后，仍然是红黑树。

③ 情况说明：被插入的节点的父节点是红色。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。

理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为3种情况(Case)。

子主题

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

删除

第一步：将红黑树当作一颗二叉查找树，将节点删除。
这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。
选择重着色3种情况。
① 情况说明：x是“红+黑”节点。
处理方法：直接把x设为黑色，结束。此时红黑树性质全部恢复。
② 情况说明：x是“黑+黑”节点，且x是根。
处理方法：什么都不做，结束。此时红黑树性质全部恢复。
③ 情况说明：x是“黑+黑”节点，且x不是根。
处理方法：这种情况又可以划分为4种子情况。这4种子情况如下表所示：

子主题

红黑树

红黑树的定义

平衡化

左旋

右旋

颜色反转

红黑树

红黑树的定义

平衡化

左旋

右旋

颜色反转

字典树（Trie）

概念

字典树，也称为“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。

trie 树（字典树）

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

字典树

字典树（Trie）

概念

字典树，也称为“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。

R树

N元树

树(多叉)和森林

存储结构

双亲表示法

顺序存储；存储地址=逻辑地址

孩子表示法

邻接表存储；有向图存储结构

孩子兄弟/二叉树表示法

树、森林和二叉树转换

遍历对应关系

树：先根

森林：先序

二叉树：先序

树：后根

森林：后序

二叉树：中序

森林和二叉树关系

右孩子指针为空的结点数相同

森林结点数

已知森林边和结点数，求森林中包含的树的个数

应用

并查集

Union(S,Root1,Root2)

Find(S,x)

Initial(S)

并查集

并查集结构

并查集 API 设计

并查集的实现

并查集应用举例

UF_Tree 算法优化

路径压缩

案例-畅通工程

并查集

并查集主要用于解决动态连通性问题

连通的三个性质

1、自反性：节点p和p是连通的

2、对称性：如果节点p和q连通，那么q和p也连通

3、传递性：如果节点p和q连通，q和r连通，那么p和r也连通

方向数组 d 是上下左右搜索的常用手法
int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};

二维坐标映射到一维的常用技巧：x * n + y(m是棋盘的行数，n是棋盘的列数）

并查集

操作

合并 Union

寻找祖先 Find(S,x)

初始化 Init(S)

并查集与等价类

其他

4.6.1分类与判定树

抽象数据类型

树状数组

树状数字

线段树

二叉树（Binary Tree）

二叉树的基本定义

二叉树的定义

二叉树每个结点最多有两棵子树

二叉树的子树有严格的左右之分

二叉树允许只有右（左），而没左（右）子树

树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。

区分树和图的重要特征是树中不存在环路。

基本术语

Root - 根节点

Parent - 父节点

Child - 子节点

Leaf - 叶子节点

Sibling - 兄弟节点

二叉树概念

如果某结点只有一个子结点，则必为左孩子

定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集，或者由一个根结点和两个互不相交的，分别称为根结点的左子树和右子树的二叉树组成

是n（n>=0）个结点的有限集合，该集合或者为空集合（称为空二叉树），或者有一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树的概念

每个结点至多只有两棵子树，是有序树

与度为2的有序树的区别

度为2的树

至少有3个结点

孩子结点的左右次序是相对于另一孩子而言

二叉树

可以为空

结点次序不是相对于另一结点而言，而是确定的

特殊二叉树

二叉树的基本概念

由一个根及两棵互不相交的左子树和右子树组成

特点

5种基本形态

基本运算

初始化Initiate(BT)

求双亲Parent(BT,X)

求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)

建二叉树Create(BT)

先序遍历PreOrder(BT)

中序遍历InOrder(BT)

后序遍历PostOrder(BT)

层次遍历LevelOrder(BT)

概述

定义

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

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

特点

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

二叉树的存储结构

顺序存储结构

顺序存储

二叉树的顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置也就是数组的下标，要能体现结点之间的逻辑关系
比较适合存储完全二叉树
对于一般的二叉树，也可以按照完全二叉树存储，将不存在的结点用“^”占位

4.3.1二叉树的顺序存储结构

用于完全二叉树

节省内存

结点位置确定方便

用于一般二叉树

浪费空间

链式存储结构

链式存储

二叉链表

由一个数据域和两个指针域组成

左，右孩子，结点值

三叉链表

4.3.2二叉树的链式存储结构

二叉树的存储结构

顺序存储结构：一个完全二叉树，按照相应的下标对应其相同的位置，对于一般的二叉树就是相对于完全二叉树没有的结点就用^来表示

二叉链表：二叉树每个结点最多有两个子结点，所以给他设计一个数据域与两个指针域，这样的链表叫做二叉链表。

二叉树的遍历与线索化

深度优先

前中后序遍历，基于栈实现迭代访问

广度优先

基于队列实现

二叉树的三种遍历

定义：二叉树的遍历是指从根结点出发，按照某种次序，依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

树的广度优先遍历（层次遍历）

树的深度优先遍历

先根遍历

递归

先序(NLR)

非递归

二叉树中查找值为x的结点

根—左—右

先序遍历 N-L-R

前序遍历：先访问根结点，再前序遍历左子树，再前序遍历右子树

中根遍历

递归

非递归

中序(LNR)

中序遍历 L-N-R

左—根—右

中序遍历：先中序遍历左子树，再访问根结点，再中序遍历右子树

应用：表达式树（四则混合运算）

后根遍历

递归

非递归

求二叉树的深度

后序遍历 L-R-N

后序(LRN)

左—右—根

后序遍历：先后续遍历左子树，再后续遍历右子树，再访问根结点

二叉树的遍历

4.4.1二叉树遍历的递归实现

1、先序遍历（递归算法）

2、中序遍历运算（递归算法）

3、后序遍历运算（递归算法）

4.4.2二叉树的层次遍历

4.4.3二叉树遍历的非递归实现

二叉树的基础遍历

前序遍历

中序遍历

后序遍历

二叉树的层序遍历

遍历方式

广度优先搜索

深度优先搜索

前序遍历

中序遍历

后序遍历

遍历二叉树

定义：是从根节点出发，按照某种次序依次访问二叉树中得所有结点，使得每个结点都被访问一次。

方法

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

层序遍历：一层一层一次访问，每层是从左到右。

二叉树的性质

非空二叉树上的叶子结点数等于度为2的结点数加1，即N0=N2 +1

非空二叉树上第K层上至多有2^(k-1) 个结点（K>=1）

高度为H的二叉树只有有2^H -1个结点(H>=1)

对完全二叉树按从上到下，从左到右的顺序依次编号1,2,...,N，则有

i>1时，结点i的双亲结点编号为┗i/2┛

i为偶数时，双亲编号i/2，是双亲的左孩子

i为奇数时，双亲编号(i-1)/2，是双亲的右孩子

2i<=N时，结点i的左孩子编号2i，否则无左孩子

2i+1<=N时，结点i的右孩子编号2i+1，否则无右孩子

结点i所在层次（深度）为┗log2 i┛+1

具有N个(N>0)结点的完全二叉树的高度为┏log2 (N+1)┓或┗log2 N┛ +1

4.2.2二叉树的性质

1.在第i(i>=1)层上至多有2i-1个结点

2.深度为k(k>=1)至多有2k-1个结点

满二叉树——深度为k(k>=1)且有2k-1个结点

3.叶结点数n0=度为2的结点数n2+1

完全二叉树

4.具有n个结点的完全二叉树的深
度为⌊log2n⌋+1

性质5

性质

1: 在二叉树的第i层上，最多有2^i - 1个结点

2：深度为k的二叉树，最多有2^k - 1个结点

3：对于任意一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

4: 具有n个结点完全二叉树的深度为[log2 n]+1([x]表示不大于x的最大整数)

5：如果对一棵有n个结点的完全二叉树的结点按层级编号，对任意结点i有：
1. 如果i=1，则结点i是树的根。如果i>1，则其双亲结点是[i/2]
2. 如果2i > n，则结点i无左孩子(为叶子结点)，否则其左孩子为2i
3. 如果2i+1 > n，则结点i无右孩子，否则其右孩子为结点2i+1

二叉树中的第i（i>=0）层上的结点数最多为2^n

深度为h(h>=1)的二叉树中最多有2^h-1个结点

对于任何一课二叉树，其叶结点数为a,度为2的结点数为b，则a=b+1

具有n个结点的完全二叉树，其深度为(log2^n)+1 或者（log2^(n+1)）

二叉树性质

遍历

先序遍历和后序遍历序列相反

左必在右的前面被访问

前中后序的访问序列，叶子结点序列不变

遍历顺序合法性使用中+前/后确定具体二叉树，再检验其他

个数

叶子结点个数

叶子个数 = 度为2的结点个数+1

第k层最多结点数

高度为h至多结点个数

下标

编号与左右孩子

i 结点的左孩子编号 = 2i

i 结点的右孩子编号 = 2i+1

最后一个非叶结点编号

深度

结点所在深度

n个结点的完全二叉树深度

指针个数

N 个结点的二叉树，有 N+1 个空指针

性质

在二叉树的第i层上至多有2^(i-1)-1个结点（i>=1）。

深度为k的二叉树至多有2^k-1结点（k>=1）

对任何一棵树二叉树T，如果其终端结点数为n0，度为2的结点数为n1，则n0=n1+1

具有n个结点的完全二叉树的深度为[log2N]+1([x]指的是不大于x的最大整数)

如果对一棵有n个结点的完全二叉树（其深度为[log2N]+1）的结点按层序号（从第一层到最后一层，每层从左到右），对任一结点i（1=<i=<n）有：
1.如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是节点[i/2]。
2.如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
3.如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。

特点

每个结点最多有两棵子树，所以二叉树不存在度大于2的结点。

左子树和右子树是有顺序的，次序不能颠倒。

即使一个结点只有一棵树，也要区分是左子树还是右子树。

五种基本形态

空二叉树

只有一个根节点

根节点只有左子树

根节点只有右子树

根节点既有右子树也有右子树

二叉树应用

平衡二叉树AVL

定义

树的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

某结点的左子树与右子树的高度（深度）差即为该结点的平衡因子（BF、Balance Factor）

由于二叉搜索树在最坏的情况下（顺序写入）会退化成链表，搜索时的时间复杂度高

这里AVL树在节点进行插入、删除、修改的时候进行了自平衡，让整棵树不至于过于倾斜

平衡二叉树是一种二叉查找树，其中每一个结点的左子树和右子树高度差至多为1

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1

1. 二叉查找树的定义

2. 左右两个子树的高度差的绝对值不超过1(子高平衡)

左右子树高度差绝对值不超过1

平衡二叉树（AVL树）

AVL树

平衡二叉树

AVL树图示

图示

右边二叉树中节点值为10的左右子树高度差为2

自平衡手段

如果插入新节点时发现左右子树的平衡因子的绝对值大于2，通过LL、LR、RR、RL的操作保证平衡因子的绝对值小于等于1

特点

AVL树由于自平衡的存在，使得树的高度不会太高，平均搜索的时间复杂度为O(logN)

缺点

树的高度较高，需要多次IO操作

几乎每次插入/删除节点都会影响二叉树的平衡

平衡因子

双亲结点因子=左子树高度 - 右子树高度

操作

插入

查找

旋转

LL(左孩子左子树)

以A的左孩子固定为新的根右旋一次
并将A连接为其右子结点
原本右节点按照前驱后继关系连接【比大小】

LL平衡旋转（右单旋转）

RR(右孩子右子树)

以A的右孩子固定为新的根左旋一次
并将A连接为其左子结点
原本左节点按照前驱后继关系连接【比大小】

RR平衡旋转（左单旋转）

LR(左孩子右子树)

先调节左子树内部平衡，左旋一次
再调节整体平衡，右旋一次

LR平衡旋转（先左后右双旋转）

RL(右孩子左子树)

RL平衡旋转（先右后左双旋转）

平衡旋转诀窍

调整最小不平衡子树

LL,RR 旋一次，LR,RL 旋两次（先内后外）

左重顺旋减轻左深，右重逆旋减轻右深

根连前驱后继【按照数值大小比较连接】

计算

1.构造一棵高为 h 的 AVL 所需要的最少结点数
2.已知共有 n 个结点的 AVL，求其最大深度
3.已知AVL的高度为 n,且所有非叶子结点的平衡因子为 1,求结点总数

二叉搜索树
二叉树查找树(BST)

定义

二叉排序树（BST）

二叉搜索树

排序二叉树

或者是一棵空树，或者具有以下特性的树

左子树非空，则左子树所有结点关键字值小于根节点的

右子树非空，则右子树所有结点关键字值大于根节点的

左右子树本身也分别是一棵二叉排序树

左子树上所有关键字小于更节电关键字，而右结点则均大于。

对于树中每个结点X，它的左子树中所有项的值都小于X项的值，它的右子树中所有项的值都大于X项的值

首先如果普通二叉树每个节点满足：左子树所有节点值小于它的根节点值，且右子树所有节点值大于它的根节点值，则这样的二叉树就是排序二叉树。

操作

插入

插入操作

首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是：新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节点，则到左子树中寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。

插入操作

查找

递归查找

非递归查找

查询操作

查找操作的主要流程为：先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。

因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。

删除

叶结点
直接删除

x 只有一个左/右子树
子结点接上其父节点

x 有左右两棵子树
补前驱后继

删除操作

删除操作主要分为三种情况，即要删除的节点无子节点，要删除的节点只有一个子节点，要删除的节点有两个子节点。

1. 对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
2. 对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点。
3. 对于要删除的节点有两个子节点，则首先找该节点的替换节点（即右子树中最小的节点），接着替换要删除的节点为替换节点，然后删除替换节点。

子主题

构造

二叉查找树的创建

效率分析

平均查找长度

性质

删除某节点后将其插入，则前后排序树有可能不同

题目计算

ASL(平均查找长度）

成功查找长度

失败查找长度

递增序列遍历=中序遍历

非法查找路径序列

二叉查找树其他便捷方法

查找二叉树中最小的键

查找二叉树中最大的键

定义

1. 左子树所有节点的值均小于他的根节点的值

2. 右子树所有节点的值均大于他的根节点的值

3. 子树也符合以上规则

缺点

数据不平衡

简单定义

首先二叉搜索树也是一棵二叉树

二叉搜索树的任意结点A，其左子树的所有结点的值都小于结点A的值，其右子树的所有结点都大于结点A的值；前提是任意结点A的左右子树不为空

二叉搜索树的左右子树也是一棵二叉搜索树

二叉搜索树没有值相等的结点

特点

二叉搜索树所存储的元素必须具有可比较性，也就是说字段的值必须存在，不能为NULL

二叉搜索树搜索元素的时间复杂度为O(logN) ~ O(N)，N为元素的个数

图示

缺点

在顺序（递增或者递减）写入的情况下，会退化成链表。查询数据时需要全表扫描，时间复杂度为O(N)

图示

BST 二叉搜索树

二叉排序树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
它的左、右子树也分别为二叉排序树。

存在的问题

对于一般的二叉搜索树（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.从任意节点到每个叶子节点的简单路径上有相同节点的黑色节点。

红黑树

https://blog.csdn.net/kexuanxiu1163/article/details/103431589?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param

AVL树

SBT

Splay

Treap

左旋操作: 当传入一个二叉查找树P时，将它的右孩子定义为R，将R的左子树变为P的右子树，再将P改为R的左子树，最后将R替换P成为根结点，完成一次左旋操作

右旋操作：当传入一个二叉查找树P时，将它的左孩子定义为L，将L的右子树变为P的左子树，再将P改为L的右子树，最后将L替换P成为根结点，完成一次右旋操作

平衡二叉树(AVL)

相关概念

平衡因子：二叉树上结点的左子树深度减去右子树深度值称为平衡因子

最小不平衡子树：距离插入结点最近的，且平衡因子绝对值大于1的结点为根的子树，称为最小不平衡子树

单旋转：只通过一次旋转使最小不平衡子树重新恢复平衡，当平衡因子为负时左旋，当平衡因子为正时右旋

双旋转：当最小不平衡子树的平衡因子与它的子树平衡因子符号相反时，就需要对结点先进行一次旋转使符号相同，再反向旋转一次

红黑树

性质：

1. 节点是红色或黑色。
2. 根节点是黑色。
3.所有叶子都是黑色。（叶子是NIL节点）
4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

伸展树

完全二叉树

定义

每个结点都与高为 h的满二叉树编号为的结点位置一一对应

对一棵具有n个结点的二叉树按层级编号，如果编号为i的结点与和它相同深度的满二叉树的编号为i的结点在树中位置一致，则这棵二叉树称为完全二叉树

性质结论

若一个结点没有左孩子，则其必然是叶结点

叶子结点的双亲的左兄弟（若存在）则必然不是叶子节点

高度为 h 的完全二叉树，节点个数最小为

最后一个分支结点序号为

若某完全二叉树有 x 个结点，则其叶子节点个数为

计算

完全二叉树第 x 层有 k 个叶节点，则其
结点个数最少为：
结点个数最多为：

完全二叉树

在满二叉树的基础上，从右到左，有序减掉0-n个叶结点

规定编号从0-n,则结点编号为i的双亲结点为(i-1)/2

若2i+1>=n,则编号为i的结点没有左孩子

若2i+2>=n,则编号为i的结点没有右孩子

完全二叉树

高为h，含有n个结点的二叉树，当且仅当每一个结点都与高为h的满二叉树对应时

若i<=┗n/2┛,则结点i为分支结点，否则为叶子结点

叶子结点只可能在层次最大的两层出现

若有度为1的结点，只能有一个，且该结点只有左孩子而无右孩子

按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点

n的取值

n为奇数

每个分支结点都有左子女和右子女

n为偶数

编号最大的分支结点（编号n/2）只有左子女而没有右子女，其余分支都有

完全二叉树

堆

完全二叉树

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

完全二叉树

对于一个具有n个节点的二叉树按层序编号，如果标号为i（1<=i<=n）的结点于同样深度的满二叉树中的编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树。

特点

叶子结点只能出现最下两层。

最下层的叶子结点只能出现在最左侧连续的位置。

倒数二层，若有叶子结点，一定出现在右部连续的位置。

如果结点度为1，则该结点只有左孩子，既不存在只有右子树的情况。

同样的结点数的二叉树，完全二叉树的深度最小。

示例

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置

完美二叉树

当所有叶子节点都在同一层时

满二叉树

高为h，且含有2^h -1个结点的二叉树

二叉树中的每个结点恰好有两个孩子且所有叶子结点都在同一层

满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2

在一棵二叉树中，所有的分支结点都有左子树和右子树，并且所有的叶子结点都在同一层上，这样的二叉树称为满二叉树

所有结点（叶结点）都非空，满

定义

二叉树中的每个结点恰好有两个孩子且所有叶子结点都在同一层

如果每个内部节点（非叶节点）都包含两个孩子，就成为满二叉树

满二叉树

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

满二叉树

在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树就被称为满二叉树。

特点

叶子结点只能出现在最后一层，出现在其他层就会不平衡。

非叶子结点的度必须是2。

在同样深度的二叉树中，满二叉树的结点和叶子节点都是最多的。

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树

斜树

所有的结点都只有左子树的二叉树被称为左斜树；所有的结点都只有右子树的二叉树被称为右斜树，这两者统一被称为斜树。

所有结点都只有左子树或只有右子树的二叉树

哈夫曼树

哈夫曼编码

固定长度编码

每个字符用相等长度二进制位表示

前缀编码

没有一个编码是另一个编码的前缀

哈夫曼树

带权路径长度

定义

带权路径长度(WPL)最小的二叉树；也称最优二叉树

度为 m 的哈夫曼树，为严格的 m 叉树

构造

贪心，每次取两个权值最小的结点作为新结点的左右子树
新结点权值为左右子树和，并放入到可选择的结点集合中

性质

初始结点均为叶子结点

权值越小到根节点路径越长

新建了n-1个结点，结点总数为 2n-1

度为m的哈夫曼树中，叶子结点为n，则其非叶子节点个数为

叶子结点个数即为不同符号的编码数

哈夫曼树

构造

步骤...

哈夫曼编码

哈夫曼树

4.6.2哈夫曼树和哈夫曼算法

4.6.3哈夫曼编码

赫夫曼树(哈夫曼树)

相关概念

路径：从树中一个结点到另一个结点的分支构成两个结点之间的路径

路径长度：路径上的分支数称为路径长度

结点路径长度：从该结点到根结点的分支数称为结点的路径长度

树的路径长度:从树根到每一个结点的路径之和称为树的路径长度

结点的WPL(带权路径长度)：从该结点到树根的路径长度与该结点上权的乘积

树的带权路径长度：树中所有叶子结点的WPL(带权路径长度)之和

定义：假设有n个权值{w1,w2,...,wn},构造一个有n个叶子结点的二叉树，每个叶子结点的带权为wk，则其中带权路径长度最小的二叉树称为赫夫曼树

构造赫夫曼树的算法描述：
1. 根据给定的n个权值{w1,w2,...wn},构成n棵二叉树F={T1,T2,...Tn}。其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空；
2. 在F中选择两个权值最小的树作为左右子树构成新的二叉树，且置新二叉树的根结点权值为其左右子树根结点权值之和
3. 在F中删除这两棵树，并将新得到的二叉树加入F中
4. 重复2和3的步骤，直到F中只有一棵树为止，这棵树便是赫夫曼树

赫夫曼编码

以w1,w2,...,wn作为相应叶子结点的权值来构造一棵赫夫曼树，规定赫夫曼树的左分支代表0，右分支代表1。则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该叶子结点对应字符的编码，这就是赫夫曼编码

哈弗曼编码

哈夫曼树

概念

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

结构

适用场景

典型运用

哈夫曼编码

哈夫曼树

最优二叉树