问题标题: 算法：100豆--说出你们知道的算法名称

自动AC机，真有这算法

周琪岳熟练掌握:

动态规划,dp 动态规划初步 背包 环形 dp 数位 dp 多维状态 区间 dp 树形 dp 插头 dp

搜索 广度优先搜索,BFS 深度优先搜索,DFS 剪枝 记忆化搜索 迭代加深 随机调整 

数论,数学 集合论 线性规划 Lucas

图论 图遍历 仙人掌

计算几何 凸包 叉积 线段相交 点积 半平面交 最近点对 凸多边形的交 离散化扫描 旋转卡壳

树形结构 点分治 树状数组 cdq 分治 整体二分 环套树 K-D Tree

博弈论 Nim游戏 博弈树 Shannon开关游戏

线段树 二维线段树 矩形树 主席树

平衡树 AVL Treap SBT Splay 静态排序树 替罪羊树

二叉堆 左偏树 斜堆 二项堆

整数研究 素数判断,质数,筛法 最大公约数,gcd 扩展欧几里德,扩欧 不定方程 进制 同余,中国剩余定理 莫比乌斯反演逆元

• 二叉树
• 最值，平均值
• 图论
• 排列组合
• 位运算
• 逻辑分析
• 数论
• 链表
• 二分
• 栈
• 互质
• 数学
• 包河区2019年竞赛
• 队列
• 动态规划
• 标准输出
• 变量
• 标准输入
• 实数
• 除法
• 变量自增自减
• 正序循环输出
• for循环执行顺序及循环变量i
• 倒序循环输出
• 求余数
• 奇数和偶数
• 连续赋值
• bool类型
• 关系运算符
• if结构
• 打折
• 逻辑与/或/非
• 逻辑运算符优先级
• if-else结构
• printf
• 强制类型转换
• 字符型变量
• 字符型常量
• ASCII码
• 字符算术运算
• 大小写字母转换
• 变量交换
• if-else嵌套
• else if结构
• 选择结构
• 循环求和
• 循环套选择结构
• 阶乘
• 次方
• pow函数
• while循环
• 循环输入，遇0结束
• do-while循环
• break语句
• continue语句
• 循环求最大值、最小值、平均值
• 双重循环
• 一维数组定义
• 一维数组元素引用
• 一维数组输入与输出
• 一维数组初始化
• 求一维数组最大值和最小值
• 一维数组
• 选择排序
• 二维数组的定义
• 二维数组的输入与输出
• 二维数组元素引用
• 二维数组某整行、列操作
• 字符串赋值
• 字符串输入与输出
• 求字符串长度
• 连接两个字符串
• 字典序
• 字符串中截取子串
• 字符串中删除子串
• 字符串中插入子串
• 字符串中查找子串
• 字符串内部排序
• 函数的定义
• 形参和实参
• 局部变量和全局变量
• 值传递和地址传递
• sort函数
• 冒泡排序
• 插入排序
• 桶排序
• sort排序
• 结构体定义
• 结构体函数
• 结构体排序
• 四舍五入
• 分段收费问题
• 循环取位数
• 最大公约数、最小公倍数
• 因数、平方根、质数
• 质因数
• 埃氏筛法
• 进制转换
• 打印图形
• 枚举
• 矩阵（上）：矩阵基本性质
• 矩阵（下）：填数问题
• 周期问题
• 字符串模拟
• 回文
• 字符串变换加密
• 模拟
• 机器分配
• 递推
• 字符串中替换子串
• 遍历字符串
• 字符串比较大小
• 贪心
• 搜索与回溯
• 复合运算
• 01背包
• 完全背包
• 多重背包
• 混合背包
• 分组背包
• 依赖背包
• 二维费用的背包
• 背包求方案总数
• 选择排序优化
• 线性DP
• 线性DP-最长不下降子序列
• 线性DP-NOIP真题
• 表达式求值
• 括号匹配
• 走迷宫
• 填数问题
• 洪泛
• 桶去重
• 桶计数
• 递归
• 堆
• 并查集
• 最短路径
• 优先队列
• 区间DP
• 循环计数
• 归并排序
• 前缀和
• 最长公共子序列
• 数塔
• 文件操作
• 桶的运用
• 高精度
• 字符数组
• 标志位
• STL-map
• 排序综合练习
• 滑动窗口
• 双指针
• 三分
• 欧拉路径
• 分治
• STL-vector
• Dijkstra
• SPFA
• Floyd
• 位宽函数
• Prim
• Kruscal
• 单调队列
• 背包问题中最少物品数量
• stringstream
• 最小生成树
• 连续子数组
• 费用流
• 八皇后
• 线段树
• 最短路径算法
• LCA
• 记忆化搜索
• 强连通分量
• 博弈论
• 容量问题
• 数字删除、拆分
• 区间问题
• 点的距离
• 数组模拟操作
• 矩阵折叠
• 简单模型
• 复杂模型
• 进制转换
• 位运算
• 排序算法
• 向上取整
• 递归
• 深度优先搜索
• 广度优先搜索
• 模拟（字符串）
• 斐波那契数列
• 按位异或
• 模拟（其它模拟）
• 课时5 质数、质因数
• 快速排序
• 编辑距离
• 二分查找
• 课时9 日期
• 课时11 简单贪心
• 2020北京小学市赛
• 拓扑排序
• 实数域上的二分
• 整数域上的二分
• 模板题
• 求解转判定
• 最大连续子数组和
• 树状数组
• 子集问题
• 深度优先搜索
• 剪枝优化
• abs函数
• max,min函数
• ceil函数
• 广度优先搜索，bfs
• 树形DP
• 数位DP
• 差分约束
• 欧拉回路
• 建图
• 日期问题
• 后缀表达式
• 二进制
• 快速输入输出
• 哈希表
• 二叉树的遍历
• ST算法
• 快速幂
• 矩阵乘法
• 树链剖分

