数据结构知识点-个人笔记

数据结构知识点-个人笔记《数据结构与算法》复习第1部分：1.概念：数据结构、存储结构、逻辑结构注：磁盘文件管理系统是树状结构。1.1基本概念(1)数据：指所有能够输入到计算机中并被计算机程序处理的符号的总称，范围广泛，包括图像和声音等。(2)数据项：数据的不可分割的最小单元。(3)数据元素：是数据的基本单位，由若干数据项组成，通常作为一个整体考虑。(4)数据对象：性质相同的数据元素的集合，是数据的一个子集。例如：表A和表B都是数据对象，每张表中的每一行就称为数据元素，姓名、性别、身高、科目、分数就称为数据项。1.2数据结构定义：相互之间存在一种或多种特定关系的数据元素的集合，这种关系包括三方面的内容，即数据逻辑结构、数据存储结构、数据的操作。数据结构数据逻辑结构数据存储结构数据的操作集合树形结构图形结构线性结构顺序存储链式存储读取、修改、插入、删除等把逻辑上相邻的元素存放在物理位置上相邻的单元使用指针把有关联的元素链接起来，不用物理地址相连2.数据元素是组成数据的基本单位。3.算法、算法分析、算法特性、时间复杂度3.1算法：描述求解问题方法操作步骤的集合。不是所有的程序都是算法，要满足五个特性。算法的基本特性好算法的指标有穷性正确性确定性健壮性有输入可读性有输出可行性高时间效率（主）高空间效率（次重）3.2时间复杂度3.2.1定义：在算法分析中，一般用算法中的语句的执行次数来度量算法的时间效率，时间效率也就是时间复杂度。3.2.2计算方法：对于问题规模为n的某个函数f(n)，算法时间复杂度记为T(n)，存在一个正常数c，使cf(n)>T(n)恒成立，则T(n)=O(f(n))，称O(f(n))为时间复杂度。时间复杂度的大O表示法：保留最高次数项，令最高次数项的系数为1。例如O(8)→O(1)，O(2n^3+2n^2)→O(n^3)，O(n*log2n)第2部分1.线性表的概念、特点、存储结构线性表是一种线性结构，具有以下特点：-数据元素之间存在一对一的线性关系；-线性表中必有一个唯一的“第一个”数据元素；-线性表中必有一个唯一的“最后一个”数据元素；-除第一个和最后一个数据元素外，其他数据元素均有且只有一个直接前驱和一个直接后继。线性表的存储结构有两种形式：顺序存储和链式存储。顺序存储是将数据元素顺序存放在一块连续的存储空间中，链式存储则是使用指针将数据元素链接起来，不要求存储空间连续。线性表的操作包括读取、修改、插入、删除等。顺序表的存储方式存在以下缺点：对于元素较多的顺序表，插入和删除操作需要移动大量元素，效率低下；同时需要预先分配足够的空间，可能导致大量空间浪费或数据溢出。相反，链式表的优缺点与顺序表相反。因此，在选择存储方式时，若需要频繁进行插入删除操作且元素数量较大，建议使用链式存储；若按照序号访问元素时，建议使用顺序表存储，因为时间效率为O(1)。关于字符串的基本操作，模式匹配指的是在主串S中查找子串T第一次出现的位置。串是由一个或多个字符序列组成的有限序列，可以看作是数据元素为单个字符的特殊线性表。空串表示为空格数，而非空格串。串的存储类型有顺序存储和链式存储两种。顺序存储包括定长顺序存储结构和堆分配存储结构，而链式存储则是通过指针实现。朴素模式匹配算法（BP算法）的核心思想是比较主串S和子串T中每个字符，若相等则继续比较下一个字符，若不相等则将子串向右移动一个字符再继续比较。BP算法的时间复杂度为O(mn)，效率不高。而KMP算法则尽量利用已经得到的“部分匹配”的结果信息，不让i回溯，加快子串右滑的速度，问题由子串决定而不是主串决定的。KMP算法中使用了next数组，它是一个智能数组，指导子串下一步改用几号元素去匹配。其中，next[1]和next[2]永远为1，其余next[n]看n位的前后缀的相同数目。求解KMP算法中的next数组给定主串S=“bbsbbcdfbb”和子串T=“bbsbbs”，求解T的next数组。首先，我们需要了解什么是KMP算法和next数组。KMP算法是一种字符串匹配算法，用于在一个主串中查找一个子串的出现位置。而next数组则是KMP算法中的一个重要概念，它存储了子串中前缀和后缀相等的最大长度。接下来我们来求解T的next数组。首先，我们将T分为两部分，即前缀和后缀。可以发现，T的前缀和后缀有重叠部分“bbs”，因此我们只需要求解这部分的最大长度即可。对于一个长度为i的子串，它的前缀和后缀相等的最大长度记为next[i]。因此，我们可以通过递推的方式求解next数组。具体来说，我们从next[1]开始递推，假设已知next[1]到next[i-1]的值，现在要求解next[i]的值。首先，我们将T的前缀和后缀分别表示为P和S，其中P表示前缀，S表示后缀，且P和S的长度相等。然后，我们将P和S的长度都减1，得到P'和S'。如果P'和S'相等，那么next[i]=next[i-1]+1；否则，我们将P'缩短为next[next[i-1]]，然后继续比较P'和S'，直到找到相等的前缀和后缀，或者P'缩短到长度为0为止。根据上述递推公式，我们可以得到T的next数组为：next[1]=0next[2]=1next[3]=0next[4]=2next[5]=2next[6]=3因此，T的next数组为{0,1,0,2,2,3}。栈的基本概念与特点栈和队列是线性表的两种特殊形式，它们的操作受到限制。栈是一种后进先出（LIFO）的线性表，类似于装电池，只能对栈顶进行操作。栈有两种存储方式，即顺序存储和链式存储。顺序存储的栈使用数组来存储元素，栈顶指针指向栈顶元素。入栈操作将元素插入栈顶，出栈操作将栈顶元素弹出。判空操作检查栈顶指针是否为0，如果为0则栈为空。链式存储的栈使用链表来存储元素，栈顶指针指向链表头结点。入栈操作将元素插入链表头结点之后，出栈操作将链表头结点的下一个结点作为新的栈顶结点。判空操作检查链表头结点是否为null，如果为null则栈为空。栈的两种存储结构的基本操作栈的基本操作包括入栈、出栈、取栈顶和判空。对于顺序存储的栈，入栈操作将元素插入栈顶，出栈操作将栈顶元素弹出，取栈顶操作返回栈顶元素，判空操作检查栈顶指针是否为0。对于链式存储的栈，入栈操作将元素插入链表头结点之后，出栈操作将链表头结点的下一个结点作为新的栈顶结点，取栈顶操作返回链表头结点的下一个结点的元素，判空操作检查链表头结点是否为null。如何实现栈的入栈和出栈操作？对于顺序存储的栈，入栈操作只需要将元素插入栈顶即可，即S->stack[S->top]=x，然后将栈顶指针加1，即S->top++。出栈操作只需要将栈顶指针减1即可，即S->top--。对于链式存储的栈，入栈操作需要先创建一个新的结点，然后将新结点插入链表头结点之后，即p->next=head->next，head->next=p。出栈操作需要先将链表头结点的下一个结点作为新的栈顶结点，然后释放原来的栈顶结点，即head->next=head->next->next，free(p)。如何判断栈是否为空？对于顺序存储的栈，判断栈是否为空只需要检查栈顶指针是否为0，即if(S->top==0)。对于链式存储的栈，判断栈是否为空只需要检查链表头结点是否为null，即if(head->next==null)。栈的应用举例栈是一种常见的数据结构，具有后进先出的特点。栈的应用非常广泛，下面介绍几个常见的应用。进制转换进制转换是栈的一个重要应用。在计算机中，二进制、八进制和十六进制都是常见的数字表示方式。将一个十进制数转换为其他进制数，可以通过不断地除以对应进制的数，将余数存入栈中，然后倒序输出即可。递归递归是一种常见的算法思想，也可以通过栈来实现。递归函数将自己调用，直到满足某个条件后才停止调用。在调用过程中，每个函数的返回值都需要存入栈中，以便在递归结束后依次取出。迷宫迷宫问题也可以通过栈来解决。在求解迷宫时，可以将每个可行的路径存入栈中，直到找到一条通往终点的路径。如果当前路径不通，则需要将栈顶元素弹出，回到上一个节点，继续探索其他路径。表达式求值表达式求值也是栈的一个重要应用。常见的表达式有中缀表达式、前缀表达式和后缀表达式。其中，前缀表达式和后缀表达式可以直接通过栈来求解，而中缀表达式需要先转换为后缀表达式，再通过栈来求解。队列的基本概念与特点队列是一种常见的数据结构，具有先进先出的特点。下面介绍队列的一些基本概念与特点。队列的特点队列的特点是先进先出，可以看做是排队买冰淇淋。队列只能对队头和队尾进行操作，不能对中间的元素进行操作。队列的存储方式队列的存储方式有两种，分别是顺序存储和链式存储。在顺序存储中，需要注意队头和队尾的位置。在链式存储中，需要定义节点类型和队列的结构体。假溢出问题假溢出是指队列中因为多次出队入队而导致的存储空间不足的问题。为了解决这个问题，可以使用循环队列。循环队列的实现方式是将队列的底层存储空间看做一个环，当队列的尾部到达存储空间的结尾时，就将尾部指针指向存储空间的开头。队列的基本操作队列的基本操作包括入队、出队、判空和判满。在判满时，可以使用计数器或标志位来判断队列是否已满。在判空时，只需要判断队头和队尾是否相等即可。对于假溢出问题，可以使用循环队列来解决。1.二叉树的第i层最多有2^(i-1)个结点。（其中i>=1）2.深度为k的二叉树最多有2^k-1个结点。（其中k>=1）3.对于任意一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。4.在任意一棵非空二叉树中，若n为叶子结点个数，n1为度为1的非叶子结点个数，则n=n1+1。5.具有n个结点的完全二叉树的深度为|log2n|+1（以2为底）。6.如果对一棵有n个结点的完全二叉树（其深度为|log2n|+1）的结点按层序编号，对于任意一个编号为i的结点：（1）如果i=1，则结点i是二叉树的根，无父节点；如果i>1，则其父节点编号为|i/2|。（2）如果2i>n，则结点i无左孩子；否则其左孩子的编号为2i。（3）如果2i+1>n，则结点i无右孩子；否则其右孩子的编号为2i+1。一颗非空二叉树的第i层上至多有2^i个节点。对于这个结论，我们可以通过画图来理解。比如第一层只有一个节点，第二层最多有两个节点，第三层最多有四个节点，以此类推。因此，第i层最多有2^i个节点。高度为k的二叉树最多有[2^(k+1)]-1个节点。这个结论可以通过满二叉树来理解。满二叉树是一种每个节点都有两个子节点的二叉树，因此在高度为k的满二叉树中，节点数为2^(k+1)-1。由于非满二叉树的节点数不会超过满二叉树，所以高度为k的非空二叉树最多有[2^(k+1)]-1个节点。若二叉树的叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。这个结论可以通过度数定理来证明。度数定理指出，对于一个有n个节点的树，其节点的度数之和等于2(n-1)。在二叉树中，叶子节点的度数为0，度为2的节点的度数为2，因此n0+2n2=2(n-1)，即n0=n2+1。完全二叉树是一种特殊的二叉树，其除了最后一层外，其他层都是满的，并且最后一层的节点都靠左排列。有n个节点的完全二叉树的高度k为[log2n]。这个结论可以通过画图来理解。比如对于一个有7个节点的完全二叉树，其高度为2，因为第一层有1个节点，第二层有2个节点，第三层有4个节点。有n个节点的完全二叉树若节点按层次编号(0开始)，则对于序号为i的节点有以下规律：•若2i+1<=n-1，则节点i的左孩子节点的序号为2i+1，否则没有左孩子。•若2i+2<=n-1，则节点i的右孩子节点的序号为2i+2，否则没有右孩子。这个结论可以通过画图来理解。比如对于一个有7个节点的完全二叉树，节点0的左孩子节点序号为1，右孩子节点序号为2，节点1的左孩子节点序号为3，右孩子节点序号为4，以此类推。在满二叉树中，叶子节点的个数比分支节点的个数多1。这个结论可以通过画图来理解。在满二叉树中，每个分支节点都有两个子节点，因此分支节点的个数是叶子节点个数减1。二叉树有两种存储方式：顺序存储和链式存储。顺序存储采用一组连续的存储单元存放二叉树的节点，没有节点的地方需要补上。链式存储用一条链表储存二叉树，一个节点有数据域和两个左右孩子的指针组成，若没有左/右孩子用^表示。线索二叉树是一种增加节点标志域的二叉树，利用这些指针把节点的前驱和后继的节点的信息连接起来，建立线索二叉树，主要是为了保留在各种遍历时得到的节点前驱和后继节点信息（即保留在各种遍历时产生的线性关系）。对于中序遍历，线索二叉树的结果是一条线性链表，其中每个节点的左指针指向前驱节点，右指针指向后继节点。其他遍历方式也可以建立线索二叉树。二叉树的遍历方式有三种：先序遍历、中序遍历和后序遍历。先序遍历的顺序是根左右，中序遍历的顺序是左根右，后序遍历的顺序是左右根。在递归实现遍历算法时，先访问当前节点，然后递归访问左子树和右子树。voidpostOrder(BNodep){if(p==NULL)return;postOrder(leftChild_btree(p));postOrder(rightChild_btree(p));visit(p);}3.二叉树的链式存储结构：每个节点包含数据域、左孩子指针和右孩子指针。4.二叉树的递归算法：中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。voidinOrder(BNodep){if(p==NULL)return;inOrder(leftChild_btree(p));visit(p);inOrder(rightChild_btree(p));}先序遍历：先访问根节点，再遍历左子树，最后遍历右子树。voidpreOrder(BNodep){if(p==NULL)return;visit(p);preOrder(leftChild_btree(p));preOrder(rightChild_btree(p));}后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。voidpostOrder(BNodep){if(p==NULL)return;postOrder(leftChild_btree(p));postOrder(rightChild_btree(p));visit(p);}求叶子结点算法：voidcountLeaf(BiTreeT,int*count){if(T){if((!T->lchild)&&(!T->rchild))(*count)++;countLeaf(T->lchild,count);countLeaf(T->rchild,count);}}5.哈夫曼算法及哈夫曼编码，WPL的计算5.1哈夫曼树相关概念：(1)路径长度：从A->B所经过的分支序列称路径，经过的分支个数称为路径长度。(2)带权路径长度：若二叉树中的叶节点都带有权值，从根节点到叶节点的路径长度与相应的叶节点权值乘积之和称为该树的带权路径长度（WPL）。WPL=∑wi*pi，i在[1,n]。(3)哈夫曼树：一组带权的叶节点可以构造多个二叉树，其中WPL最小的树称为哈夫曼树或最优二叉树。(4)假设哈夫曼树叶子节点的个数为m，则哈夫曼树的分支节点为m-1，总共节点个数为2m-1。5.2哈夫曼树的构造：原则是将权值大的结点靠近根。根节点的值等于所有叶子节点的权值之和。例子：用7，10，1,3,4,6,17构造一棵哈夫曼树。5.3哈夫曼树编码：在哈夫曼树中把每个节点引向左孩子上的边标为0，引向右孩子的边标为1，再从上至下写出节点的编码。6.二叉树与树的转换6.1树的表示方法：(1)父指针表示法(2)孩子链表表示法(3)孩子兄弟表示法，增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针，即左分支存放孩子节点，右分支存放兄弟节点。6.2树与二叉树的转换6.2.1树转为二叉树：1、树中同一结点的兄弟相连；2、保留结点的最左孩子连线，删除其它孩子连线；3、调整位置。6.2.2二叉树转为树：即把所有右孩子节点变为兄弟节点。6.2.3森林转为树。第i行中非0或非∞的元素个数。1.3邻接表——链式存储（1）邻接表：用一个一维数组存储图中顶点的信息，同时每个顶点vi的所有边相邻的顶点链成一个单链表，由于邻接表表示法不需要存储没有边的顶点之间的关系，因此对于稀疏图而言，邻接表的存储空间要远远小于邻接矩阵的存储空间。无向图：有向图：（2）邻接表的特点：a、邻接表需要额外的空间存储边的信息，但对于稀疏图而言，存储空间远远小于邻接矩阵。b、查找图中任一顶点的度需要遍历链表，效率相对较低。但是，对于有向图而言，可以直接查找顶点的入度或出度，效率较高。c、在邻接表中插入或删除一条边的操作比邻接矩阵更加高效。1.4图的遍历（1）深度优先遍历（DFS）：从某个顶点v出发，访问v，并依次访问v的邻接顶点w1、w2、…、wn，再依次从w1、w2、…、wn出发，访问它们的邻接顶点，直到所有可达顶点都被访问到。（2）广度优先遍历（BFS）：从某个顶点v出发，访问v，并依次访问v的所有邻接顶点w1、w2、…、wn，再依次访问它们的所有邻接顶点，直到所有可达顶点都被访问到。（3）图的遍历应用：a、连通性问题：检查图是否连通，求出连通分量等。b、拓扑排序：对有向图进行拓扑排序，求解工程问题等。c、关键路径：对有向图进行关键路径分析，求解工程问题等。d、最短路径：求解两个顶点之间的最短路径等。1.5图的应用（1）最小生成树：在连通图中，选择n个顶点，构成一棵树，使得这棵树的边权之和最小，称为最小生成树。（2）最短路径：在有向图或无向图中，求解两个顶点之间的最短路径。（3）网络流：在有向图或无向图中，求解网络的最大流或最小割问题。（4）匹配问题：在二分图中，求解最大匹配或最小点覆盖等问题。（5）图的着色：在图中对顶点进行染色，使得相邻顶点颜色不同，称为图的着色问题。本文介绍了图的存储结构和遍历算法，并介绍了最小生成树算法的两种实现方法：Prim算法和Kruskal算法。在图的存储结构方面，本文介绍了邻接表的实现方法，其中顶点信息被存储在一个一维数组中，每个顶点元素有data域和指针域，指针域存放该顶点的邻接表的第一个节点的地址。在遍历算法方面，本文介绍了深度优先遍历和广度优先遍历两种方法。深度优先遍历采用栈实现，从图中某个顶点出发，访问此顶点，然后依次从该顶点的未被访问的邻接顶点出发深度优先遍历图，直至图中所有和该顶点有路径相通的顶点都被遍历过。广度优先遍历采用队列实现，依次访问起始点的邻接点，然后再依次访问这些点中未被访问过的邻接点，直到所有顶点都被访问过为止。最后，本文介绍了最小生成树算法的两种实现方法：Prim算法和Kruskal算法。Prim算法通过从未落在生成树上的顶点集中选取顶点w加入生成树的顶点集合U，使得顶点w和已经在生成树上的顶点之间的边上的权值是在所有边中权值最小的条件，来构造最小生成树。Kruskal算法则通过将所有边按照权值从小到大排序，并依次加入生成树中，直到生成树中包含所有顶点为止。为了使生成树上的总权值最小，应该选择权值最小的边，直到选出n-1条不构成回路的最小边为止。Dijkstra算法是一种按照最短路径长度递增次序产生最短路径的算法，即将弧的权值之和取最小值的路径。AOV网是指用顶点表示活动，弧表示活动间的优先关系的有向图。AOE网是指用顶点表示事件，弧表示活动，弧上的权值表示活动所需时间构造的有向无环图。拓扑排序算法的步骤包括选择一个入度为0的顶点输出，删除所有以该顶点为尾的弧，重复执行直到找不到入度为0的顶点，若最终图中仍有顶点存在，不存在入度为0的点，则证明有环。关键路径是指AOE网中存在唯一的、入度为0的顶点，叫做源点，存在唯一的、出度为0的顶点，叫做汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。字典是由一些具有相同可辨认特性的数据元素构成的集合，关键字是数据元素中某个数据项的值，用它可以标识一个数据元素。检索是根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。常见的查找方法有静态查找和动态查找。静态查找包括顺序表的查找、二分查找等方法，动态查找包括散列查找、二叉搜索树查找、B树查找等方法。平均查找长度ASL是查找过程中对关键字需要执行的平均比较次数。存储：顺序表和链表都可以使用顺序表查找方法。1.2二分查找(折半查找)（1）基本思想：先将数据排序，形成有序表，然后将key与中间元素进行比较。若key小，则在前半部分查找；若key大，则在后半部分查找。在每个区域内再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。（2）对线性表的要求：需要按关键字排序，排序本身是一种费时的运算，所以二分法的时间复杂度最好也是O(nlog2n)，增加了算法的时间复杂度。（3）算法ASL=log2n（4）二分查找只适用于顺序存储结构的有序表，链表无法实现二分查找。（5）二分查找的比较次数(Ci)需要借用判定树来计算。判定树的画法：按照比较的次数生成判定树，比较1次的是根结点，比较2次的在第二层，比较3次的在第三层，以此类推。也可以说是每次的mid即形成判定树的结点，左子树上的结点是有序表前半部分的所有结点，右子树是后半部分的结点。判定树求平均成功平均查找长度和不成功平均查找长度的方法：例题：2．二分查找对线性表的要求，会写二分检索算法。代码如下：intBinarySearch(SequenceListR，ElemTypex){intlow=0，high=R.size-1，mid；while(low<=high){mid=(low+high)/2；if(R.list[mid].key==x.key)//判断mid是否=keyreturnmid；/*查找成功返回元素位置*/if(R.list[mid].key>x.key)//若key<mid则在mid左边的元素进行递归查找high=mid-1;//注意此时在设定high时不用加上midelse//若key>mid则在mid右边的元素进行递归查找low=mid+1；}//注意此时在设定low时不用加上midreturn-1}/*当low>high时表示查找区间为空，查找失败*/2.动态查找——二叉排序树——二叉搜索树（1）特征a、若左子树非空，则左子树的所有元素均小于根元素b．若右子树非空，则右子树的所有元素均大于根元素c.左右子树本身又各是一颗二叉排序树（2）二叉排序树可以通过树的中序遍历获得关键字的有序序列。1）散列函数的计算速度；2）散列函数的分布均匀程度；3）散列函数的存储空间利用率；4）散列函数的容错性。3.4拉链法拉链法是一种解决冲突的方法，它的基本思想是将所有散列值相同的元素存储在同一个链表中。当发生冲突时，只需要在相应的链表中查找即可。拉链法的优点是易于实现，存储空间利用率高，但查找效率较低，尤其是当链表长度过长时。总之，散列表是一种常用的数据结构，它能够快速地进行查找、插入和删除操作。在设计散列函数时需要考虑多个因素，选择合适的冲突解决方法也是非常重要的。i.计算哈希表函数所需时间ii.关键字长度iii.哈希表长度（哈希地址范围）iv.关键字分布情况v.记录查找频率3.4散列表解决冲突的方法3.4.1开放地址法：为发生冲突的关键码找到哈希表中最近的尚未被使用的位置。(1)计算第n位置查找成功的平均查找长度为：ASL1=(N1+N2+...+N10)/空间大小，其中N为每个元素查找成功的比较次数。(2)计算第n位置查找不成功时的比较次数为，第n位置到第一个没有数据位置的距离。找不成功的平均查找长度ASL2=(n1+n2+...+ni)/A，其中A为分配的所有空间，不是元素使用的空间（例如h(k)是%15，但是元素只使用了12格，则ASL1除以12，ASL2除以15）。例题：3.4.2拉链法：是把相互冲突的同义词用同一个单链表链接起来，若干组同义词可以组成若干个单链表。例题：给定关键字序列：19,14,23,1,68,20,84,27,55,11,10,79，h(k)=k%13，用拉链法解决冲突建立哈希表。4.二叉排序树的生成与删除，ASL的计算。5.AVL树的生成过程（如何调整），ASL的计算。5.1AVL树即平衡二叉树。(1)特点：要么是一颗空树，若非空则一定满足左子树和右子树都是平衡二叉树且左右子树深度之差不大于1。(2)平衡因子：当前节点的平衡因子定义为当前节点左子树的深度减右子树的深度。(3)最小不平衡子树：离插入节点最近，且平衡因子的绝对值大于1的节点为根的子树。5.2AVL树的平衡调整。1.目的：保证生成的二叉排序树的高度为log2n，从而使二叉排序树的插入，删除，查找等操作的平均时间为O(log2n)。所需调整的是最小不平衡子树，保证二叉树始终处于平衡状态。2.平衡调整模式：LL型调整，LR型调整，RR型调整，RL型调整。LL型调整LR型调整RR型调整RL型调整例题：关键字序列为：10，13，19，7，4，8，15，24，33，21。试用二叉排序树和平衡二叉树进行检索，给出检索15时需要的比较次数及成功检索的平均检索长度。第8部分1.排序的方法及比较。堆的定义。1.1排序算法优劣的判断标准：-时间复杂度（最重要）-最坏是O(n^2)单支树-空间复杂度（重要）-排序过程中使用的辅助空间-稳定性：算法按关键字多次排序得到结果，相同则稳定，否则不稳定。1.2堆的定义：堆是一种特殊的树形数据结构，每个节点都有一个值，通常所指的是优先队列。堆通常是一个可以被看做一棵树的数组对象。（以上是文章的全部内容，已经剔除了格式错误和明显有问题的段落，并进行了小幅度的改写）排序算法可以根据其实现方式和性质进行分类。其中，稳定性是一种重要的性质，指排序后相同元素的相对顺序是否改变。常用的排序算法包括直接插入排序、冒泡排序和归并排序，其中归并排序是稳定的。在时间复杂度方面，最好的排序算法可以看做是完全一棵二叉树，最好情况下时间复杂度为O(1)，最坏情况下为O(n)。不同的排序算法有不同的思想和实现方式。常见的排序算法包括选择排序、插入排序、交换排序和归并排序等。其中，直接选择排序的思想是从n个元素中找出关键字最小的记录，放在第一个位置，然后从剩余的元素中找出最小的记录，放在第二个位置，以此类推。其代码实现可以使用两层循环，每次找出最小值并交换位置。该算法的时间复杂度为O(n^2)，不稳定性取决于具体实现。堆排序算法的思想是将无序的n个元素建成一个完全二叉树，然后调整为小根堆或大根堆，输出堆顶元素并调整剩余元素，直至所有元素输出。该算法的时间复杂度为O(nlog2n)，空间复杂度为O(1)，可以用顺序存储创建堆。