首页  思维导图  详情

考研数据结构知识框架笔记

2022-10-31 10:57:32   0  举报





AI智能生成

考研数据结构知识框架笔记

考研数据结构

考研

数据结构

作者其他创作

大纲/内容

图lt/bgt

ltbgt图的存储结构lt/bgt

ltbgt邻接矩阵lt/bgt(适用于稠密图)

n个结点则为n阶矩阵

图：有边/弧为1，否则为0

网：有边/弧为权值，否则为∞

ltbgt邻接表lt/bgt(适用于稀疏图)

数组(弧尾结点)+链表(邻接点)+个数

图的遍历

ltbgt深度优先搜索lt/bgt

辅助用栈，结果不唯一

过程

访问某节点，从该结点出发

沿某路径依次访问未被访问的结点

若有顶点未访问，则选取一个未访问结点出发

重复上述过程，直到无未被访问结点

：深搜过程就是对搜索树先序遍历的过程

ltbgt广度优先搜索lt/bgt

辅助用队列，结果不唯一

过程

访问某节点，从该结点出发

依次访问邻接点，再从邻接点出发

若有顶点未访问，则选取一个未访问结点出发

重复上述过程，直到无未被访问结点

广搜过程就是对搜索树层次遍历的过程

ltbgt应用lt/bgt

ltbgt最小生成树lt/bgt

实质上是带权无向图。最小生成树是权值之和最小的生成树，不唯一

普利姆(Prim)算法

特点：只与顶点个数n有关，与边的个数e无关，适用于稠密图

V为连通网顶点集，U为生成树顶点集，TE为生成树边集

U={v₀}，TE=∅

计算U到其他顶点的最小代价，将该顶点纳入U，边纳入TE

重复上一步骤，知道U=V

克鲁斯卡尔(Kruskal)算法

特点：只与边的个数n有关，与顶点个数e无关，适用于稀疏图

不构成环条件下，每次选最小的边(做题技巧，不要过程时使用)

时间复杂度： ltbgtPrimnbsp ltfont color=quot#c41230quotgtO(n²)lt/fontgt，Kruskalnbsp ltfont color=quot#c41230quotgtO(e log₂e)lt/fontgtlt/bgt

ltbgt最短路径lt/bgt

两顶点之间带权路径长度最短的路径

ltbgtDijkstralt/bgt算法

初始化数组

从顶点ltbgtVlt/bgt中选出ltbgtvⱼ，lt/bgt满足ltbgtdist[j]=Min{dist[i], vⱼ∈V}lt/bgt

ltbgtvⱼlt/bgt为当前所求最短路径终点，另求ltbgtS∪{j}nbsplt/bgt

修改此时从ltbgtv₀出发到集合V-Slt/bgt上任意顶点ltbgtvₖlt/bgt最短路径的长度

若ltbgtdist[j]+arcs[j][k]ltdist[k]lt/bgt则令ltbgtdist[k]=dist[j]+arcs[j][k]nbsp path[k]=jlt/bgt

重复2、3、4步骤n-1次，知道S中包含全部顶点

ltbgtFloydlt/bgt算法

使用邻接矩阵ltbgtA⁽⁰⁾、A⁽¹⁾、A⁽²⁾······、A ⁽ⁿ⁾lt/bgt

第n次计算从起点经过n-1个顶点到达某个顶点最小带权之和

若到某个顶点有更小的权值之和，则替换之前的值并修改路径

直到到达终点

ltbgt拓扑排序lt/bgt

有向无环图：一个有向图中不存在环，简称DAG图

AOV网：用DAG图表示一个工程，顶点为活动，有向边为优先级，这样的网络为AOV网

由一个有向无环图的顶点组成的序列，满足一下要求，则称该图的拓扑排序

要求：

若顶点A在B的前面，则图中不存在从B到A的路径

每个顶点只出现一次

ltbgt关键路径lt/bgt

AOE网：用DAG图表示一个工程，顶点代表事件，边代表活动，这样的网络为AOE网

AOE网只有一个入度/出度为0的顶点，称为ltbgt源点lt/bgt/ltbgt汇点lt/bgt

问题：

整个工程完工需要多多长时间

哪些活动影响工程进度？

事件(顶点)：最早发生时间ltbgtVe(i)lt/bgt，最晚发生时间ltbgtVl(i)lt/bgt