字符串 后缀自动机,SAM字典树,Trie 树AC 自动机KMP后缀数组,SA后缀树有限状态自动机哈夫曼,Huffman简单密码学回文自动机 PAMManacher 算法

动态规划,dp

动态规划,dp 动态规划初步背包环形 dp数位 dp多维状态区间 dp树形 dp插头 dp

搜索

搜索 广度优先搜索,BFS深度优先搜索,DFS剪枝记忆化搜索迭代加深随机调整

数论,数学

数论,数学 集合论线性规划Lucas

图论

图论 图遍历仙人掌

计算几何

计算几何 凸包叉积线段相交点积半平面交最近点对凸多边形的交离散化扫描旋转卡壳

树形结构

树形结构 点分治树状数组cdq 分治整体二分环套树K-D Tree

博弈论

博弈论 Nim游戏博弈树Shannon开关游戏

线段树

线段树 二维线段树矩形树主席树

线性结构

线性结构 莫队前缀和基本数组向量栈队列块状链表,块状数组,分块st表,稀疏表差分

平衡树

平衡树 AVLTreapSBTSplay静态排序树替罪羊树

二叉堆

二叉堆 左偏树斜堆二项堆

最大匹配

最大匹配 匈牙利算法一般图的最大匹配Konig定理

整数研究

整数研究 素数判断,质数,筛法最大公约数,gcd扩展欧几里德,扩欧不定方程进制同余,中国剩余定理莫比乌斯反演逆元

基础算法

基础算法 模拟贪心递推递归枚举,暴力分治

排序

排序 冒泡排序选择排序桶排插入排序归并排序快速排序堆排序希尔排序外部排序

查找算法

查找算法 二分答案顺序查找二分查找

启发式搜索

启发式搜索 启发式迭代加深,IDA*Dancing Links爬山法模拟退火遗传A*算法

动态规划优化

动态规划优化 单调队列降低维度,降维优先队列矩阵加速,矩阵优化斜率优化状态压缩,状压凸完全单调性,凸单调四边形不等式

