算法学习 4.树.pdf

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

1、树七月算法邹博2015年4月16日4月算法在线班2/二叉查找树 二叉查找树(二叉搜索树)是满足以下条件的二叉树：左子树上的所有节点值均小于根节点值，右子树上的所有节点值均不小于根节点值，左右子树也满足上述两个条件4月算法在线班3/二叉查找树的查找 给定一颗二叉查找树，查找某节点p的过程就是递归过程：若当前节点cur的值小于p的值，查找cur的左子树；若当前节点cur的值不小于p的值，查找cur的右子树；递归上述过程，直到cur=p或者cur为空；4月算法在线班4/查找Code4月算法在线班5/二叉查找树的插入 插入过程如下：若当前的二叉查找树为空，则插入的元素为根节点，若插入的元素值小于根节点

2、值，则将元素插入到左子树中，若插入的元素值不小于根节点值，则将元素插入到右子树中，递归上述过程，直到找到插入点为叶子节点。4月算法在线班6/插入实例4月算法在线班7/二叉树的建立 依次插入：15,5,3,12,16,20,23,13,18,10,6,74月算法在线班8/二叉查找树的删除 记待删除的节点为p，分三种情况进行处理：p为叶子节点 p为单支节点 p的左子树和右子树均不空4月算法在线班9/待删除点为叶子节点 p为叶子节点，直接删除该节点，再修改p的父节点的指针4月算法在线班10/待删除点只有一个孩子 若p为单支节点（即只有左子树或右子树），则将p的子树与p的父亲节点相连，删除p即可4月算

3、法在线班11/待删除点有两个孩子 若p的左子树和右子树均不空，则找到p的直接后继d(p的右孩子的最左子孙)，因为d一定没有左子树，所以使用删除单支节点的方法：删除d，并让d的父亲节点dp成为d的右子树的父亲节点；同时，用d的值代替p的值；对偶的，可以找到p的直接前驱x(p的左孩子的最右子孙)，x一定没有右子树，所以可以删除x，并让x的父亲节点成为x的左子树的父亲节点。4月算法在线班12/待删除点有两个孩子 任务：删除p 过程：两步走 将p的直接后继的值拷贝到p处 删除p的直接后继4月算法在线班13/删除Code 代码过长，分片来看4月算法在线班14/删除Code：part14月算法在线班15/

4、删除Code：part24月算法在线班16/删除Code：part34月算法在线班17/二叉树的遍历 前序遍历：访问根节点前序遍历左子树前序遍历右子树 中序遍历：中序遍历左子树访问根节点中序遍历右子树 后序遍历：后序遍历左子树后序遍历右子树访问根节点4月算法在线班18/前序遍历 前序遍历：15,5,3,12,10,6,7,13,16,20,18,234月算法在线班19/Code4月算法在线班20/中序遍历 中序遍历：3,5,6,7,10,12,13,16,18,20,23二叉查找树的中序遍历，即为数据的升序过程4月算法在线班21/Code4月算法在线班22/后序遍历 后序遍历：3,7,6,10

5、,13,12,5,18,23,20,16,154月算法在线班23/Code4月算法在线班24/根据前序中序，计算后序 如：已知某二叉树的遍历结果如下，求它的后序遍历序列 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 两个步骤：根据前序中序，构造二叉树 后序遍历二叉树4月算法在线班25/根据前序中序，计算后序 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 根据前序遍历的特点得知，根结点为G；根节点将中序遍历结果ADEFGHMZ分成ADEF和HMZ两个左子树、右子树。递归确定中序遍历序列ADEF和前序遍历序列DAEF的子树结构；递归确定中序遍历序列HMZ和前序遍历序列MHZ的子