活动(边)a(i,j)：最早开始时间ltbgte(i,j)lt/bgt，最晚发生时间 ltbgtl(i,j)lt/bgt

整个工程完工的时间就是终点的最早发生的时间，关键路径就是路径长度最长的路径。

算法：

对顶点进行拓扑排序ltigt（*是任意前驱事件）lt/igt

计算ltbgtVe(j)lt/bgt

ltbgtVe(1)=0lt/bgt

ltbgtVE(j)=max{Ve(*)+a(*,j)}lt/bgt

计算ltbgtVl(i)lt/bgt

ltbgtVl(n)=Ve(n)lt/bgt

ltbgtVl(i)=min{Vl(*)-a(i,*)}lt/bgt

计算ltbgte(i,j)lt/bgt和 ltbgtl(i,j)lt/bgt

ltbgte(i,j)=Ve(i)lt/bgt

ltbgtl(i,j)=Vl(j)-a(i,j)lt/bgt

结论：工程总用时ltbgtVe(n)lt/bgt，关键活动是ltbgte(i,j)= l(i,j)lt/bgt的活动ltbgta(i,j)lt/bgt

ltbgt查找

ltbgt顺序查找lt/bgt

顺序存储和链式存储，时间复杂度ltbgtO(n)lt/bgt

按顺序逐个比较，直到找到或者找不到

成功ASL=ltbgt(n-1)/2lt/bgt，失败ASL=ltbgtn/2+n/(n+1)lt/bgt

ltbgt折半查找lt/bgt

仅适用于有序的顺序表，时间复杂度ltbgtO(log₂n)lt/bgt

先从中间开始比较，比较一次抛弃一半元素逐渐缩小范围

ASL=ltbgtlog₂(n+1)+1lt/bgt

ltbgt分块查找lt/bgt

索引顺序查找，顺序查找+折半查找

块内元素可以无序，但块之间必须有序

ltbgtB树和B+树lt/bgt

阶：所有结点的孩子结点数的最大值

B树

只能随机检索

ltbgtnlt/bgt个关键字，ltbgtmlt/bgt阶B树高度ltbgthlt/bgt：ltbgtlogₘ(n+1)≤h≤logₘ ₂[(n+1)/2]+1lt/bgt

每个ltbgt结点lt/bgt最多有ltbgtmlt/bgt棵子树

非叶根结点至少有ltbgt2lt/bgt棵子树

除根结点以外的所有非终端结点至少有ltbgtm/2lt/bgt(取上界)棵子树

非终端结点有ltbgtnlt/bgt个关键字和ltbgtn+1lt/bgt棵子树，关键字个数n：ltbgt(m/2)-1≤n≤m-1lt/bgt

所有叶子在同一层，不含信息

B+树

可以顺序查找和随机查找

每个ltbgt分支结点lt/bgt至多ltbgtmlt/bgt棵子树

非叶根节点至少有ltbgt2lt/bgt棵子树

除根节点以外的所有非终端结点至少有ltbgtm/2lt/bgt(取上界)棵子树

结点的子树个数与关键字个数均为ltbgtm/2lt/bgt(取上界)

叶子结点包含全部关键字，且按顺序排列

ltbgt散列查找lt/bgt

哈希(Hash)查找

散列表/哈希表：建立了关键字与存储地址之间的一种映射关系

散列函数/哈希函数：把关键字映射到其对应存储地址的函数

装填因子：α=n/m，n个记录，m个地址空间

ltbgtltfont color=quot#c41230quotgt散列表的平均查找长度lt/fontgtlt/bgt与n和m不直接相关，而是ltbgtltfont color=quot#c41230quotgt取决于装填因子和处理冲突的方法lt/fontgtlt/bgt

冲突处理

ltbgt开放定址法lt/bgt

不可随意删除某个元素，否则会造成查找失败

ltbgt线性探测法lt/bgt：易引起堆积现象，降低效率

ltbgt二次(平方)探测法lt/bgt：避免堆积，但无法探测到所有单元

再散列法

伪随机序列

ltbgt链地址法lt/bgt

把所有同义词存放在一个线性链表中，散列表存放头指针

适用于经常插入和删除的情况

排序

ltbgt插入排序lt/bgt

直接插入排序

