二叉排序的时间复杂度_二叉树查找的时间复杂度

数据结构和算法学习记录 　　笔者毕业于某一本土木工程专业，毕业后自学转行到了互联网行业，做了一名前端开发工程师，写了3年多的前端。虽然我是非科班出身，但是一直有一颗想要弥补计算机科班课程的心。所以，基于当前就业市场和自身需求，决定从《数据结构和算法》开始学习。在这里，开了本篇文章，记录自己学习数据结构和算法的过程。 　　这里使用的课程是慕课网里面的浙大《数据结构》 　　课程共12讲，建议课时是48-96课时，包含了视频 文档 随堂测验 富文本 讨论等内容。 　　1.基础概念和复杂度分析 　　看完第一讲数据结构、算法的概念描述数据结构的方法是抽象数据类型，其包含了数据集和操作集2部分描述算法是否优秀，用时间复杂度（T(n)）和空间复杂度(S(n))2个标准去评判复杂度的渐进表示法（但是对于该表示法，并没有完全理解，需要进一步加强理解）

　　5. 分析复杂度的一些技巧：包括了2个复杂度相加和相乘、k阶多项式、for循环、if..else等情况6. 描述算法时间复杂度的时候，很多时候不需要特别精确，只是需要一个大概的判断，判断他是一个怎么样的表达式：logn、n、nlogn、
、
、n！即可7. 最大子列和的例子说明解决一个问题，可以有不同的算法，而不同的算法解决问题的效率差距可以非常大。比如解决该问题用了4种算法，时间复杂度分别是：T(N) = O(N³)、T(N)=O(N²)、T(N)=O(NlogN)、T(N)=O(N)8. 分而治之是一种算法思想9. 自己的高数和线性代数需要加强 　　2.C语言和线性表及其实现1.对C语言进行查漏补缺 　　由于课程里面例子使用到编程语言的是C语言，虽然笔者在刚入门编程的时候大概地看了一遍《C primer plus》这本书，但是时间久远也忘得差不多了。因此，今天根据课程里面的C语言设计到的代码进行了一番查漏补缺：1.typedef关键字 — 为变量类型（包括【基本变量类型】和【自定变量类型如结构体和共同体】）自定义另外名字2.struct结构体 — 类似于数组，但是里面的素的数据类型可以不是一致的3.结构体何如取数据 — struct.a，结构体指针如何取数据 — p->next4.ElemType是什么 — 一个举例的时候用的关键字，泛指某种数据类型（基本数据类型或者自定义数据类型）5.指针和函数指针 — C语言最为关键的特征6.malloc函数 — 分配空间的函数，参数是字节数，语法：str = (char *) malloc(15) 或者 type *var_name = (type*)malloc(sizeof(type)*num); 7.union共同体 — 多个可能的数据共用一个内存空间的方式 ，当前只能有一个数据使用该内存，使用下一个数据，上一个数据会被覆盖重写2.线性表及其实现 　　第二讲的课程从【多项式的表示】这一问题开始，依次使用了数组、二维数组（优点：可以只表示非0项）、链表结构进行了表示，提炼出2个观点：1.同一个问题可以有不同的表示（存储）方法2.有一个共性问题：有序线性序列的组织和管理紧接着提出了【线性表】这一数据结构，并给出了相关定义（是什么，长度、空表、表头、表尾是什么）和用抽象数据类型进行了描述然后讲了顺序表的2种C语言的具体实现（实现抽象数据类型中的对象集和操作集（查找，插入，删除））1.顺序存储具体实现（数组）2.链式存储的具体实现（指针） 特点：不要求逻辑上相邻的2个素物理上也相邻；通过“链”建立起数据素之间的逻辑关系 优点：插入、删除不需要移动数据素，只需要修改“链” 　　最后提出了【广义表】（线性表里面的素数据再套线性表）、【多重链表】（链表中的节点可能同时隶属于多个链，树、图这样的数据结构都可以采用多重链表的方式进行储存）、【十字链表】的概念 　　并且用【十字链表】实现了【矩阵】的表示 　　3.堆栈和队列1.【堆栈】的概念，应用的地方 一种受约束的【线性表】 函数调用、递归，表达式求值2.由想用计算机解决【后缀表达式】计算的问题，引出需要一种【先进后出】的存储方案，进而提出了【堆栈】这样一种数据结构3.【堆栈】的抽象数据类型描述4.【堆栈】的顺序存储实现 — 利用了C语言的【数组】5.【堆栈】的链式存储实现 — 利用了C语言的【链表】6.利用新设计出来的【堆栈】数据结构，解决【前缀表达式】转换为【后缀表达式】的问题 　　7.【队列】的概念和特点 — 具有操作约束（一端删除，一端新增，先进先出）的线性表8.【队列】的抽象数据类型描述9.【队列】的顺序存储实现10.【队列】的链式存储实现11.【多项式加法运算】算法 — 运用了线性表（但是不是【堆栈】也不是【队列】） 　　4.二叉树和二叉树的遍历 　　1.什么是树，有哪些特性2.树的基本术语：【结点的度】【树的度】【叶结点】【父结点】【子结点】【兄弟结点】【路径和路径长度】【祖先结点】【子孙结点】【结点的层次】【树的深度】3.使用【儿子-兄弟表示法】可以用结构体【1个数据域+2个指针域】就可以达到将任意树进行表达的目的，并且可以转化为【二叉树】4.【查找】分为【静态查找】和【动态查找】，区别是查找的过程是否有可能有记录的插入和删除静态查找有2种方法：【顺序查找】和【二分查找】【顺序查找】就是按顺序去找，时间复杂度是O(n)【二分查找】就是递归：找到中间判断在左边还是右边，时间复杂度是O(log(n))5.什么是【二叉树】（注意二叉树有左右之分）6.需要记住的特殊的二叉树：【斜二叉树】、【完美二叉树（满二叉树）】、【完全二叉树】7.【二叉树】的几个重要性质：一个二叉树第i层的最大结点数为：
深度为k的二叉树有最大结点数为：
对于任何非空二叉树T，若
表示叶结点的个数、
是度为2的非叶结点的个人，则有
8.和之前【线性表】一样，二叉树也有【顺序存储】和【链式存储】2种顺序存储：利用数组进行存储，一般用于【完全二叉树】链式存储：就是利用【结构体】，包含一个数据域，2个指针域9.二叉树的遍历：先序：根左右中序：左根右后序：左右根一般是用递归实现，但是也有非递归实现（使用堆栈）层序遍历：使用队列10.二叉树的几个应用：一、输出二叉树中的叶子结点思路：在二叉树的递归遍历算法中增加一个是否是叶子节点（左右指针都为空）的判断，进入判断则输出二、求二叉树的高度思路：递归，逐层函数return出来，算出最后的高度三、二运算表达式树及其遍历思路：运算表达式表示成如下的二叉树，依次对其进行前序，中序，后序遍历，将结果输出将会得到【前缀表达式】、【中缀表达式】、【后缀表达式】四、由两种遍历序列确定二叉树思路：前序、中序、后序，只要包含了中序加另外一种，就可以唯一确定二叉树 　　5.二叉搜索树和平衡二叉树 　　1.二叉搜索树二叉搜索树也称二叉排序树。特点：左子树小于根节点，右子树大于根节点。操作集：1.查找. 2.查找最小值. 3.查找最大值 4.插入 5.删除1.查找递归方式 -利用一种叫尾递归的方式去实现，return的时候调用自身函数，最后反复return到有结果的那一层。尾递归效率较低，从编译的角度看，尾递归都可以用循环去实现。迭代方式 -while(BST) 大于小于都更新BTS继续循环，直到找到后return出来2.查找最大最小值思路：最大素一定是在树的最右分枝的端结点上 最小素一定是在树的最左分枝的端结点上然后利用上面查找思路的基础上去操作3.插入和查找思路类似，一直比较后找到位置插入4.删除分为3种情况：1.为叶子节点 2.只有一个子节点 3.有2个子节点为叶子节点：直接删除，再修改其父节点指针为null只有一个子节点：删除节点，然后将其父节点指针指向删除节点的子节点有2个子节点：删除节点，用另一节点替代被删除的节点：右子树最小节点或者左子树最大节点 　　2.平衡二叉树不同树的形状会造成不同的查找效率，其中树左右两边越【平衡】（左右子树的层级相差不大），查找效率越高平衡因子和平衡二叉树：平衡因子：BF(T) = hL – hR平衡二叉树：空树或者任一节点的左右子树高度差的绝对值不超过1（ |BF(T)| <= 1 ）平衡二叉树的一个重要性质：给定节点数为n的AVL树的最大高度为【lgn】平衡二叉树的调整：当一个AVL树新加入一个结点之后，通过一定方法，可以将其调整为AVL树方法是找到发现者和麻烦结点然后按照一定的方法进行操作方法：1.右单旋 2.左单旋 3.左右单旋 4.右左单旋 　　6.堆，哈夫曼树和哈夫曼编码，集合与运算 　　堆：堆：优先序列（最大值or最小值）的完全二叉树堆的优点：相比于数组，有序数组，链表，有序链表表示，用【完全二叉树】表示其插入和查找的复杂度都不高分为最大堆和最小堆：最大堆：完全二叉树，每个结点的素值大于其子节点的素值最小堆：完全二叉树，每个结点的素值小于其子节点的素值操作集：1. 创建一个最大堆2. 判断最大堆H是否已经满3. 将素item插入最大堆H4. 判断最大堆H是否为空5. 返回H中的最大素（高优先级） 　　1-创建最大堆定义一个结构体，里面包含了数组，堆的当前素个数，堆的最大容量。可以设置结构体中数组中第一个素是“哨兵”，以便以后更快操作。2-插入思路是向下过滤，将新增素放到最后一个位置，从最后一个开始找到他的父节点并比较，大的话，把父节点的值拉下来子节点的位置。如此类推，直到item不能继续把父节点拉下来为止。3-删除思路是向上过滤，拿出最大堆的最后一个素item，将顶层素删除，然后找到他的子素，和最后一个素比较，如果子素比最后一个素大，则将他往上顶。如此类推，直到item大于子素，不能继续把子素往上顶，则插入item。4.最大堆的建立1.利用前面的插入操作，将素一个个插入到堆中。时间复杂度为 O(N log(N))2.(1).先按顺序输入，构成一个完全二叉树(2).调整各个节点的位置，以满足最大堆的有序特性调整方式：从n/2的位置开始，使用堆删除的思路去搞成一个最大堆，然后递减，慢慢把全部搞成一个最大堆 　　哈夫曼树与哈夫曼编码：哈夫曼树（最优二叉树）：【带权】的【叶子节点】【之和】最小的树哈夫曼树的构建：给一个【权值的数组】，将其构建成【哈夫曼树】这里利用了【最小堆】，因为【最小堆】可以通过【delete】操作每次拿到最小值，2次操作可以拿到最小的2个值，然后用来构建【哈夫曼树】的结点，然后再次插入【最小堆】，然后再继续进行上面的操作（做Size-1次合并，直到堆的素数量变成1），最后将最后一个堆的素取出，即为构造好的【哈夫曼树】 　　哈夫曼树的特点：1.没有度为1的结点2.n个叶子节点的哈夫曼树共有2n-1个结点（ 因为二叉树有这样的性质：n0 = n2 + 1 ，结合上面第一条可以得出本条结论）3.哈夫曼树的任意左右结点交换后仍是哈夫曼树3.对同一权值{ w1,w2,w3…wn }，存在不同构的哈夫曼树 　　哈夫曼编码的问题： 给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？每一个字符都有其频率，这个频率相当于【权值】对字符构造【哈夫曼树】则可以得到其最佳编码方案（占用空间最小）集合和运算：首先，集合可以用树来表示其次，在上面的基础上，集合可以用数组表示最后，就可以用数组来进行集合的编程运算查找运算：就是查找数组的素，找到后返回他的下标，拿到对应的Parent值 　　并运算：1.分别找到X1和X2 两个素所在集合树的根节点2.如果他们不同根，则将其中一个素的根节点设置成另外一个素根节点的数组下标7.图和图的遍历图：是一种多对多的关系（线性表和树都是特殊的图，分别表示一对一和一对多的关系）包含了一组顶点和一组边抽象数据类型定义：类型名称：图数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成操作集（主要）：1.DFS（深度优先搜索）2.BFS（广度优先搜索）相关概念：边有权重的时候，被称为网络边有方向的时候，被称为有向图用邻接矩阵表示图1.二维数组的邻接矩阵2.一维数组的邻接矩阵（用矩阵的一半【n*(n+1)/2规模的数组】去表示）邻接矩阵表示的优点：方便检查任意2个顶点之间是否存在边方便检查任意1个顶点的所有邻接点邻接矩阵表示的缺点：浪费空间：存稀疏矩阵有大量的无效素浪费空间浪费时间：统计稀疏矩阵一共有多少条边 　　用邻接表表示图：G[N]为指针数组，对应矩阵每行一个链表，表头是每一个顶点素，链接的是和他有边的顶点（链接的顺序没有要求）特点：1. 方便找到某一个顶点所有的邻接点2. 需要N个头指针 + 2E个结点（每个结点至少2个域）3. 对于无向图，方便计算任一顶点的“度”4. 不方便检查任一对顶点间是否有边 　　图的遍历DFS：一条道探索，探索到最深（不能继续探索），然后回去上一层探索之前没有探索过的，依然是到最深，一直做这个过程 　　BFS：类似于树的层序遍历，利用了【队列】 　　关于图连通 　　首先要知道一些概念：【连通】：顶点间存在路径，则这2个顶点联通【路径】：V到W的路径是一系列顶点{ V,v1,v2,v3…vn,W }的集合，其中任一一对相邻的顶点间都有图中的边。路径的长度是路径中边数（如果带权重，则是所有边的权重之和）。如果V到W之间的所有顶点都不同，则称简单路径。【回路】：起点等于终点的路径【连通图】：图中任意2顶点均连通【连通分量】：无向图的最大连通子图 1）极大顶点数-再加一个顶点就不连通了 2）包含子图的所有顶点相连的所有边【强连通】：连通的基础上，路径是双向的【强连通图】：有向图中任意2顶点均强连通【强连通分量】：有向图的【极大连通子图】 　　图不连通时候的遍历 　　2道图搜索例题 1.007问题 现实：007需要从中间的小岛，依次踩着鳄鱼的头，最后成功上岸抽象：岛和鳄鱼以及岸上抽象成【图】的顶点，问题转化为：找到一条【中心小岛顶点】到【岸上】的路径算法： 　　2.6度空间理论现象：你和任何一个陌生人之间所间隔的人不会超过六个思路：返回的是6层以内的结点数量，需要记录结点数目（count）和结点层数（level）每visit一个结点，count++记录每一层最后进入邻接点（第一层只有一个）遍历的顶点为last 同时，进入遍历的每次遍历的顶点记录为tail 跳出循环的时候，tail为最后一个邻接点，此时判断当前顶点是否和之前记录的某一层的最后顶点相同，如果相同，则说明这一层已经遍历完了，level++，同时改变last为当前顶点，记录该层最后一个顶点 　　8.最小路径问题，最小生成树问题，拓扑排序最短路径网络中，2个不同顶点之间所有路径中权值之和最小的路径。第一个顶点叫：源点。最后一个顶点叫：终点。单源最短路径从某固定源点出发，求其到所有其他顶点的最短路径多源最短路径求任意2顶点的最短路径无权图的单源最短路算法 　　有权图的单源最短路算法 　　多源最短路算法 　　9.排序学习了9种排序，分别是冒泡，选择，插入排序（这3种一般被称作简单排序）希尔排序，归并排序，堆排序，快速排序，表排序，基数排序冒泡排序原理：第一轮排序 — 第一个开始，和下一个进行比较，如果第一个比第二个大，则交换位置第二个和第三个比较，如果第二个比第三个大，则交换位置如此类推，知道比较完最后一个素，这时，完成一轮排序，最后一个素是最大的第二轮排序 –第一个开始，和下一个进行比较，如果第一个比第二个大，则交换位置 第二个和第三个比较，如果第二个比第三个大，则交换位置如此类推，直到比较完倒数第二个素，这时，完成二轮排序，最后2个素是最大的第n轮排序..完成最后的排序 　　需要注意：每轮排序前面已经排好的素不需要再比较 　　选择排序原理：每次找到最小，然后交换位置到对应的位置就可以当然可以设置minposition，然后逐一比较去找插入排序原理：想象成往牌堆里面插牌 抽出牌往排好序的牌堆里面插的时候去比较，如果新抽出来的牌比上一张大则换位 重复上面的过程，直到新抽出来的牌比牌堆里面的牌小，则表示新抽出来的牌已经在它应该有的位置上面希尔排序原理：在插入排序的基础上，每次修改插入排序插入的牌的次序，和调换顺序的时候的间隔归并排序原理：分为递归和非递归2种1.基础函数是【有序子序列】的归并函数2.递归的思想是分而治之，类似于微积分，微分了再积分。递归到颗粒度为1，进行归并操作，然后往上出栈3.非递归则使用的是2次遍历操作，内层的遍历从基数1开始两两【有序子序列】往下合并，外层则再内层遍历完一次之后将length*2，继续进行内层遍历，直到length的值大于N的值，说明已经归并完毕堆排序原理：堆排序的最大特点是同时利用了选择排序和堆，在选择排序的思路上利用了堆去构建 　　这里的堆排序又分了2种： 1.需要额外空间。原理是先建成【最小堆】，然后delete出顶层的最小素，放入临时数组。一直这样操作N遍 2.利用自身数组空间。原理是先建成【最大堆】，然后把【最大堆】的顶层最大素和数组最后一个交换数值，然后去掉从倒数第二个素再循环进行上述操作快速排序原理：分而治之的思想选出一个主。左右分别比较后交换，直到左边和右边位置相交，此时将主放到正确的位置上。递归进行上述操作，直到进入一个阈值，不再递归，直接用插入排序将阈值内的列表排好。 　　表排序原理：排序的素不是一个简单的数字，是一个结构体（书，电影）使用其他排序方法需要移动该素，效率比较低这时候可以使用【表排序】（间接排序）用一个数组去代表真正需要排的序列，然后根据待排素的特征去排该数组，最后形成真正的顺序 　　基数排序原理：创建一个个桶，遍历素，将素放入这一个个桶中基于基数排序，可以将基数排序的思路延伸到其他类似的场景 　　排序算法的比较：简单排序：时间复杂度较大，但是程序比较简单好写 　　希尔排序：平均时间复杂度取决于增量序列的选择，最坏情况下d=2 　　堆排序、归并排序：理论上是效率最好的，归并排序需要额外的空间复杂度N（意味着和其他排序算法相比，他最多只能处理他们一半的素） 　　快速排序：理论上效率也不错，因为他利用了递归去解决，所以需要额外的空间复杂度O(N) 　　基数排序：某种情况下比O(NlogN)还要快（取决于N、B、P的值） 　　关于稳定：相邻素交换的都是稳定的，跳着交换的是不稳定的 　　10.散列查找待完善