图的建立,建图

图的建立,建图 邻接矩阵邻接表

拓扑排序

拓扑排序 AOVAOE

最短路

最短路 FloydDijkstraBellman-FordSPFAK短路差分约束

生成树

生成树 PrimKruskal生成树的另类算法次小生成树特殊生成树

圈和块

圈和块 最小环负权环连通块2-SAT欧拉公式欧拉回路

强连通分量,缩点

强连通分量,缩点 Tarjan割点

二分图

二分图 带权二分图匹配稳定婚姻系统

最大流

最大流 DinicSap有上下界的最大流

最小割

最小割 闭合图最小点权覆盖集最大点权独立集分数规划最大密度子图

费用流

费用流 最短路增广费用流最小费用可行流

树上距离

树上距离 节点到根的距离最近公共祖先,LCA节点间的距离树的直径

动态树

动态树 树链剖分,树剖Link-Cut Tree,LCT

树的应用

树的应用 并查集树的遍历哈夫曼树RMQ树套树可持久化虚树

哈希,HASH

哈希,HASH ELFhashSDBMBKDR

群论

群论 置换Polya原理

组合数学

组合数学 排列组合二项式定理康托展开袋与球问题鸽笼容斥斐波那契,Fibonacci卡特兰,CatalanStirling生成函数

概率论,统计

概率论,统计 众数简单概率条件概率Bayes期望

线性代数

线性代数 矩阵运算矩阵乘法线性递推,递推式高斯消元异或方程组线性基

微积分初步

微积分初步 极限导数积分定积分立体解析几何级数

其它技巧

其它技巧 暴力数据结构高精度倍增离散化随机贪心,随机化快速傅里叶变换，FFT位运算,按位NP 问题构造快速数论变换 NTT快速沃尔什变换 FWT快速莫比乌斯变换 FMT

