数据结构
简单数据结构
10年积累的成都网站制作、网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站设计制作后付款的网站建设流程，更有邵原免费网站建设让你可以放心的选择与我们合作。
数据结构简单的可分为线性结构（主要是线性表）和非线性结构（主要是树和图）。
线性数据结构
线性结构是一个有序数据元素的集合。
常用的线性结构
线性表，栈，队列，双队列，串(一维数组)。
非线性数据结构
关于广义表、数组(高维)，是一种非线性的数据结构。
常见的非线性结构
二维数组，多维数组，广义表，树(二叉树等)，图。
树
树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
其中每个元素称为结点(node),每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
如图是一棵树：
一棵树中至少有1个结点，即根结点。
一个结点的子树个数，称为这个结点的度（如结点1的度为3，结点3的度为0）。
度为0的结点称为叶结点（leaf）（如结点3、5、6、8、9）。
树中各结点的度的最大值称为这棵树的度（此树的度为3）。
上端结点为下端结点的父结点，称同一个父结点的多个子结点为兄弟结点（如结点1是结点2、3、4的父结点，结点 2、3、4是结点1的子结点，它们又是兄弟结点）。
遍历
树结构解决问题时，按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。
先序(根)遍历
先访问根结点，再从左到右按照先序思想遍历各棵子树（如，上图先序遍历的结果为）。
后序（根）遍历
先从左到右遍历各棵子树，再访问根结点（如，上图后序遍历的结果为）。
层次遍历
按层次从小到大逐个访问，同一层次按照从左到右的次序（如，上图层次遍历的结果为）。
叶结点遍历
即从左到右遍历所有叶节点（如，上图叶节点遍历的结果为）。
二叉树
二叉树是一种特殊的树型结构，它是度数为2的树，即二叉树的每个结点最多有两个子结点。
每个结点的子结点分别称为左儿子、右儿子。
五种基本形态
性质
性质一
二叉树的第i层最多有2i-1个结点（i>=1）（可用二进制性质解释。）。
性质二
深度为k的二叉树至多有2k–1个结点（k>=1）。
性质三
任意一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。
性质四
有n个结点的完全二叉树的深度为floor(log2n)+1。
性质五
一棵n个结点的完全二叉树，对任一个结点(编号为i)，有：如果i=1，则结点i为根，无父结点；如果i>1,则其父结点编号为floor（i/2），如果i为父节点编号，那么2i是左孩子，2i+1是右孩子。
图A-满二叉树
图B-完全二叉树
编号示意图
遍历
二叉树的遍历是指按一定的规律和次序访问树中的各个结点。
遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。
先序遍历
若二叉树为空，则空操作，否则：
访问根结点、先序遍历左子树、先序遍历右子树
void preorder(tree bt)//先序递归算法
{
if(bt)
{
cout << bt->data;
preorder(bt->lchild);
preorder(bt->rchild);
}
}先序遍历此图结果为：
中序遍历
若二叉树为空，则空操作，否则：
中序遍历左子树、访问根结点、中序遍历右子树
void inorder(tree bt)//中序遍历递归算法
{
if(bt)
{
inorder(bt->lchild);
cout << bt->data;
inorder(bt->rchild);
}
}中序遍历上图结果为：
后序遍历
若二叉树为空，则空操作，否则：
后序遍历左子树、后序遍历右子树、访问根结点
void postorder(tree bt)//后序递归算法
{
if(bt)
{
postorder(bt->lchild);
postorder(bt->rchild);
cout << bt->data;
}
}后序遍历上图结果为：
已知先序序列和中序序列可唯一确定一棵二叉树；
已知中序序列和后序序列可唯一确定一棵二叉树；
已知先序序列和后序序列不可唯一确定一棵二叉树；
二叉树操作（建树、删除、输出）
普通树转二叉树
由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转换成二叉树进行操作。
通用法则：“左孩子，右兄弟”
建树
删除树
插入一个结点到排序二叉树中
在排序二叉树中查找一个数
相关题目
扩展二叉树
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用“.”补齐，称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列，要求输出其中序和后序序列。
输入样例：
ABD..EF..G..C..
输出样例：
DBFEGAC
DFGEBCA
二叉树的建立和输出
以二叉链表作存储结构，建立一棵二叉树，并输出该二叉树的先序、中序、后序遍历序列、高度和结点总数。
输入样例：
12##3##
//#为空
输出样例：
123
//先序排列
213
//中序排列
231
//后序排列
2
//高度
3
//结点总数
因为本蒟蒻不太会用指针，所以自己写了一个不带指针的，代码很丑，见谅QwQ
#include
#include
#define ll long long
using namespace std;
int top,maxh;
char s;
struct t{
int data,father,lson=0,rson=0,h=0;
}tree[];
void build(int father,bool right){
cin>>s;
if(s=='\n')
return;
if(s!='#'){
++top;
int t=top;
tree[t].father=father;
tree[t].data=s-'0';
tree[t].h=tree[father].h+1;
maxh=max(tree[t].h,maxh);
if(right==1)
tree[father].rson=t;
else
tree[father].lson=t;
build(t,0);
build(t,1);
}
else return;
}
void xian(int now){
cout< P1030 求先序排列
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入：
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与 后序排列。
输出：
1行，表示一棵二叉树的先序。
输入样例：
BADC
BDCA
输出样例：
ABCD
分析
中序为BADC，后序为BDCA，所以A为根结点，B、DC分别为左右子树的中序序列，B、DC分别为左右子树的后序序列。然后再递归处理中序为B，后序为B的子树和中序为DC，后序为DC的子树。
自己用char数组写的代码QwQ
#include
#include
#include
#define ll long long
using namespace std;
char mid[10],post[10];
//mid数组记录中序排列，post数组记录后序排列
//除了打暴力最好不要用string
int z[10],m[10],p[10];
//z数组做中转使用，m数组记录mid数组的内容，p数组记录post数组的每一位在mid数组中的位置
void find(int start,int end,int kai,int jie){
//start和end记录我们正在找的mid数组的范围
//kai（开头）和jie（结尾）记录我们正在找的post数组的范围
if(start>end||kai>jie)return;
//如果开头大于结尾，就返回
if(start==end||kai==jie){
printf("%c",mid[p[jie]]);
return;
}
//如果开头等于结尾，那此节点一定没有儿子，输出当前节点并返回
printf("%c",mid[p[jie]]);
//前面说过后序排列的最后一位就是当前树的根节点，所以p[jie]就是根节点在mid数组中的位置
//开头小于结尾，那就输出当前节点然后再去寻找此节点的左儿子和右儿子
find(start,p[jie]-1,kai,kai+p[jie]-start-1);
//求左子树的范围，然后递归寻找左儿子
find(p[jie]+1,end,kai+p[jie]-start,jie-1);
//求右子树的范围，然后递归寻找右儿子
}
int main(){
scanf("%s%s",mid+1,post+1);
//输入时下标从1开始（主要是因为我比较毛病）
int len=strlen(mid+1);
//输入时下标从1开始那么计算字符串长度时也要加1
for(int i=1;i<=len;i++){
m[i]=mid[i]-'A'+1;
//将每一位转成数字以方便处理（是的，我很毛病）
z[m[i]]=i;
//z数组记录m数组每一位的位置（这一步是为了方便后面记录post数字）
}
for(int i=1;i<=len;i++){
p[i]=z[post[i]-'A'+1];
//记录post数组的每一位在mid数组中的位置
//z：我滴任务完成啦！
}
find(1,len,1,len);
//开始递归
return 0;
} 求后序排列
输入：
二叉树的前序序列与中序序列
输出：
二叉树的后序序列
样例输入：
abcdefg
cbdafeg
样例输出：
cdbfgea
#include
#include
#include
#define ll long long
using namespace std;
char qian[],zhong[];
int q[],z[],a[],cnt=0;
void find(int start,int end){
if(start>end){
return;
}
cnt++;
if(start==end){
cout<>qian>>zhong;
int len=strlen(qian);
for(int i=0;i 因为有小可爱说我的代码在输入时的处理不清楚，所以又写了一个版本QwQ
#include
#include
#include
#define ll long long
using namespace std;
char qian[],zhong[];
int q[],z[],a[],cnt=0;
void find(int start,int end){
// cout<end){
return;
}
cnt++;
if(start==end){
cout<>qian+1>>zhong+1;
scanf("%s%s",qian+1,zhong+1);//这里的输入下标从1开始
int len=strlen(qian+1);
for(int i=1;i<=len;i++){
a[zhong[i]-'a']=i;
}
for(int i=1;i<=len;i++){
z[i]=zhong[i]-'a'+1;
q[i]=a[qian[i]-'a'];
}
find(1,len);
return 0;
} 表达式树
关于表达式树，我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如，对于下图的遍历结果如下，它们对应着表达式的3种表示方法。
-+a*b-cd/ef (前缀表示、波兰式)
a+b*(c-d)-e/f (中缀表示)
abcd-*+ef/- (后缀表示、逆波兰式)
哈夫曼树
QwQ，不是很会，那就推荐一篇博客吧。
序列维护（线段树&平衡树）
线段树
线段树的用处就是，对编号连续的一些点进行修改或者统计操作，修改和统计的复杂度都是O(log2(n))。
线段树的原理就是将[1,n]分解成若干特定的子区间(数量不超过4*n),然后，将每个区间[L,R]都分解为少量特定的子区间，通过对这些少量子区间的修改或者统计，来实现快速对[L,R]的修改或者统计。
用线段树统计的东西，必须符合区间加法，否则，不可能通过分成的子区间来得到[L,R]的统计结果。
相关题目
做法
考虑我们维护了什么，有哪些是我们没有维护的（一般是一个左边、一个右边、一个跨过中线的东西）。
平衡树
平衡树(BT) 全称“平衡二叉搜索树”，指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作,时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。
设“2-3 树”的每个结点存放一组与应用问题有关的数据, 且有一个关键字 (>0的整数) 作为标识。关键字的存放规则如下:对于结点X, 设左、中、右子树均不空, 则左子树任一结点的关键字小于中子树中任一结点的关键字;中子树中任一结点的关键字小于结点X的关键字;而X的关键字又小于右子树中任一结点的关键字, 称这样的“2-3树”为平衡树。
常见的类型
splay
treap
AVL Tree
Red Black Tree
Scape Goat Tree
Weight Balanced Leafy Tree（特殊结构）
二叉搜索树（BST）
性质
一个节点x左子树所有点的关键字都比x的关键字小，右子树所有点的关键字都比x的关键字大。
treap
“树堆”“Tree + Heap”
性质
每个点随机分配一个权值，使treap同时满足堆性质和二叉搜索树性质 。
复杂度
期望O( logn )
设每个节点的关键字是key，随机权值是rand
如果v是u的左儿子，则key[v] < key[u]
如果v是u的右儿子，则key[v] > key[u]
如果v是u的子节点，则rand[u] > rand[v]
Treap维护权值的时候一般会把相同的权值放在同一个节点上 。
一个treap节点需要维护的信息
左右儿子
关键字
关键字出现次数
堆随机值
节点大小（即子树大小）
Treap的旋转
平衡二叉搜索树主要通过旋转来保持树的平衡，即保证复杂度。
旋转有单旋和双旋，treap只需要单旋。
Treap的插入
先给这个节点分配一个随机的堆权值 ，
然后把这个节点按照bst的规则插入到一个叶子上：
从根节点开始，逐个判断当前节点的值与插入值的大小关系。如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子；
然后通过旋转来调整，使得treap满足堆性质。
Treap的删除
和普通的BST（二叉搜索树）删除一样：
如果删除值小于当前节点值，则递归至左儿子；大于则递归至右儿子 。
若当前节点数值的出现次数大于 1 ，则减一（通常将同一个权值缩掉），
若当前节点数值的出现次数等于 1 :
若当前节点没有左儿子与右儿子，则直接删除该节点（置 0）；
若当前节点没有左儿子或右儿子，则将左儿子或右儿子替代该节点；
若当前节点有左儿子与右儿子，则不断旋转当前节点，并走到当前节点新的对应位置，直到没有左儿子或右儿子为止。
Treap的查询
递归到叶子节点，一路维护信息即可。
Treap的分裂合并
用于维护序列，支持将Treap按前k个位置分裂为两棵树 。
分裂的时候维护两棵树，分别代表左边和右边的部分 。
复杂度
因为保证了堆性质，所以复杂度期望下是正确的 。
Treap只需要保证堆性质复杂度就期望正确。
splay
“伸展树”“自适应查找树”
每次对一个节点进行操作的时候通过一种方法把这个点旋转至根 。
splay的分裂
用于维护序列，支持将splay按前k个位置分裂为两棵树 。
直接把第k个位置splay到根，然后断开根的右儿子。
splay的合并
将右边部分的第一个位置splay到根，然后让其左儿子为左边部分
复杂度
可以证明复杂度为均摊O(mlogn)
可能存在一次操作复杂度特别高 。
splay具有“自适应性” 。
大概就是说splay会根据操作的特点调整树结构，使得操作尽可能高效。
可以去了解一下splay的动态最优性猜想，是个著名的open problem
缺点
可以通过势能分析证明splay的复杂度是均摊O( logn )的，也就是说splay在很多次操作中可能会有一次O( n )复杂度的操作 。
而且这样的操作也很好构造 。
所以splay不适合做一些需要撤销操作/可持久化的题目（虽然可以通过随机旋转什么的方法来规避，但还是感觉很吃力）
自身常数比较大 。
优点
splay用来维护序列还是比较好写的，用来维护名次树感觉不好写 。
由于自适应性，splay不需要特殊的技巧就可以高效启发式合并，还可以高效实现LCT（STT）等动态树
WBLT（Weight Balanced Leafy Tree）
这个Weight Balanced是指的Balanced by Boundary，也就是BB[α]
和clj那个定义不一样
大概可以理解为通过旋转而不是重构来满足替罪羊树那个平衡关系 。
也就是说替罪羊树是Weight Balanced Tree的一种。
线段树就是一种Leafy Tree，也就是说把信息都存在叶子上，非叶节点都是存储了信息的合并的虚点 。
优点
目前最好写的平衡树，可持久化效率很高 。
缺点
非可持久化的情况下要两倍空间，拿来写LCT（STT）很吃力 。
替罪羊树
定义常数平衡因子α
如果一个点的某个儿子，占到了子树大小的α，则认为不平衡，重构这个子树 。
复杂度也是带均摊的，均摊O(logn)，最坏单次操作O(n)。
解决问题
给你一个序列，每次查询区间的分治信息，可能有单点修改或者区间修改 。
给你一棵树，每次查询路径的分治信息，可能有单点修改或者路径修改。
注意
这里维护的信息是可快速合并的信息，具体怎么定义快速合并比较复杂。
建议考虑线段树合并区间答案的时候，考虑如果答案都在左区间，都在右区间的情况，然后剩下的情况就是这次合并需要额外维护的 。
有可能考虑合并需要额外维护的信息时需要额外在线段树节点上维护新的信息。
常见的打标记的操作
区间加
区间乘
区间染色（区间修改为一个数）
区间翻转
区间xor
区间值修改
维护出区间中每个极长的 “X” 段的长度，可以发现这个存在一个自然根号：
假设区间长度为size，则最多只有O( sqrt( size ) )种极长 “X” 段的长度 ，
每次对区间进行值修改的时候，即对这个长度为O( sqrt( size ) )的多项式进行求值，暴力计算即可，求值复杂度为O( sqrt( size ) )，即可以O( sqrt( size ) )的时间将一个节点值进行修改，同时维护信息 。
区间符号修改
每次对区间符号进行修改的时候，区间的信息只会变成区间和或者区间乘积，所以我们每个节点要维护区间和和区间乘积 。
符号修改之后，这个节点的极长 “X” 段只会有O( 1 )种了 。
符号进行修改可能影响一些节点的极长 “X” 段，考虑如何维护这个。
对一个节点，我们可以归并两个儿子的极长 “X” 段，来维护出这个节点的极长 “X” 段 。
对一个大小为size的节点进行归并，代价是O( sqrt( size ) )的 。
注意需要特判左儿子的最右极长 “X” 段是否和右儿子的最左极长 “X” 段进行合并 。
区间信息合并
合并区间信息的时候，只需要把左右儿子信息加起来，同时特判O(1)个位置即可
这O(1)个位置就是左儿子的最右部分和右儿子的最左部分
可处理：
标记对标记的影响
标记对信息的影响
信息和信息的合并
复杂度
T( n ) = T( n / 2 ) + O( sqrtn )
sqrt( n ) + sqrt( n / 2 ) + sqrt( n / 4 ) + … + sqrt( 1 ) = O( sqrt(n) )
空间
T( n ) = 2T( n / 2 ) + O( sqrtn )
sqrt( n ) + 2sqrt( n / 2 ) + 4sqrt( n / 4 ) + … + nsqrt( 1 ) = O( n )
总时间复杂度O( msqrtn )，空间复杂度O( n )
均摊复杂度问题
序列染色段数均摊
特点
修改有区间染色操作
用平衡树维护区间的颜色连续段 。
区间染色每次最多只会增加O( 1 )个连续颜色段，用平衡树维护所有连续段即可 。
均摊的颜色段插入删除次数O( n + m )
应用
区间染色，维护区间的复杂信息
区间排序
“ODT”类问题
注意
这里这个颜色段数均摊是有2~3的常数，常数很大。
“重量”平衡树
平衡树旋转/重构的节点的size的和是O( nlogn )
这样可以在旋转的时候暴力重构一些信息
应用
动态标号问题
序列
1.在x后面插入y
2.查询x和y在序列上的先后问题，这个要求O(1)
可以线性解决，但是由于其他部分一般带log所以OI中一般采用O( nlogn )的解决方法 。
套用动态标号法可以得到平衡树维护后缀数组的算法，被称为“后缀平衡树” 。
可以实现树套树的外层树插入。
Old Driver Tree
在有类区间染色操作，以及保证数据随机的情况下 。
可以用一个平衡树维护颜色连续段的暴力来解决 。
复杂度期望O( (n+m)loglogn )，可以做到O( n + m )，但是not practical
在线
O( (n+m)loglogn )（直接做），O( (n+m)logloglogn )（使用exponential tree），
O( n + m )（使用O( logn/logw )的动态前驱数据结构）
离线
O( n + m )，压位即可
可以证明复杂度是期望O( (n+m)logn )的
假设有k种操作，其中一种是区间染色，定义势能为颜色段个数
每次操作的时候有两种可能性：
1.以O( x )的代价消除O( x )势能，势能+2，概率1/k
2.以O( x )的代价啥都没做，势能+2，概率1-1/k
势能的均摊是O( n + m )
于是这部分总的代价是O( (n+m)k )
所以复杂度瓶颈在于平衡树而不是暴力的均摊部分
应用
各种题都能用，基本上不会被卡
因为大部分出题人都觉得序列维护的那种数据结构题只需要随机数据就足够强了…
不过要注意，别被没有区间染色的部分给卡了…
可以水掉各种题
补：
gcd（最大公约数）
gcd(a,b)=gcd(a-b,b)
题目
询问区间gcd
gcd(a[l],a[l+1],……a[r])=gcd(a[l],a[l+1]-a[l],……a[r])
=gcd(a[l],a[l+1]-a[l],a[l+2]-a[l+1],……a[r]-a[r-1]
=gcd(a[l],b[l+1],……b[r]
树上倍增
用于求LCA（最近公共祖先）。
倍增的思想是二进制。
首先开一个n×logn的数组，比如fa[n][logn],其中fa[i][j]表示i节点的第2^j个父亲是谁。
然后，我们会发现一个性质：
fa[i][j]=fa[fa[i][j-1]][j-1]
用文字叙述为：i的第2^j个父亲 是i的第2^(j-1)个父亲的第2^(j-1)个父亲。
这样，本来我们求i的第k个父亲的复杂度是O(k)，现在复杂度变成了O(logk)。
树状数组
类似于线段树，用于区间查询、区间求和。
顾名思义，树状数组就是用数组来模拟树形结构。那么衍生出一个问题，为什么不直接建树？答案是没必要，因为树状数组能处理的问题就没必要建树。和Trie树的构造方式有类似之处。
树状数组可以解决大部分基于区间上的更新以及求和问题。
树状数组可以解决的问题都可以用线段树解决，这两者的区别在于树状数组的系数要少很多，就比如字符串模拟大数可以解决大数问题，也可以解决1+1的问题，但没人会在1+1的问题上用大数模拟。
树状数组的修改和查询的复杂度都是O(logn)，而且相比线段树系数要少很多，比传统数组要快，而且容易写。
缺点是遇到复杂的区间问题还是不能解决，功能还是有限。
求LCP（最长公共前缀）
前置知识
maxsuf（最大后缀）
maxpre（最大前缀）
方法
二分加哈希
左边的哈希值一样，就在右边继续求哈希，
左边的哈希值不一样，就在左边继续求哈希，
直到求出LCP。
离散化
离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
用法
有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。
用途
缩小值域。
set/map
分别是集合/映射
内部使用红黑树（一种平衡树）实现。
同样的当set<>和map<,>中的第一个参数是自定义类型的时候
需要重新定义小于号。
复杂度基本上是O(log(当前大小))
map相当于是一个下标可以是任何数值的数组，如果访问时没有赋值就会返回零。
并非原创，仅是整理，请见谅
当前文章：数据结构
文章地址：http://6mz.cn/article/dsoihps.html