时间复杂度ltbgtO(n²)，lt/bgt空间复杂度ltbgtO(1)lt/bgt

ltbgt顺序存储和链式存储lt/bgt，ltbgt稳定lt/bgt算法

折半插入排序

时间复杂度ltbgtO(n²)lt/bgt，空间复杂度ltbgtO(1)lt/bgt

ltbgt顺序存储lt/bgt，ltbgt稳定lt/bgt算法

ltbgt希尔排序lt/bgt

时间复杂度ltbgtO(n¹˙⁵)lt/bgt，空间复杂度ltbgtO(1)lt/bgt

ltbgt顺序存储lt/bgt，ltbgtltfont color=quot#c41230quotgt不稳定lt/fontgtlt/bgt算法

增量序列逐渐缩小到1

ltbgt冒泡排序lt/bgt

时间复杂度ltbgtO(n²)lt/bgt，空间复杂度ltbgtO(1)lt/bgt

ltbgt顺序存储和链式存储lt/bgt，ltbgt稳定lt/bgt算法

一次比较相邻元素，逆序则交换，重复n-1次

ltbgt快速排序lt/bgt

时间复杂度ltbgtO(nlog₂n)lt/bgt，空间复杂度ltbgtltfont color=quot#c41230quotgtO(log₂n)lt/fontgtlt/bgt

ltbgt顺序存储和链式存储lt/bgt，ltbgtltfont color=quot#c41230quotgt不稳定lt/fontgtlt/bgt算法

选1个元素为轴从前向后、从后向前扫描，抓大放小，分成两部分后依次进行快排

ltbgt简单选择排序lt/bgt

时间复杂度ltbgtO(n²)lt/bgt，空间复杂度ltbgtO(1)lt/bgt

ltbgt顺序存储和链式存储lt/bgt，ltbgtltfont color=quot#c41230quotgt不稳定lt/fontgtlt/bgt算法

第i次排序在剩余待排记录选一个最小(大)的放在第i个位置。

比较次数为nbspltbgtn(n-1)/2lt/bgt

ltbgt堆排序lt/bgt

时间复杂度ltbgtO(nlog₂n)lt/bgt，空间复杂度ltbgtO(1)lt/bgt

ltbgt顺序存储和链式存储lt/bgt，ltbgtltfont color=quot#c41230quotgt不稳定lt/fontgtlt/bgt算法

小顶堆堆顶为最小元素，大顶堆堆顶为最大元素

堆的初始化

对具有双亲结点的结点从大到小编号做出以下调整

ltbgt①lt/bgt 若孩子结点皆小于双亲结点，则该结点调整结束

ltbgt②lt/bgt 若孩子结点大于双亲结点，则将最大的孩子结点与双亲结点交换

ltbgt③lt/bgt 对交换后的堆再次重复①②，直到出现①结束

堆排序

将堆顶元素与编号最后一个的元素交换后弹出

对堆进行初始化，并再次重复上述步骤，直到堆空结束

ltbgt二路归并排序lt/bgt

时间复杂度ltbgtO(nlog₂n)lt/bgt，空间复杂度ltbgtO(n)lt/bgt

ltbgt顺序存储和链式存储lt/bgt，ltbgt稳定lt/bgt算法

归并：两个或两个以上的有序表合成一个新的有序表

划分+排序（直接插入排序）

ltbgt基数排序lt/bgt

时间复杂度ltbgtO(d(n+r))lt/bgt，空间复杂度ltbgtO(r)lt/bgt

ltbgtltfont color=quot#c41230quotgt不基于比较lt/fontgtlt/bgt，ltbgt稳定lt/bgt算法

特点

基于关键字各位的大小进行排序，分为

最高位优先MSD

最低位优先LSD

采用“分配”与“收集”策略

对ltbgtnlt/bgt个数据进行基数排序，每个数据基数为nbspltbgtrlt/bgt，有ltbgtdlt/bgt位数字

一趟分配和收集用时ltbgtn+rlt/bgt（分配用ltbgtnlt/bgt，收集用nbspltbgtrlt/bgt），共需ltbgtnlt/bgt趟

辅助空间用到nbspltbgtrnbsplt/bgt个队列

ltbgt绪论lt/bgt

ltbgt数据结构的内容lt/bgt

逻辑结构

