算法学习 4.1树.pdf
树七月算法邹博2015年4月16日4月算法在线班2/树主要内容二叉查找树增删改查其他结构的基础：如平衡二叉树前序中序后序遍历三种遍历本身通过前序中序求后序平衡二叉树四种分类：左左、左右、右左、右右四种旋转：左旋和右旋；单旋转和双旋转增删改查B树及其变种分裂节点、合并节点R树实践中的应用4月算法在线班3/二叉查找树 二叉查找树(二叉搜索树)是满足以下条件的二叉树：左子树上的所有节点值均小于根节点值，右子树上的所有节点值均不小于根节点值，左右子树也满足上述两个条件4月算法在线班4/二叉查找树的查找 给定一颗二叉查找树，查找某节点p的过程如下：将当前节点cur赋值为根节点root；若p的值小于当前节点cur的值，查找cur的左子树；若p的值不小于当前节点cur的值，查找cur的右子树；递归上述过程，直到cur的值等于p的值或者cur为空；当然，若节点是结构体，注意定义“小于”“不小于”“等于”的具体函数。4月算法在线班5/查找Code4月算法在线班6/二叉查找树的插入 插入过程如下：若当前的二叉查找树为空，则插入的元素为根节点，若插入的元素值小于根节点值，则将元素插入到左子树中，若插入的元素值不小于根节点值，则将元素插入到右子树中，递归上述过程，直到找到插入点为叶子节点。4月算法在线班7/插入实例4月算法在线班8/二叉树的建立 依次插入：15,5,3,12,16,20,23,13,18,10,6,74月算法在线班9/二叉查找树的删除 记待删除的节点为p，分三种情况进行处理：p为叶子节点 p为单支节点 p的左子树和右子树均不空4月算法在线班10/待删除点为叶子节点 p为叶子节点，直接删除该节点，再修改p的父节点的指针4月算法在线班11/待删除点只有一个孩子 若p为单支节点（即只有左子树或右子树），则将p的子树与p的父亲节点相连，删除p即可4月算法在线班12/待删除点有两个孩子 若p的左子树和右子树均不空，则找到p的直接后继d(p的右孩子的最左子孙)，因为d一定没有左子树，所以使用删除单支节点的方法：删除d，并让d的父亲节点dp成为d的右子树的父亲节点；同时，用d的值代替p的值；对偶的，可以找到p的直接前驱x(p的左孩子的最右子孙)，x一定没有右子树，所以可以删除x，并让x的父亲节点成为x的左子树的父亲节点。4月算法在线班13/待删除点有两个孩子 任务：删除p 过程：两步走 将p的直接后继的值拷贝到p处 删除p的直接后继4月算法在线班14/删除Code 代码过长，分片来看4月算法在线班15/删除Code：part14月算法在线班16/删除Code：part24月算法在线班17/删除Code：part34月算法在线班18/二叉树的遍历 前序遍历：访问根节点前序遍历左子树前序遍历右子树 中序遍历：中序遍历左子树访问根节点中序遍历右子树 后序遍历：后序遍历左子树后序遍历右子树访问根节点4月算法在线班19/前序遍历 前序遍历：15,5,3,12,10,6,7,13,16,20,18,234月算法在线班20/Code4月算法在线班21/中序遍历 中序遍历：3,5,6,7,10,12,13,15,16,18,20,23二叉查找树的中序遍历，即为数据的升序过程4月算法在线班22/Code4月算法在线班23/后序遍历 后序遍历：3,7,6,10,13,12,5,18,23,20,16,154月算法在线班24/Code4月算法在线班25/根据前序中序，计算后序 如：已知某二叉树的遍历结果如下，求它的后序遍历序列 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 两个步骤：根据前序中序，构造二叉树 后序遍历二叉树4月算法在线班26/根据前序中序，计算后序 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 根据前序遍历的特点得知，根结点为G；根节点将中序遍历结果ADEFGHMZ分成ADEF和HMZ两个左子树、右子树。递归确定中序遍历序列ADEF和前序遍历序列DAEF的子树结构；递归确定中序遍历序列HMZ和前序遍历序列MHZ的子树结构；4月算法在线班27/根据前序中序，构造二叉树 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ4月算法在线班28/Code4月算法在线班29/思考 若已知二叉树的中序和后序遍历序列，如何求二叉树、如何求二叉树的前序遍历序列呢？4月算法在线班30/根据中序后序遍历，求前序遍历 中序遍历：ADEFGHMZ 后序遍历：AEFDHZMG 提示：后序遍历最后一个结点即为根结点，即根结点为G 递归4月算法在线班31/Code4月算法在线班32/平衡二叉树 平衡二叉树（Balanced Binary Tree）是二叉查找树的一个变体，也是第一个引入平衡概念的二叉树。1962年，G.M.Adelson-Velsky 和 E.M.Landis发明了这棵树，所以它又叫AVL树。平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。4月算法在线班33/二叉查找树与平衡二叉树4月算法在线班34/分析高度不平衡节点 高度不平衡节点的两颗子树的高度差2。只考虑该不平衡节点本身，分四种情况分别讨论：4月算法在线班35/高度不平衡1：左左 6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。4月算法在线班36/高度不平衡2：左右 6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。4月算法在线班37/高度不平衡3：右左 2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。4月算法在线班38/高度不平衡4：右右 2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。4月算法在线班39/对称与旋转 左左和右右对称；左右和右左对称 左左和右右两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，称之为单旋转。左右和右左两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，称之为双旋转。4月算法在线班40/左左单旋转 节点K2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且K1子树中，更深的一层的是K1的左子树X子树，所以属于左左情况。4月算法在线班41/单旋转 如图，假设K2不平衡：为使树恢复平衡，把K1变成根节点 K2大于K1，所以，把K2置于K1的右子树上 K1右子树Y大于K1，小于K2，所以，把Y置于k2的左子树上4月算法在线班42/AVL单旋转假设K2不平衡：为使树恢复平衡，把K1变成根节点K2大于K1，所以，把K2置于K1的右子树上K1右子树Y大于K1，小于K2，所以，把Y置于k2的左子树上4月算法在线班43/双旋转 对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。以左右为例：节点K3不满足平衡特性，它的左子树K1比右子树D深2层，且K1子树更深的是右子树K2。4月算法在线班44/Code4月算法在线班45/平衡二叉树的插入 插入的方法和二叉查找树基本一样，区别是，插入完成后需要从插入的节点开始维护一个到根节点的路径，每经过一个节点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。4月算法在线班46/Code4月算法在线班47/平衡二叉树的查找 平衡二叉树和使用和二叉查找树完全相同的查找方法，不过根据高度基本平衡存储的特性，平衡二叉树能保持O(logN)的稳定时间复杂度，而二叉查找树则相当不稳定。4月算法在线班48/平衡二叉树的删除 删除的方法也和二叉查找树的一致，区别是，删除完成后，需要从删除节点的父亲开始向上维护树的平衡一直到根节点。4月算法在线班49/Code4月算法在线班50/Code part14月算法在线班51/Code part24月算法在线班52/二叉到多叉的思考 一个节点存一个值，则有2个孩子：W 一个节点存两个值，则有3个孩子：MO 一个节点存三个值，则有4个孩子：MO4月算法在线班53/2-3-4树4月算法在线班54/查找L4月算法在线班55/插入B4月算法在线班56/插入X4月算法在线班57/插入H4月算法在线班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：微博研究者July七月问答邹博_机器学习4月算法在线班67/感谢大家恳请大家批评指正！
