数据结构树的建造（数据结构你真的懂了吗）

数据结构树的建造（数据结构你真的懂了吗）结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；堂兄结点：同一层上结点；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点；

树和二叉树

一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。

基本术语：

树结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子；

双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；

兄弟结点：同一双亲的孩子结点；

堂兄结点：同一层上结点；

结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的高（深）度：树中最大的结点层

结点的度：结点子树的个数

树的度： 树中最大的结点度。

叶子结点：也叫终端结点，是度为0的结点；

分枝结点：度不为0的结点（非终端结点）；

森林：互不相交的树集合；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；

二叉树

二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。注意区分：二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树

二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。

二叉树与树是不同的，二叉树不等价于分支树最多为二的有序树。当一个结点只包含一个子节点时，对于有序树并无左右孩子之分，而对于二叉树来说依然有左右孩子之分，所以二叉树与树是两种不同的结构。

性质：

在二叉树的第 i 层上至多有2i-1个结点。

深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为 2 的结点，则必存在关系式：n0= n2 1。

具有 n 个结点的完全二叉树的深度为⎣log2 n⎦ 1 。

n个结点的二叉树中，完全二叉树具有最小的路径长度。

如果对一棵有n个结点的完全二叉树的结点按层序编号 则对任一结点i（1<=i<=n) 有：