ltbgtltfont color=quot#c41230quotgt线性结构、集合、树状结构、图状结构lt/fontgtlt/bgt（后三种为非线性结构）

存储结构/物理结构

ltbgtltfont color=quot#c41230quotgt顺序存储、链式存储、索引存储、散列存储/哈希存储lt/fontgtlt/bgt

数据的运算

ltbgt抽象数据类型（例如：栈）的表示lt/bgt

三元组：ltbgt数据对象、数据关系、基本操作lt/bgt

ltbgt时间复杂度和空间复杂度lt/bgt

ltfont color=quot#c41230quotgtltbgtO(1)＞O(log₂n)＞O(n)＞O(nlog₂n)＞O(n²)＞O(n³)＞O(n!)＞O(nⁿ)lt/bgtlt/fontgt

ltbgt线性表lt/bgt

ltbgt顺序表lt/bgt

用一组连续存储单元依次存储线性表的数据元素

基本操作

插入nbspnbsp平均移动次数：ltbgtltfont color=quot#c41230quotgtn/2lt/fontgtlt/bgt，时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，需要移动元素

删除nbsp nbsp平均移动次数：ltbgtltfont color=quot#c41230quotgt(n-1)/2lt/fontgtlt/bgt，时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，需要移动元素

按值查找nbsp nbsp平均移动次数：ltbgtltfont color=quot#c41230quotgt(n+1)/2lt/fontgtlt/bgt，时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，顺序访问

按位查找nbsp nbsp时间复杂度：ltbgtltfont color=quot#c41230quotgtO(1)lt/fontgtlt/bgt，随机访问

ltbgt链表lt/bgt

线性表的链式存储

ltbgt单链表lt/bgt

基本操作

建立单链表：ltbgtltfont color=quot#c41230quotgt头插法lt/fontgtlt/bgt(头结点之后)、ltbgtltfont color=quot#c41230quotgt尾插法lt/fontgtlt/bgt(尾结点之后)

删除nbsp nbsp时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，不需要移动元素

查找nbsp nbsp时间复杂度：ltbgtltfont color=quot#c41230quotgtO(n)lt/fontgtlt/bgt，不需要移动元素，顺序访问

ltbgt循环链表lt/bgt

尾结点指向下一个节点的指针不是NULL，而是头结点

若常做操作在表头表尾，可对循环链表不设头指针而仅设尾指针，提高效率

ltbgt双向链表lt/bgt

在单链表的机车上增加一个指向前驱结点的指针

ltbgt静态链表lt/bgt

借用数组来描述链表(非顺序存储)

ltbgt栈、队列、数组lt/bgt

ltbgt栈nbsplt/bgt

后进先出的线性表，抽象数据结构

栈的顺序存储(类似顺序表)，插入删除操作均在表尾

ltbgt栈的链式存储lt/bgt

优点：便于多个栈共享存储空间和提高效率，且不存在栈满上溢

共享栈：栈底在共享空间两端，栈顶向空间中部延伸

用不带头节点的单链表实现，指针指向栈顶，所有操作均在栈顶完成

ltbgt合法出栈个数：C(上标2n 下标n)/(n+1)lt/bgtnbsp

ltbgt应用lt/bgt

ltfont color=quot#0076b3quotgtltbgt括号匹配lt/bgtlt/fontgt

左括号则入栈

右括号，若匹配则弹出栈顶，不匹配则序列非法

遍历完毕，若栈非空则序列非法

ltbgtltfont color=quot#0076b3quotgt表达式求值lt/fontgtlt/bgt

中缀表达式转化为后缀/前缀表达式

简便做法

1.按优先级对所有运算单位加括号

前缀：把运算符移到对应括号前

后缀：把运算符移到对应括号后

3.去掉括号

ltfont color=quot#0076b3quot style=quotquotgtltbgt递归转化为非递归常使用栈来完成lt/bgtlt/fontgt

ltbgt队列lt/bgt

先进先出的线性表，队头删除队尾插入，抽象数据结构，

队列的顺序存储，两个指针分别指向队头队尾

队列的链式存储，两个指针分别指向头结点和尾结点

ltbgt循环队列lt/bgt

ltbgt队列长度：ltfont color=quot#c41230quotgt(Q.rear+MaxSize-Q.front)%MaxSizelt/fontgtlt/bgt

