July_algorithm 4.3树.pdf

《July_algorithm 4.3树.pdf》由会员分享，可在线阅读，更多相关《July_algorithm 4.3树.pdf（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数组、树七月算法邹博2015年10月25日10月算法在线班2/84Cantor数组 已知数组A0N-1乱序着前N个正整数，现统计后缀数组Ai+1N-1中小于元素Ai的数目，并存放在数组Ci中。如给定数组A=4,6,2,5,3,1，得到数组C=3,4,1,2,1,0。问：给定数组C=3,4,1,2,1,0，如何恢复数组A？我们称A为原数组，C为Cantor数组。10月算法在线班3/84Code 原数组 Cantor数组10月算法在线班4/84问题分析 Cantor数组：3,4,1,2,1,0原数组：4,6,2,5,3,1 给定顺序数组B=1,2,3N-1,N，从0开始数 考察Cantor数组的首

2、位C0：小于A0的个数为C0，则A0为BC0 在序列数组B中删除BC0，仍然满足以上性质。10月算法在线班5/84Code10月算法在线班6/84进一步思考 以上代码空间复杂度为O(N)，时间复杂度为O(N2)，若允许更改数组C，可否降低空间复杂度？Cantor数组：3,4,1,2,1,0原数组：4,6,2,5,3,1 考察Cantor数组中第一个出现0的位置：它表示位于该位置右侧的所有元素都大于该元素，则该元素必然是最小的。每次找到第一个0后，将0左侧的Cantor值都减一，重复以上操作。空间复杂度为O(1)。10月算法在线班7/84Code10月算法在线班8/84总结与思考 Cantor数

3、组：3,4,1,2,1,0原数组：4,6,2,5,3,1 将Cantor数组的每个元素都指定各自的权重：ci的权重为(n-1-i)的阶乘，则Cantor数组与一个整数一一对应，该数称为原数组的Cantor展开数，从Cantor展开数求Cantor数组的过程称为Cantor展开。Cantor数组中元素的和，表示原数组中逆序对的个数，问：给定数组A，如果计算A的逆序对个数？思考时间复杂度为O(NlogN)的算法。10月算法在线班9/84子集和数问题 N-Sum 已知数组A0N-1，给定某数值sum，找出数组中的若干个数，使得这些数的和为sum。布尔向量x0N-1 xi=0表示不取Ai，xi=1表示

4、取Ai 假定数组中的元素都大于0：Ai0 这是个NP问题！10月算法在线班10/84分析方法 直接递归法(枚举)分支限界 存在负数的处理办法10月算法在线班11/84直接递归法10月算法在线班12/84考虑对于分支如何限界 前提：数组A0N-1的元素都大于0 考察向量x0N-1，假定已经确定了前i个值，现在要判定第i+1个值xi为0还是1。假定由x0i-1确定的A0i-1的和为has；Ai,i+1,N-1的和为residue(简记为r)；has+aisum并且has+rsum：xi可以为1；has+(r-ai)=sum：xi可以为0；注意，这里是“可以”可以能够：可能。10月算法在线班13/8

5、4分支限界法10月算法在线班14/84数理逻辑的重要应用：分支限界的条件 分支限界的条件是充分条件吗？在新题目中，如何发现分支限界的条件。学会该方法，比此问题本身更重要10月算法在线班15/84考虑负数的情况 枚举法肯定能得到正确的解 如何对负数进行分支限界？可对整个数组A0N-1正负排序，使得负数都在前面，正数都在后面，使用剩余正数的和作为分支限界的约束：如果Ai为负数：如果全部正数都算上还不够，就不能选Ai；如果递归进入了正数范围，按照数组是全正数的情况正常处理；10月算法在线班16/84带负数的分支限界10月算法在线班17/84求字符串的最长回文子串 回文子串的定义：给定字符串str，若

6、s同时满足以下条件：s是str的子串 s是回文串 则，s是str的回文子串。该算法的要求，是求str中最长的那个回文子串。10月算法在线班18/84枚举中心位置 给定字符串str，则：以stri为中心的回文串最长是多少(奇数)？stri+j=stri-j 以stri和stri+1为中心的回文串最长是多少(偶数)？stri-j=stri+1+j 判断时注意i+j,i-j,i+1+j不要越界。时间复杂度为O(N2)。10月算法在线班19/84Code10月算法在线班20/84算法解析 step1预处理 因为回文串有奇数和偶数的不同。判断一个串是否是回文串，往往要分开编写，造成代码的拖沓。一个简单的