如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲的编号是 i/2(整除）。

如果2i>n，无左孩子；否则，其左孩子是结点2i。

如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。

二叉树的存储结构

顺序存储结构：仅仅适用于满或完全二叉树，结点之间的层次关系由性质5确定。

二叉链表法：每个节点存储左子树和右子树。三叉链表：左子树、右子树、父节点，总的指针是n 2

在有n个结点的二叉链表中，值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外，其余N-1个结点都有一个父结点。所以，一共有N-1个非空链域，其余2N-(N-1)=N 1个为空链域。

二叉链存储法也叫孩子兄弟法，左指针指向左孩子，右指针指向右兄弟。而中序遍历的顺序是左孩子，根，右孩子。这种遍历顺序与存储结构不同，因此需要堆栈保存中间结果。而中序遍历检索二叉树时，由于其存储结构跟遍历顺序相符，因此不需要用堆栈。

遍历二叉树和线索二叉树

遍历二叉树：使得每一个结点均被访问一次，而且仅被访问一次。非递归的遍历实现要利用栈。

先序遍历DLR：根节点->左子树->右子树

中序遍历LDR：左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序

后续遍历LRD：左子树->右子树->根节点。需要栈的支持。

层次遍历：用一维数组存储二叉树时 总是以层次遍历的顺序存储结点。层次遍历应该借助队列。

线索二叉树：对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。

如何线索化？以中序遍历为例，若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。前驱就是在这一点之前走过的点，不是下一将要去往的点。

加上结点前趋后继信息（结索）的二叉树称为线索二叉树。n个结点的线索二叉树上每个结点有2个指针域（指向左孩子和右孩子），总共有2n个指针域；一个n个结点的树有n-1条边，那么空指针域= 2n - (n-1) = n 1，即线索数为n 1。指针域tag为0，存放孩子指针，为1，存放前驱/后继节点指针。

线索树下结点x的前驱与后继查找：设结点x相应的左（右）标志是线索标志，则lchild(rchild)就是前驱(后继），否则：

LDR–前驱：左子树中最靠右边的结点；后继：右子树中最靠左边的结点

LRD–前驱：右子树的根，若无右子树，为左子树跟。后继：x是根，后继是空；x是双亲的右孩子、x是双亲的左孩子，但双亲无右孩子，双亲是后继；x是双亲的左孩子，双亲有右孩子，双亲右子树中最左的叶子是后继

DLR–对称于LRD线索树—将LRD中所有左右互换，前驱与后继互换，得到DLR的方法。

为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点，约定：

头结点的lchild域：存放线索链表的根结点指针；

头结点的rchild域: 中序序列最后一个结点的指针；

中序序列第一结点lchild域指向头结点;

中序序列最后一个结点的rchild域指向头结点;

中序遍历的线索二叉树以及线索二叉树链表示意图

一棵左右子树均不空的二叉树在前序线索化后 其中空的链域的个数是1。前序和后续线索化后空链域个数都是1，中序是2。二叉树在线索化后，仍不能有效求解的问题是前序求前序先驱，后序求后序后继。

中序遍历的顺序为：左、根、右，所以对于每一非空的线索，左子树结点的后继为根结点，右子树结点的前驱为根结点，再递归的执行上面的过程，可得非空线索均指向其祖先结点。在中序线索二叉树中 每一非空的线索均指向其祖先结点。

在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历 此时，不需栈，也不需递归。基本步骤：

p=T->lchild; p指向线索链表的根结点；

若线索链表非空，循环：

循环，顺着p左孩子指针找到最左下结点；访问之；

若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环： p=p->rchild； 并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）

一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p->rchild，使 p指向右孩子结点；

树和森林

树的存储结构：

双亲表示法

孩子表示法

利用图表示树

孩子兄弟表示法（二叉树表示法）：链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点

将树转化成二叉树：右子树一定为空

加线：在兄弟之间加一连线

抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系

旋转：以树的根结点为轴心，将整树顺时针转45°

森林转换成二叉树：

将各棵树分别转换成二叉树

将每棵树的根结点用线相连

以第一棵树根结点为二叉树的根

树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历

哈弗曼树/霍夫曼树

一些概念

路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；

路径长度：路径上的分支数目称为路径长度；

树的路径长度：从根到每个结点的路径长度之和。

结点的权：根据应用的需要可以给树的结点赋权值；

结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；

树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li

哈夫曼树：假设有n个权值(w1 w2 … wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。

前缀码的定义：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码，可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树，若有n个节点，则共有(n 1)/2个码子

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。哈夫曼树的结点个数必为奇数。

哈夫曼树不一定是完全二叉树，但一定是最优二叉树。

若度为m的哈夫曼树中 其叶结点个数为n 则非叶结点的个数为[(n-1)/(m-1)]。边的数目等于度。

图遍历与回溯

图搜索->形成搜索树

穷举法。

贪心法。多步决策，每步选择使得构成一个问题的可能性，同时满足目标函数。

回溯法。根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理。

图

无向图

回路或环：第一个顶点和最后一个顶点相同的路径。

简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路

连通：顶点v至v’ 之间有路径存在

连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。

连通分量：极大连通子图，子图中包含的顶点个数极大

所有顶点度的和必须为偶数

有向图：

回路或环：第一个顶点和最后一个顶点相同的路径。

简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。

连通：顶点v至v’之间有路径存在

强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。

强连通分量：极大连通子图

有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度

生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。

完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。

有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。

一个无向图 G=(V E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。如果 G=(V E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。

图的存储形式

邻接矩阵和加权邻接矩阵

无权有向图：出度: i行之和；入度: j列之和。

无权无向图：i结点的度: i行或i列之和。

加权邻接矩阵：相连为w，不相连为∞

邻接表

用顶点数组表、边（弧）表表示该有向图或无向图

顶点数组表：用数组存放所有的顶点。数组大小为图顶点数n

边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。

n个顶点的无向图的邻接表最多有n(n-1)个边表结点。有n个顶点的无向图最多有n*(n-1)/2条边，此时为完全无向图，而在邻接表中每条边存储两次，所以有n*(n-1)个结点

图的遍历

深度优先搜索利用栈，广度优先搜索利用队列

求一条从顶点i到顶点s的简单路径–深搜。求两个顶点之间的一条长度最短的路径–广搜。当各边上的权值均相等时 BFS算法可用来解决单源最短路径问题。

生成树和最小生成树

每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。

生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边 在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图

最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。

Kruskal算法：令最小生成树集合T初始状态为空，在有n个顶点的图中选取代价最小的边并从图中删去。若该边加到T中有回路则丢弃，否则留在T中；依此类推，直至T中有n-1条边为止。

Prim算法、Kruskal算法和Dijkstra算法均属于贪心算法。

Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。

Dijkstra算法解决了从某个原点到其余各顶点的最短路径问题，由循环嵌套可知该算法的时间复杂度为O(N*N)。若要求任一顶点到其余所有顶点的最短路径，一个比较简单的方法是对每个顶点当做源点运行一次该算法，等于在原有算法的基础上，再来一次循环，此时整个算法的复杂度就变成了O(N*N*N)。

Bellman-Ford算法解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值。该算法返回一个布尔值，以表明是否存在一个从源节点可以到达的权重为负值的环路。如果存在这样一个环路，算法将告诉我们不存在解决方案。如果没有这种环路存在，算法将给出最短路径和它们的权重。

双连通图和关节点

若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。

若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。

没有关节点的连通图为双连通图

若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；

对生成树上的任意一个非叶“顶点”，若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。

有向无环图及其应用

拓扑排序。在用邻接表表示图时 对有n个顶点和e条弧的有向图而言时间复杂度为O(n e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。拓扑序列唯一不能唯一确定有向图。

AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。

拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。

拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：

在有向图中选一个没有前驱的顶点且输出之

从图中删除该顶点和所有以它为尾的弧

重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止(此时说明图中有环）

采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路).深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。

算法描述：

把邻接表中入度为0的顶点依此进展

若站不空，则

栈顶元素vj退栈并输出；

在邻接表中查找vj的直接后继vk，把vk的入度减1；若vk的入度为0则进栈

若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。

AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。

一些定义：

事件的最早发生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间。

事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间。

活动ai由弧

查找

顺序查找、折半查找、索引查找、分块查找是静态查找，动态查找有二叉排序树查找，最优二叉树查找，键树查找，哈希表查找

静态查找表

顺序表的顺序查找：应用范围：顺序表或线性链表表示的表，表内元素之间无序。查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。

顺序有序表的二分查找。平均查找时间(n 1)/n log2(n 1)

分块查找：将表分成几块，块内无序，块间有序，即前一块中的最大值小于后一块中的最小值。并且有一张索引表，每一项存放每一块的最大值和指向该块第一个元素的指针。索引表有序，块内无序。所以，块间查找用二分查找，块内用顺序查找，效率介于顺序和二分之间；先确定待查记录所在块，再在块内查找。因此跟表中元素个数和块中元素个数都有关。

用数组存放待查记录

建立索引表，由每块中最大（小）的关键字及所属块位置的信息组成。

当索引表较大时，可以采用二分查找

在数据量极大时，索引可能很多，可考虑建立索引表的索引，即二级索引，原则上索引不超过三级

分块查找平均查找长度：ASLbs = Lb Lw。其中，Lb是查找索引表确定所在块的平均查找长度， Lw是在块中查找元素的平均查找长度。在n一定时，可以通过选择s使ASL尽可能小。当s=sqrt(n)时，ASL最小。

时间：顺序查找最差，二分最好，分块介于两者之间

空间：分块最大，需要增加索引数据的空间

顺序查找对表没有特殊要求

分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。

二分查找要求表有序，所以若表的元素的插入与删除很频繁，维持表有序的工作量极大。

在表不大时，一般直接使用顺序查找。

动态查找

二叉排序树的结点删除：

x为叶子结点，则直接删除

x只有左子树xL或只有右子树xR 则令xL或xR直接成为双亲结点f的子树；

x即有左子树xL也有右子树xR，在xL中选值最大的代替x，该数据按二叉排序树的性质应在最右边。

平衡二叉树：每个结点的平衡因子都为 1、－1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树。

平衡二叉树的平衡：

左调整(新结点插入在左子树上的调整)：

LL(插入在结点左子树的左子树上)：旋转前后高度都为h 1

LR(新插入结点在左子树的右子树上)：旋转前后高度仍为h 1

右调整(新结点插入在右子树上进行的调整):

RR(插入在的右子树的右子树上)：处理方法和 LL对称

RL(插入在的右子树的左子树上)：处理方法和 LR对称

平衡树建立方法：

按二叉排序树插入结点

如引起结点平衡因子变为|2|，则确定旋转点，该点是离根最远（或最接近于叶子的点）

确定平衡类型后进行平衡处理，平衡后以平衡点为根的子树高不变

最小二叉平衡树的节点的公式如下 F(n)=F(n-1) F(n-2) 1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

常见的平衡二叉树：

红黑树是平衡二叉树，也就是左右子树是平衡的，高度大概相等。这种情况等价于一块完全二叉树的高度，查找的时间复杂度是树的高度，为logn，插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)

节点是红色或黑色。

根是黑色。

所有叶子都是黑色（叶子是NIL节点）。

每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。

avl树也是自平衡二叉树；红黑树和AVL树查找、插入、删除的时间复杂度相同；包含n个内部结点的红黑树的高度是o(logn); TreeMap 是一个红黑树的实现，能保证插入的值保证排序

STL和linux多使用红黑树作为平衡树的实现：

如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。

其次，AVL的结构相较RB-Tree来说更为平衡，再插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。

map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。

查找总结

既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找。二叉排序树查找，最优二叉树查找，键树查找，哈希法查找是动态查找。分块、顺序、折半、索引顺序查找均为静态。分块法应该是将整个线性表分成若干块进行保存，若动态变化则可以添加在表的尾部（非顺序结构），时间复杂度是O(1)，查找复杂度为O(n)；若每个表内部为顺序结构，则可用二分法将查找时间复杂度降至O(logn)，但同时动态变化复杂度则变成O(n)；顺序法是挨个查找，这种方法最容易实现，不过查找时间复杂度都是O(n)，动态变化时可将保存值放入线性表尾部，则时间复杂度为O(1)；二分法是基于顺序表的一种查找方式，时间复杂度为O(logn)；通过哈希函数将值转化成存放该值的目标地址，O（1）

二叉树的平均查找长度为O(log2n)——O(n).二叉排序树的查找效率与二叉树的高度有关，高度越低，查找效率越高。二叉树的查找成功的平均查找长度ASL不超过二叉树的高度。二叉树的高度与二叉树的形态有关，n个节点的完全二叉树高度最小，高度为[log2n] 1 n个节点的单只二叉树的高度最大，高度为n，此时查找成功的ASL为最大(n 1)/2，因此二叉树的高度范围为[log2n] 1——n.

链式存储不能随机访问，必须是顺序存储

B_树的B 树

B_树

B-树就是B树。m阶B_树满足或空，或为满足下列性质的m叉树：

树中每个结点最多有m棵子树

根结点在不是叶子时，至少有两棵子树

除根外，所有非终端结点至少有⎡m/2⎤棵子树

有s个子树的非叶结点具有 n = s-1个关键字，结点的信息组织为:(n A0 K1 A1 K2 A2 … Kn，An)。这里：n为关键字的个数，ki（i=1 2 … n)为关键字，且满足Ki小于Ki 1 ，Ai(i=0 1 ..n)为指向子树的指针。

所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。

关键字集合分布在整棵树中

任何一个关键字出现且只出现在一个结点中

搜索有可能在非叶子结点结束

其搜索性能等价于在关键字全集内做一次二分查找

只适用于随机检索，不适用于顺序检索。

有结点的平衡因子都为零

M阶B-树中含有N个关键字，最大深度为log⎡m/2⎤(n 1)/2 2

B_树中结点的插入

m代表B_树的阶，插入总发生在最低层

插入后关键字个数小于等于 m-1 完成。

插入后关键字个数等于m 结点分裂，以中点数据为界一分为二，中点数据放到双亲结点中。这样就有可能使得双亲结点的数据个数为m 引起双亲结点的分裂，最坏情况下一直波及到根，引起根的分裂——B_树长高。

3阶B_树的插入。每个结点最多3棵子树，2个数据；最少2棵子树，1个数据。所以3阶B_树也称为2-3树。

B_树中结点的删除

删除发生在最底层

被删关键字所在结点中的关键字数目大于等于 m/2 ，直接删除。

删除后结点中数据为⎡m/2⎤-2，而相邻的左（右）兄弟中数据大于⎡m/2⎤-1，此时左（右兄弟）中最大（小）的数据上移到双亲中，双亲中接（靠）在它后（前）面的数据移到被删数据的结点中

其左右兄弟结点中数据都是⎡m/2⎤-1，此时和左（右）兄弟合并，合并时连同双亲中相关的关键字。此时，双亲中少了一项，因此又可能引起双亲的合并，最坏一直到根，使B-树降低一层。

删除不在最底层

在大于被删数据中选最小的代替被删数据，问题转换成在最底层的删除

B 树

在实际的文件系统中，用的是B 树或其变形。有关性质与操作类似于B_树。

差异：

有n棵子树的结点中有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。

所有叶子结点中包含全部关键字信息，及对应记录位置信息及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)

所有非叶子为索引，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B树的非终节点也包含需要查找的有效信息)

非叶最底层顺序联结，这样可以进行顺序查找

B 特性

所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

不可能在非叶子结点命中

非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层

更适合文件索引系统

B 树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)

查找过程

在 B 树上，既可以进行缩小范围的查找，也可以进行顺序查找；

在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；

若在结点内查找时，给定值≤Ki， 则应继续在 Ai 所指子树中进行查找

插入和删除的操作：类似于B_树进行，即必要时，也需要进行结点的“分裂”或“合并”。

为什么说B tree比B树更适合实际应用中操作系统的文件索引和数据库索引？

B tree的磁盘读写代价更低

B tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘块。而B 树内部结点只需要1个盘块。当需要把内部结点读入内存中的时候，B树就比B 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

B tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

B树和B 树都是平衡的多叉树。B树和B 树都可用于文件的索引结构。B树和B 树都能有效的支持随机检索。B 树既能索引查找也能顺序查找.