ltbgt判空/满lt/bgt

牺牲一个存储单元nbsp nbspltbgtltfont color=quot#c41230quotgtnbspnbsplt/fontgtlt/bgtltbgtltfont color=quot#c41230quotgtlt/fontgtlt/bgt

空:ltbgtltfont color=quot#c41230quotgtQ.rront==Q.rearlt/fontgtlt/bgt

满:ltbgtltfont color=quot#c41230quotgtQ.front==(Q.rear+1)%MaxSizelt/fontgtlt/bgt

增加记录个数的变量(Q.size)nbsp nbspltbgtltfont color=quot#c41230quotgtlt/fontgtlt/bgt

空:ltbgtltfont color=quot#c41230quotgtQ.size==0nbspnbsplt/fontgtlt/bgt

满:ltfont color=quot#c41230quotgtltbgtQ.size==MaxSizelt/bgtlt/fontgt

增加tag标识nbsp nbspltbgtltfont color=quot#c41230quotgtlt/fontgtlt/bgt

空:ltbgtltfont color=quot#c41230quotgtQ.rront==Q.rear tag==0nbspnbsplt/fontgtlt/bgt

满:ltbgtltfont color=quot#c41230quotgtQ.rront==Q.rear tag==1lt/fontgtlt/bgt

ltbgt应用：lt/bgtltfont color=quot#0076b3quot style=quotfont-weight: boldquotgt树的层次遍历一般利用队列完成lt/fontgt

ltbgt数组lt/bgt

逻辑结构。线性表的推广，每个元素受到n个线性关系的约束

存储结构：多用顺序存储

ltbgt应用：ltfont color=quot#0076b3quotgt特殊矩阵的压缩存储lt/fontgtlt/bgt

目标：节约存储空间；方法：不存储0，多值相同存储一个

ltbgt对称矩阵lt/bgt

需ltbgtltfont color=quot#c41230quotgtn(n+1)/2lt/fontgtlt/bgt个单元空间

元素aij与他的存储位置sa[k]的关系

ltbgtk=lt/bgt

ltbgtltfont color=quot#c41230quotgti(i-1)/2+j-1lt/fontgtlt/bgtnbsp ltbgt当i≥jlt/bgt

ltbgtltfont color=quot#c41230quotgtj(j-1)/2+i-1lt/fontgtlt/bgtnbsp ltbgt当i＜jlt/bgt

ltbgt三角矩阵lt/bgt

需ltbgtltfont color=quot#c41230quotgtn(n+1)/2+1lt/fontgtlt/bgt个单元空间

元素aij与他的存储位置sa[k]的关系

ltbgt上三角区，k=lt/bgt

ltbgtltfont color=quot#c41230quotgtn(n+1)/2lt/fontgtnbsp 当i＞jlt/bgt

ltbgtltfont color=quot#c41230quotgt(i-1)(2n-i+2)/2+j-ilt/fontgtnbsp 当i≤jlt/bgt

ltbgt下三角区，k=lt/bgt

ltbgtltfont color=quot#c41230quotgti(i-1)/2+j-ilt/fontgtnbsp 当i≥jlt/bgt

ltbgtltfont color=quot#c41230quotgtn(n+1)/2lt/fontgtnbsp 当i＜jlt/bgt

ltbgt对角矩阵lt/bgt

中心地带宽为d，非0元素(2d+1)*n-(1+d)*d个

元素aij与他的存储位置sa[k]的关系 ltbgtltfont color=quot#c41230quotgtk=2i+j-3lt/fontgtlt/bgt

ltbgt稀疏矩阵lt/bgt

利用三元组(行标，列标，值)存储

稀疏矩阵压缩后，失去了随机存取的特性

ltbgt树与二叉树lt/bgt

ltbgt树lt/bgt

概念

度：该结点的子结点个数，树中最大的度称为树的度

高/深度：叶子结点向上数为高度，根节点向下数为深度，最大高/深度为树的高/深度

有/无序树：树中结点的各子树从左向右是否有序

性质

ltbgtnlt/bgt个结点的树，只有ltbgtn-1lt/bgt条边

结点数=所有结点的度+1

度为ltbgtmlt/bgt的树中第ltbgtilt/bgt层上至多有ltbgtmⁱ⁻¹lt/bgt个结点(i≥1)