• 二叉树
• 最值，平均值
• 图论
• 排列组合
• 位运算
• 逻辑分析
• 数论
• 链表
• 二分
• 栈
• 互质
• 数学
• 包河区2019年竞赛
• 队列
• 动态规划
• 标准输出
• 变量
• 标准输入
• 实数
• 除法
• 变量自增自减
• 正序循环输出
• for循环执行顺序及循环变量i
• 倒序循环输出
• 求余数
• 奇数和偶数
• 连续赋值
• bool类型
• 关系运算符
• if结构
• 打折
• 逻辑与/或/非
• 逻辑运算符优先级
• if-else结构
• printf
• 强制类型转换
• 字符型变量
• 字符型常量
• ASCII码
• 字符算术运算
• 大小写字母转换
• 变量交换
• if-else嵌套
• else if结构
• 选择结构
• 循环求和
• 循环套选择结构
• 阶乘
• 次方
• pow函数
• while循环
• 循环输入，遇0结束
• do-while循环
• break语句
• continue语句
• 循环求最大值、最小值、平均值
• 双重循环
• 一维数组定义
• 一维数组元素引用
• 一维数组输入与输出
• 一维数组初始化
• 求一维数组最大值和最小值
• 一维数组
• 选择排序
• 二维数组的定义
• 二维数组的输入与输出
• 二维数组元素引用
• 二维数组某整行、列操作
• 字符串赋值
• 字符串输入与输出
• 求字符串长度
• 连接两个字符串
• 字典序
• 字符串中截取子串
• 字符串中删除子串
• 字符串中插入子串
• 字符串中查找子串
• 字符串内部排序
• 函数的定义
• 形参和实参
• 局部变量和全局变量
• 值传递和地址传递
• sort函数
• 冒泡排序
• 插入排序
• 桶排序
• sort排序
• 结构体定义
• 结构体函数
• 结构体排序
• 四舍五入
• 分段收费问题
• 循环取位数
• 最大公约数、最小公倍数
• 因数、平方根、质数
• 质因数
• 埃氏筛法
• 进制转换
• 打印图形
• 枚举
• 矩阵（上）：矩阵基本性质
• 矩阵（下）：填数问题
• 周期问题
• 字符串模拟
• 回文
• 字符串变换加密
• 模拟
• 机器分配
• 递推
• 字符串中替换子串
• 遍历字符串
• 字符串比较大小
• 贪心
• 搜索与回溯
• 复合运算
• 01背包
• 完全背包
• 多重背包
• 混合背包
• 分组背包
• 依赖背包
• 二维费用的背包
• 背包求方案总数
• 选择排序优化
• 线性DP
• 线性DP-最长不下降子序列
• 线性DP-NOIP真题
• 表达式求值
• 括号匹配
• 走迷宫
• 填数问题
• 洪泛
• 桶去重
• 桶计数
• 递归
• 堆
• 并查集
• 最短路径
• 优先队列
• 区间DP
• 循环计数
• 归并排序
• 前缀和
• 最长公共子序列
• 数塔
• 文件操作
• 桶的运用
• 高精度
• 字符数组
• 标志位
• STL-map
• 排序综合练习
• 滑动窗口
• 双指针
• 三分
• 欧拉路径
• 分治
• STL-vector
• Dijkstra
• SPFA
• Floyd
• 位宽函数
• Prim
• Kruscal
• 单调队列
• 背包问题中最少物品数量
• stringstream
• 最小生成树
• 连续子数组
• 费用流
• 八皇后
• 线段树
• 最短路径算法
• LCA
• 记忆化搜索
• 强连通分量
• 博弈论
• 容量问题
• 数字删除、拆分
• 区间问题
• 点的距离
• 数组模拟操作
• 矩阵折叠
• 简单模型
• 复杂模型
• 进制转换
• 位运算
• 排序算法
• 向上取整
• 递归
• 深度优先搜索
• 广度优先搜索
• 模拟（字符串）
• 斐波那契数列
• 按位异或
• 模拟（其它模拟）
• 课时5 质数、质因数
• 快速排序
• 编辑距离
• 二分查找
• 课时9 日期
• 课时11 简单贪心
• 2020北京小学市赛
• 拓扑排序
• 实数域上的二分
• 整数域上的二分
• 模板题
• 求解转判定
• 最大连续子数组和
• 树状数组
• 子集问题
• 深度优先搜索
• 剪枝优化
• abs函数
• max,min函数
• ceil函数
• 广度优先搜索，bfs
• 树形DP
• 数位DP
• 差分约束
• 欧拉回路
• 建图
• 日期问题
• 后缀表达式
• 二进制
• 快速输入输出
• 哈希表
• 二叉树的遍历
• ST算法
• 快速幂
• 矩阵乘法
• 树链剖分

熊智晖在2021-06-05 20:11:33追加了内容

把豆子给我呗

        查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找，字段的查找，等等。

1、查找算法总结

(1). 最容易理解的查找算法，顺序查找法

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

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

　　复杂度分析：　

　　查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
　　当查找不成功时，需要n+1次比较，时间复杂度为O(n);

　　所以，顺序查找的时间复杂度为O(n)。

代码实现：

//顺序查找
 

int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i]==value)
            return i;
    return -1;
}
(2).二分查找

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

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

　　复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；

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

代码实现：

//二分查找（折半查找），版本1
int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}
(3).数表查找

5.1 最简单的树表查找算法——二叉树查找算法。

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

　　二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：

　　1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

　　2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

　　3）任意节点的左、右子树也分别为二叉查找树。

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

　　不同形态的二叉查找树如下图所示：



 　　有关二叉查找树的查找、插入、删除等操作的详细讲解，请移步浅谈算法和数据结构: 七 二叉查找树。

　　复杂度分析：它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡（比如，我们查找上图（b）中的“93”，我们需要进行n次查找操作）。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。

　　下图为二叉树查找和顺序查找以及二分查找性能的对比图：



 

　　基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。

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

　　2-3查找树定义：和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：

　　1）要么为空，要么：

　　2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。

　　3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。



　　2-3查找树的性质：