7、事实：长度为n的字符串，共有n-1个“邻接”，加上首字符的前面，和末字符的后面，共n+1的“空”(gap)。因此，字符串本身和gap一起，共有2n+1个，必定是奇数；abbc#a#b#b#c#aba#a#b#a#因此，将待计算母串扩展成gap串，计算回文子串的过程中，只考虑奇数匹配即可。10月算法在线班21/84数组int Psize 字符串12212321 S=$#1#2#2#1#2#3#2#1#;trick：为处理统一，最前面加一位未出现的字符，如$用一个数组Pi来记录以字符Si为中心的最长回文子串向左/右扩张的长度(包括Si)，比如S和P的对应关系：S#1#2#2#1#2#3#2#1#P

8、 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1Pi-1正好是原字符串中回文串的总长度 若Pi为偶数，考察x=Pi/2、2*x-1 思考：若Pi为奇数呢？答：不考虑！(为何？)10月算法在线班22/84分析算法核心我们的任务：假定已经得到了前i个值，考察i+1如何计算即：在P0.i-1已知的前提下，计算Pi的值。换句话说，算法的核心，是在P0.i-1已知的前提下，能否给Pi的计算提供一点有用的信息呢？1、通过简单的遍历，得到i个三元组k,Pk,k+Pk，0ki-1trick：以k为中心的字符形成的最大回文子串的最右位置是k+Pk-12、以k+Pk为关键字，挑选出这i个三元组

9、中，k+Pk最大的那个三元组，不妨记做(id,Pid，Pid+id)。进一步，为了简化，记mx=Pid+id，因此，得到三元组为(id,Pid,mx)，这个三元组的含义非常明显：所有i个三元组中，向右到达最远的位置，就是mx；3、在计算Pi的时候，考察i是否落在了区间0,mx)中；若i在mx的右侧，说明0,mx)没有能够控制住i，P0.i-1的已知，无法给Pi的计算带来有价值信息；若i在mx的左侧，说明0,mx)控制(也有可能部分控制)了i，现在以图示来详细考察这种情况。10月算法在线班23/84Manacher递推关系 记i关于id的对称点为j(=2*id-i)，若此时满足条件mx-iPj：

10、记my为mx关于id的对称点(my=2*id-mx)；由于以Sid为中心的最大回文子串为Smy+1idmx-1，即：Smy+1,id与Sid,mx-1对称，而i和j关于id对称，因此Pi=Pj(Pj是已知的)。10月算法在线班24/84Manacher递推关系 记i关于id的对称点为j(=2*id-i)，若此时满足条件mx-iPj：记my为mx关于id的对称点(my=2*id-mx)；由于以Sid为中心的最大回文子串为Smy+1idmx-1，即：Smy+1,id与Sid,mx-1对称，而i和j关于id对称，因此Pi至少等于mx-i(图中绿色框部分)。10月算法在线班25/84Manacher