ltbgtnlt/bgt个结点的ltbgtmlt/bgt叉树最小高度为ltbgtlogₘ(n(m-1))+1lt/bgt（取上界）

结点为nbspltbgtltfont color=quot#c41230quotgtilt/fontgtlt/bgt，双亲ltbgtltfont color=quot#c41230quotgt[i/2]lt/fontgtlt/bgt(取下界)，左孩子ltbgtltfont color=quot#c41230quotgt2ilt/fontgtlt/bgt，右孩子ltbgtltfont color=quot#c41230quotgt2i+1lt/fontgtlt/bgt

ltbgt二叉树lt/bgt

概念

ltbgt满二叉树lt/bgt：深度为ltbgtnlt/bgt，有ltbgtltfont color=quot#c41230quotgt2ⁿ-1lt/fontgtlt/bgt个结点

ltbgt完全二叉树lt/bgt：n个结点的完全二叉树中结点在对应满二叉树中编号1-n

性质

二叉树第ltbgt i lt/bgt层上至多有nbspltfont color=quot#c41230quot style=quotfont-weight: boldquotgt2ⁱ⁻¹ lt/fontgtltfont color=quot#000000quot style=quotquotgt个结点lt/fontgt

深度为ltbgtnlt/bgt的二叉树至多有ltbgtltfont color=quot#c41230quotgt 2ⁿ-1 lt/fontgtlt/bgt个结点

非空二叉树叶子结点数等于度为ltbgtltfont color=quot#c41230quotgt2lt/fontgtlt/bgt的节点数ltbgtltfont color=quot#c41230quotgt+1lt/fontgtlt/bgt

ltbgtnlt/bgt个结点的完全二叉树ltfont color=quot#000000quotgtlt/fontgt

深度为ltbgtltfont color=quot#c41230quotgt log₂(n+1)lt/fontgtlt/bgt(取上界)

ltbgtinbsplt/bgt的双亲是ltbgti/2lt/bgt(取下界)

ltbgtilt/bgt 的左孩子是ltbgt2ilt/bgt，若2igtn，则无左孩子

ltbgti lt/bgt的右孩子是ltbgt2i+1lt/bgt，若2i+1gtn则无右孩子

存储结构

顺序存储：用数组把编号 i 的结点存放在 i-1 处，适用于存储完全二叉树

链式存储(二叉链表)

用二叉链表存储ltbgtnlt/bgt个结点的二叉树，共有ltbgtn+1lt/bgt个ltbgt空指针域lt/bgt

用三叉链表存储n个结点的二叉树，共有n+2个空指针域

二叉树的遍历

ltbgt层次遍历lt/bgt

方法：从上至下、从左至右、利用队列

思路

将根放入队列，若队列不空则取队头元素p

若p不空则访问，将其左右子树入列

循环直至队空

ltbgt先序遍历：根-左-右lt/bgt

ltbgt中序遍历：左-根-右lt/bgt

ltbgt后序遍历：左-右-根lt/bgt

先序/后序/层次+中序，可以确定ltbgt唯一二叉树，lt/bgt先序+后序不唯一

ltbgt线索二叉树lt/bgt

线索：利用空指针指向前驱或后继结点

ltbgtlchild ltfont color=quot#f15a23quotgt|lt/fontgt LTag ltfont color=quot#c41230quotgt|lt/fontgt data ltfont color=quot#c41230quotgt|lt/fontgt RTag ltfont color=quot#c41230quotgt| lt/fontgtrchildlt/bgt

LTag/RTag=

ltbgt0nbsplt/bgt lchild/rchild域指向左/右孩子

ltbgt1lt/bgtnbsp lchild/rchild域指向前驱/后继

画线索二叉树：先写遍历序列，再画线索

ltbgt二叉排序树lt/bgt

特点：左小右大

判别：中序遍历得到结果从小到大有序

ltbgt查找lt/bgt

与根比较大小，大则去右子树，小则去左子树

平均查找长度：ltbgtltfont color=quot#c41230quotgt(n+1)/2lt/fontgtlt/bgt

ltbgt插入lt/bgt：先查找，无插入节点再将其插入最后访问节点的ltbgtltfont color=quot#c41230quotgt孩子nbsplt/fontgtlt/bgt

ltbgt删除lt/bgt