　　1）如果中序遍历2-3查找树，就可以得到排好序的序列；

　　2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。）

　　性质2）如下图所示：



 

　　复杂度分析：

　　2-3树的查找效率与树的高度是息息相关的。

在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN
　　距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。

　　对于插入来说，只需要常数次操作即可完成，因为他只需要修改与该节点关联的节点即可，不需要检查其他节点，所以效率和查找类似。下面是2-3查找树的效率：



 

　　5.3 平衡查找树之红黑树（Red-Black Tree）

　　2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现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-node节点就是2-3树中的一个3-node节点了。



　　红黑树的性质：整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同（2-3树的第2）性质，从根节点到叶子节点的距离都相等）。

　　复杂度分析：最坏的情况就是，红黑树中除了最左侧路径全部是由3-node节点组成，即红黑相间的路径长度是全黑路径长度的2倍。

　　下图是一个典型的红黑树，从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍：



　　红黑树的平均高度大约为logn。
　　下图是红黑树在各种情况下的时间复杂度，可以看出红黑树是2-3查找树的一种实现，它能保证最坏情况下仍然具有对数的时间复杂度。



　　红黑树这种数据结构应用十分广泛，在多种编程语言中被用作符号表的实现，如：

Java中的java.util.TreeMap,java.util.TreeSet；
C++ STL中的：map,multimap,multiset；
.NET中的：SortedDictionary,SortedSet 等。
　　5.4 B树和B+树（B Tree/B+ Tree）

　　平衡查找树中的2-3树以及其实现红黑树。2-3树种，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。

　　维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。

　　B树定义：

　　B树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。

根节点至少有两个子节点

每个节点有M-1个key，并且以升序排列

位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间

其它节点至少有M/2个子节点

　　下图是一个M=4 阶的B树:



　　可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似，这里就不介绍了。下面是往B树中依次插入

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

的演示动画：



　　B+树定义：

　　B+树是对B树的一种变形树，它与B树的差异在于：

有k个子结点的结点必然有k个关键码；
非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
　　如下图，是一个B+树:



 

　　下图是B+树的插入动画：

 

　　B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

　　B+ 树的优点在于：

由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
　　但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

　　下面是B 树和B+树的区别图：



　　B/B+树常用于文件系统和数据库系统中，它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中，如：

Windows：HPFS文件系统；
Mac：HFS，HFS+文件系统；
Linux：ResiserFS，XFS，Ext3FS，JFS文件系统；
数据库：ORACLE，MYSQL，SQLSERVER等中。
　　有关B/B+树在数据库索引中的应用，请看张洋的MySQL索引背后的数据结构及算法原理这篇文章，这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍，推荐阅读。

　　树表查找总结：

　　二叉查找树平均查找性能不错，为O(logn)，但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化，我们可以使用平衡查找树。平衡查找树中的2-3查找树，这种数据结构在插入之后能够进行自平衡操作，从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难，红黑树是2-3树的一种简单高效的实现，他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树，应用非常广泛，很多编程语言的内部实现都或多或少的采用了红黑树。

　　除此之外，2-3查找树的另一个扩展——B/B+平衡树，在文件系统和数据库系统中有着广泛的应用。