6、树结构；4月算法在线班26/根据前序中序，构造二叉树 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ4月算法在线班27/Code4月算法在线班28/思考 若已知二叉树的中序和后序遍历序列，如何求二叉树、如何求二叉树的前序遍历序列呢？4月算法在线班29/根据中序后序遍历，求前序遍历 中序遍历：ADEFGHMZ 后序遍历：AEFDHZMG 提示：后序遍历最后一个结点即为根结点，即根结点为G 递归4月算法在线班30/Code4月算法在线班31/平衡二叉树 平衡二叉树（Balanced Binary Tree）是二叉查找树的一个变体，也是第一个引入平衡概念的二叉树。1962年，G.M.Adel

7、son-Velsky 和 E.M.Landis发明了这棵树，所以它又叫AVL树。平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。4月算法在线班32/二叉查找树与平衡二叉树4月算法在线班33/分析高度不平衡节点 高度不平衡节点的两颗子树的高度差2。只考虑该不平衡节点本身，分四种情况分别讨论：4月算法在线班34/高度不平衡1：左左 6节点的左子树3节点高度比右子

8、树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。4月算法在线班35/高度不平衡2：左右 6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。4月算法在线班36/高度不平衡3：右左 2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。4月算法在线班37/高度不平衡4：右右 2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。4月算法在线班38/对称与旋转 左左和右右对称；左右和右左对称 左左和

9、右右两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，称之为单旋转。左右和右左两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，称之为双旋转。4月算法在线班39/左左单旋转 节点K2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且K1子树中，更深的一层的是K1的左子树X子树，所以属于左左情况。4月算法在线班40/单旋转 如图，假设K2不平衡：为使树恢复平衡，把K1变成根节点 K2大于K1，所以，把K2置于K1的右子树上 K1右子树Y大于K1，小于K2，所以，把Y置于k2的左子树上4月算法在线班41/Code4月算法在线班42/双旋转

10、对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。以左右为例：节点K3不满足平衡特性，它的左子树K1比右子树D深2层，且K1子树更深的是右子树K2。4月算法在线班43/Code4月算法在线班44/平衡二叉树的插入 插入的方法和二叉查找树基本一样，区别是，插入完成后需要从插入的节点开始维护一个到根节点的路径，每经过一个节点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。4月算法在线班45/Code4月算法在线班46/平衡二叉树的查找 平衡二叉树和使用和二叉查找树完全相同的查找方法，不过根据高度基本平衡存储的特性，平衡二叉树能保持O(logN)的稳定时间

11、复杂度，而二叉查找树则相当不稳定。4月算法在线班47/平衡二叉树的删除 删除的方法也和二叉查找树的一致，区别是，删除完成后，需要从删除节点的父亲开始向上维护树的平衡一直到根节点。4月算法在线班48/Code4月算法在线班49/Code part14月算法在线班50/Code part24月算法在线班51/二叉到多叉的思考 一个节点存一个值，则有2个孩子：W 一个节点存两个值，则有3个孩子：MO 一个节点存三个值，则有4个孩子：MO4月算法在线班52/2-3-4树4月算法在线班53/查找L4月算法在线班54/插入B4月算法在线班55/插入X4月算法在线班56/插入H4月算法在线班57/分裂节点4

12、月算法在线班58/4月算法在线班59/B树的定义 m阶B树需要满足的条件：每个结点至多有m个孩子；除根结点外，其他结点至多有m/2个孩子；根结点至少有2个孩子；所有叶结点在同一层；有个孩子的非叶结点有-1个关键字；结点内部，关键字递增排列。4月算法在线班60/B树4月算法在线班61/B树4月算法在线班62/B树的变种4月算法在线班63/二维上的B树R树4月算法在线班64/三维空间中的R树4月算法在线班65/参考文献陈海波,王申康,RTree的查询代价模型分析及算法改进,计算机辅助设计与图形学学报J，15,2003(3)程昌秀,矢量数据多尺度空间索引方法的研究,武汉大学学报信息科学版J,34,2009(5)Eric Redmond,etc,王海鹏等 译,七周七数据库M,7th,2013http:/ Hash)http:/ 更多算法面试题在官网 http:/ 直播课程 问答社区 contact us：微博 七月问答 七月算法4月算法在线班67/感谢大家恳请大家批评指正！