11、Code10月算法在线班26/84原始算法的个人改进意见 Pj mx i：Pi=mx i Pj 2；第2个元素a2到了原第4个元素a4的位置，即2-4；第3个元素a3到了原第6个元素b2的位置，即3-6；第4个元素a4到了原第8个元素b4的位置，即4-8；前n个元素中，第i个元素的最终位置为(2*i)。后n个元素，可以看出：第5个元素b1到了原第1个元素a1的位置，即5-1；第6个元素b2到了原第3个元素a3的位置，即6-3；第7个元素b3到了原第5个元素b1的位置，即7-5；第8个元素b4到了原第7个元素b3的位置，即8-7；后n个元素，第i个元素的最终位置为：(2*(i-n)-1=2*i-

12、2*n-1=(2*i)%(2*n+1)10月算法在线班36/84两个圈 我们得到两个圈 1 2 4 8 7 5 1 3 6 310月算法在线班37/84K个圈 对于2*n=(3k-1)这种长度的数组，恰好只有k个圈，且每个圈的起始位置分别是1,3,9，.3(k-1)10月算法在线班38/84若：2m可以写成3k-1的形式10月算法在线班39/84任意长度数组的完美洗牌算法10月算法在线班40/84循环移位(AB)=BA10月算法在线班41/84完美洗牌算法流程 输入数组A1.2*n step 1 找到 2*m=3k-1，且3k2*n3(k+1)step 2 把am+1m+n那部分循环右移m位

13、step 3 对每个i=0,1,2.k-1，3i是每个圈的起始位置，做cycle_leader算法；注：因为子数组长度为m，所以对2*m+1取模 step 4 对数组的剩余部分A2*m+1.2*n继续使用本算法。10月算法在线班42/84完美洗牌代码10月算法在线班43/84依据 2是3的原根，2是9的原根 20,21=1,2 20,21,22,23,24,25,26,27,28mod 9=1,2,4,8,7,5 而(9)=610月算法在线班44/84附：算法原文10月算法在线班45/84进一步的思考要求输出是a1,b1,a2,b2an,bn，而完美洗牌算法输出是b1,a1,b2,a2,bn,

14、an,怎么办？先把a部分和b部分交换，或者最后再交换相邻的两个位置不够美观。原数组第一个和最后一个不变，中间的2*(n-1)项用原始的完美洗牌算法。逆完美洗牌问题：给定b1,a1,b2,a2,bn,an，要求输出a1,a2,a3,an,b1,b2,b3,bn。既然完美洗牌问题可以通过若干圈来解决，那么，逆完美洗牌问题仍然存在是若干圈，并且2*n=(3k-1)这种长度的数组恰好只有k个圈的结论仍然成立。完美洗多付牌：给定a1,a2,an,b1,b2,bn,c1,c2,cn，要求输出是c1,b1,a1,c2,b2,a2,cn,bn,an2付牌的结论：2是群(Z/3k)*最小生成元，且(3k-1)这

15、种长度的数组，恰好只有k个圈考察是否存在某数字p(如5、7、11、13等)，使得数字3是群(Z/pk)*的最小生成元，再验证p是否存在结论(pk-1)这种长度的数组，恰好只有k个圈。提示：3是7的原根，是49的原根，于是3是7k的原根10月算法在线班46/84树主要内容二叉查找树增删改查其他结构的基础：如平衡二叉树前序中序后序遍历三种遍历本身通过前序中序求后序平衡二叉树四种分类：左左、左右、右左、右右四种旋转：左旋和右旋；单旋转和双旋转增删改查B树及其变种分裂结点、合并结点R树实践中的应用10月算法在线班47/84树和二叉树 一般地说，树的结点间是无序的，即：一个结点有m个孩子，则L1L2Lm

16、可以互换位置，仍然认为是一颗树。二叉树的两个孩子，一般称为左孩子、右孩子，不能互换位置。之所以这样定义，是因为有些算法，需要严格区分左右孩子，如前序-中序-后序遍历、堆排序等问题。从这个意义上说，树和二叉树是两个概念，不能说二叉树是树的子集。注：这种区分非常弱而且乱，因为树还有“有序树”“无序树”的说法。10月算法在线班48/84树转换成二叉树10月算法在线班49/84树转换得到的二叉树右孩子 任意一颗树转换成二叉树，右孩子为空的数目为原树非叶结点+1。对于一颗树(非二叉树)，因为任何一个非叶结点必然有孩子，所以，它必然有最右孩子。从而，这个最右孩子转换到二叉树结点后，右指针必然为空。同时，根

17、结点必然没有兄弟，所以，根结点转换成二叉树结点后，必然右孩子为空。任意颗树转换成二叉树，右孩子为空的数目为原树非叶结点+1。如果是若干个树转二叉树，这若干个树最右边的那个树，是没有右孩子的。10月算法在线班50/84树基本操作 插入 删除 查找 前序遍历 中序遍历 后序遍历10月算法在线班51/84二叉查找树 二叉查找树(二叉搜索树)是满足以下条件的二叉树：左子树上的所有结点值均小于根结点值，右子树上的所有结点值均不小于根结点值，左右子树也满足上述两个条件10月算法在线班52/84二叉查找树的查找 给定一颗二叉查找树，查找某结点p的过程如下：将当前结点cur赋值为根结点root；若p的值小于当

18、前结点cur的值，查找cur的左子树；若p的值不小于当前结点cur的值，查找cur的右子树；递归上述过程，直到cur的值等于p的值或者cur为空；当然，若结点是结构体，注意定义“小于”“不小于”“等于”的具体函数。10月算法在线班53/84Code10月算法在线班54/84二叉查找树的插入 插入过程如下：若当前的二叉查找树为空，则插入的元素为根结点，若插入的元素值小于根结点值，则将元素插入到左子树中，若插入的元素值不小于根结点值，则将元素插入到右子树中，递归上述过程，直到找到插入点为叶子结点。10月算法在线班55/84Code(recursion)10月算法在线班56/84Code10月算法在

19、线班57/84二叉树的建立 依次插入：15,5,3,12,16,20,23,13,18,10,6,710月算法在线班58/84二叉查找树的删除 记待删除的结点为p，分三种情况进行处理：p为叶子结点 p为单支结点 p的左子树和右子树均不空10月算法在线班59/84待删除点为叶子结点 p为叶子结点，直接删除该结点，再修改p的父结点的指针10月算法在线班60/84待删除点只有一个孩子 若p为单支结点(即只有左子树或右子树)，则将p的子树与p的父亲结点相连，删除p即可10月算法在线班61/84待删除点有两个孩子 若p的左子树和右子树均不空，则找到p的直接后继d(p的右孩子的最左子孙)，因为d一定没有左

20、子树，所以使用删除单支结点的方法：删除d，并让d的父亲结点dp成为d的右子树的父亲结点；同时，用d的值代替p的值；对偶的，可以找到p的直接前驱x(p的左孩子的最右子孙)，x一定没有右子树，所以可以删除x，并让x的父亲结点成为x的左子树的父亲结点。10月算法在线班62/84待删除点有两个孩子 任务：删除p 过程：两步走 将p的直接后继的值拷贝到p处 删除p的直接后继10月算法在线班63/84Code10月算法在线班64/84Code10月算法在线班65/84Code split10月算法在线班66/84二叉树的遍历 前序遍历：访问根结点前序遍历左子树前序遍历右子树 中序遍历：中序遍历左子树访问根

21、结点中序遍历右子树 后序遍历：后序遍历左子树后序遍历右子树访问根结点10月算法在线班67/84前序遍历 前序遍历：15,5,3,12,10,6,7,13,16,20,18,2310月算法在线班68/84Code10月算法在线班69/84中序遍历 中序遍历：3,5,6,7,10,12,13,15,16,18,20,23二叉查找树的中序遍历，即为数据的升序过程10月算法在线班70/84Code10月算法在线班71/84Code10月算法在线班72/84后序遍历 后序遍历：3,7,6,10,13,12,5,18,23,20,16,1510月算法在线班73/84Code10月算法在线班74/84Cod

22、e10月算法在线班75/84根据前序中序，计算后序 如：已知某二叉树的遍历结果如下，求它的后序遍历序列 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 两个步骤：根据前序中序，构造二叉树 后序遍历二叉树10月算法在线班76/84根据前序中序，计算后序 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 根据前序遍历的特点得知，根结点为G；根结点将中序遍历结果ADEFGHMZ分成ADEF和HMZ两个左子树、右子树。递归确定中序遍历序列ADEF和前序遍历序列DAEF的子树结构；递归确定中序遍历序列HMZ和前序遍历序列MHZ的子树结构；10月算法在线班77/84根据前序中序，构造二叉树

23、前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ10月算法在线班78/84Code10月算法在线班79/84思考 若已知二叉树的中序和后序遍历序列，如何求二叉树、如何求二叉树的前序遍历序列呢？10月算法在线班80/84根据中序后序遍历，求前序遍历 中序遍历：ADEFGHMZ 后序遍历：AEFDHZMG 提示：后序遍历最后一个结点即为根结点，即根结点为G 递归10月算法在线班81/84Code10月算法在线班82/84思考 给定整数数组，判断该数组有无可能是一颗二叉查找树后序遍历的结果。假定数组中没有重复元素。编程如何实现？以下序列中不可能是一棵二叉查找树的后序遍历结果的是_。1,2,3,4,53,5,1,4,21,2,5,4,35,4,3,2,110月算法在线班83/84我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班84/84感谢大家恳请大家批评指正！