• 二叉树
• 最值，平均值
• 图论
• 排列组合
• 位运算
• 逻辑分析
• 数论
• 链表
• 二分
• 栈
• 互质
• 数学
• 包河区2019年竞赛
• 队列
• 动态规划
• 标准输出
• 变量
• 标准输入
• 实数
• 除法
• 变量自增自减
• 正序循环输出
• for循环执行顺序及循环变量i
• 倒序循环输出
• 求余数
• 奇数和偶数
• 连续赋值
• bool类型
• 关系运算符
• if结构
• 打折
• 逻辑与/或/非
• 逻辑运算符优先级
• if-else结构
• printf
• 强制类型转换
• 字符型变量
• 字符型常量
• ASCII码
• 字符算术运算
• 大小写字母转换
• 变量交换
• if-else嵌套
• else if结构
• 选择结构
• 循环求和
• 循环套选择结构
• 阶乘
• 次方
• pow函数
• while循环
• 循环输入，遇0结束
• do-while循环
• break语句
• continue语句
• 循环求最大值、最小值、平均值
• 双重循环
• 一维数组定义
• 一维数组元素引用
• 一维数组输入与输出
• 一维数组初始化
• 求一维数组最大值和最小值
• 一维数组
• 选择排序
• 二维数组的定义
• 二维数组的输入与输出
• 二维数组元素引用
• 二维数组某整行、列操作
• 字符串赋值
• 字符串输入与输出
• 求字符串长度
• 连接两个字符串
• 字典序
• 字符串中截取子串
• 字符串中删除子串
• 字符串中插入子串
• 字符串中查找子串
• 字符串内部排序
• 函数的定义
• 形参和实参
• 局部变量和全局变量
• 值传递和地址传递
• sort函数
• 冒泡排序
• 插入排序
• 桶排序
• sort排序
• 结构体定义
• 结构体函数
• 结构体排序
• 四舍五入
• 分段收费问题
• 循环取位数
• 最大公约数、最小公倍数
• 因数、平方根、质数
• 质因数
• 埃氏筛法
• 进制转换
• 打印图形
• 枚举
• 矩阵（上）：矩阵基本性质
• 矩阵（下）：填数问题
• 周期问题
• 字符串模拟
• 回文
• 字符串变换加密
• 模拟
• 机器分配
• 递推
• 字符串中替换子串
• 遍历字符串
• 字符串比较大小
• 贪心
• 搜索与回溯
• 复合运算
• 01背包
• 完全背包
• 多重背包
• 混合背包
• 分组背包
• 依赖背包
• 二维费用的背包
• 背包求方案总数
• 选择排序优化
• 线性DP
• 线性DP-最长不下降子序列
• 线性DP-NOIP真题
• 表达式求值
• 括号匹配
• 走迷宫
• 填数问题
• 洪泛
• 桶去重
• 桶计数
• 递归
• 堆
• 并查集
• 最短路径
• 优先队列
• 区间DP
• 循环计数
• 归并排序
• 前缀和
• 最长公共子序列
• 数塔
• 文件操作
• 桶的运用
• 高精度
• 字符数组
• 标志位
• STL-map
• 排序综合练习
• 滑动窗口
• 双指针
• 三分
• 欧拉路径
• 分治
• STL-vector
• Dijkstra
• SPFA
• Floyd
• 位宽函数
• Prim
• Kruscal
• 单调队列
• 背包问题中最少物品数量
• stringstream
• 最小生成树
• 连续子数组
• 费用流
• 八皇后
• 线段树
• 最短路径算法
• LCA
• 记忆化搜索
• 强连通分量
• 博弈论
• 容量问题
• 数字删除、拆分
• 区间问题
• 点的距离
• 数组模拟操作
• 矩阵折叠
• 简单模型
• 复杂模型
• 进制转换
• 位运算
• 排序算法
• 向上取整
• 递归
• 深度优先搜索
• 广度优先搜索
• 模拟（字符串）
• 斐波那契数列
• 按位异或
• 模拟（其它模拟）
• 课时5 质数、质因数
• 快速排序
• 编辑距离
• 二分查找
• 课时9 日期
• 课时11 简单贪心
• 2020北京小学市赛
• 拓扑排序
• 实数域上的二分
• 整数域上的二分
• 模板题
• 求解转判定
• 最大连续子数组和
• 树状数组
• 子集问题
• 深度优先搜索
• 剪枝优化
• abs函数
• max,min函数
• ceil函数
• 广度优先搜索，bfs
• 树形DP
• 数位DP
• 差分约束
• 欧拉回路
• 建图
• 日期问题
• 后缀表达式
• 二进制
• 快速输入输出
• 哈希表
• 二叉树的遍历
• ST算法
• 快速幂
• 矩阵乘法
• 树链剖分