1、2022-7-23计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-7-23计算机应用技术研究所计算机应用技术研究所2第第9 9章章 树的基本理论与算法树的基本理论与算法（下）（下）2022-7-232022-7-23&本章学习内容本章学习内容 无向树的基本知识无向树的基本知识1 1 根树的基本知识根树的基本知识2 2 树模型的应用树模型的应用4 4 特殊根树与算法特殊根树与算法3 32022-7-23计算机应用技术研究所计算机应用技术研究所4特殊根树与算法
2、特殊根树与算法2022-7-23计算机应用技术研究所计算机应用技术研究所5&特殊根树与算法特殊根树与算法J 平衡树模型平衡树模型4 红黑树模型红黑树模型4 B B树模型树模型2022-7-232022-7-23&平衡二叉树平衡二叉树【定义】平衡二叉树是一种特殊的二叉树，要求树中任何结点的两棵子树高度差不能超过1，如果插入或者删除一个结点使得高度之差大于 1，就要进行结点之间的旋转操作，将二叉树重新维持在一个平衡状态。2022-7-232022-7-23&平衡因子平衡因子【定义】树模型中某结点左子树的高度减去该结点右子树的高度，所形成的差值称为该结点的平衡因子，即Balance Fector(B
3、F)=左子树的高度-右子树的高度。平衡二叉树的平衡因子为-1，0 或 1。设计平衡二叉树操作算法的关键在于如何使得平衡二叉树保持平衡2022-7-232022-7-23&不平衡情况不平衡情况以下四种情况下的插入操作可能会导致原有平衡二叉树发生不平衡:（1）LL：若某一节点的平衡因子为 1，当在其左子树的左子树上插入一个新结点时会导致该结点的平衡因子由 1 变为 2。（2）RR：若某一节点的平衡因子为-1，当在其右子树的右子树上插入一个新结点时会导致该结点的平衡因子由-1 变为-2。（3）LR：若某一节点的平衡因子为 1，当在其左子树的右子树上插入一个新结点时会导致该结点的平衡因子由 1 变为
4、2。（4）RL：若某一节点的平衡因子为-1，当在其右子树的左子树上插入一个新结点时会导致该结点的平衡因子由-1 变为-2。平衡二叉树有四种基本的旋转方式，分别为：左旋转，右旋转，先左后右旋转，先右后左旋转。针对上述四种情况可能导致的不平衡，可通过旋转的方式使得平衡二叉树恢复平衡。2022-7-232022-7-23&LL LL型调整型调整2022-7-232022-7-23&RR RR型调整型调整2022-7-232022-7-23&LR LR型调整型调整2022-7-232022-7-23&LR LR型调整型调整2022-7-232022-7-23&RL RL型调整型调整2022-7-232
5、022-7-23&RL RL型调整型调整2022-7-232022-7-23在上述四种旋转基础上，就可对平衡二叉树进行插入和删除操作，具体如下：（1）插入操作：插入完成后需要从插入的结点开始维护一个到根结点的路径，每经过一个结点都要维持树的平衡，需要根据高度差的特点采取不同的旋转策略进行调整，使整棵树恢复成为平衡树。（2）删除操作：首先定位要删除的结点，删除完成后，要从删除结点的父亲开始向上维护树的平衡一直到根结点，然后采取不同的旋转策略调整，使整棵树恢复成为平衡树。&插入删除操作插入删除操作2022-7-23计算机应用技术研究所计算机应用技术研究所16&特殊根树与算法特殊根树与算法4 平衡树
6、模型平衡树模型J 红黑树模型红黑树模型4 B B树模型树模型2022-7-232022-7-23&红黑树红黑树【定义】红黑树是一种自平衡二叉查找树。与其他二叉查找树的不同，红黑树在每个结点上增加一个存储位来表示结点的颜色，可以是红色或黑色，通过自动控制红色和黑色这两种颜色的结点分布，以保证树的高度达到近似平衡，从而能够得到比较高的算法效率。一棵红黑树需要满足以下五条性质：（1）每个结点是红色或者是黑色；（2）根结点是黑色；（3）每个叶结点，即空结点（NIL）是黑色的；（4）如果一个结点是红色，那么它的两个子结点都是黑色；（5）对每个结点，从该结点到其所有后代叶结点的所有路径上包含相同数目的黑结
7、点。2022-7-232022-7-23&插入操作插入操作插入操作主要为以下3个基本步骤：步骤1：查找要插入的位置；步骤2：将新结点的颜色域赋值为红色；步骤3：自下而上重新调整该树为红黑树；2022-7-232022-7-23&具体实现具体实现步骤3的具体实现方法：假设要插入的结点为N，其父亲结点为P，P的兄弟结点为U。考虑以下两类情况：（1）如果P是黑色的，那么整棵树已经是红黑树不需要再进行调整。（2）如果P是红色的，那么插入N后，将与第4条性质不符，这时需要进行旋转调整。具体的调整方法又可以分为以下3种情况：2022-7-232022-7-23&具体实现具体实现1）如图所示，N的叔叔U是红
8、色（图中使用阴影表示红色），将结点P和结点U的定义为黑色并定义结点G为红色。此时，插入结点N的父亲结点P为黑色。因为通过父结点P或结点U的任何路径都必定通过结点G，而在这些路径上黑色结点的数目没有改变。但是，结点G的父结点也可能是红色的，因此需要以结点G向上递归调整结点颜色。2022-7-232022-7-23&具体实现具体实现2）如图所示，N的叔叔U是黑色的，且N是右孩子，此时对结点P进行一次左旋转调换，然后按情形3）的方法处理。2022-7-232022-7-23&具体实现具体实现3)如图所示，N的叔叔U是黑色的，且N是左孩子，此时需对结点G做一次右旋转调换，使得在变换后的树中结点P是新结
9、点N和结点G的父结点，然后调换之前的结点P和结点G的颜色，使之满足第4和第5条性质。2022-7-232022-7-23&删除操作删除操作红黑树删除操作分为以下三个基本步骤：(1)查找要删除结点的位置；(2)用其后继替换该结点；(3)若替换结点为黑色，则需重新调整树模型使其重新成为红黑树。2022-7-232022-7-23&具体实现具体实现步骤3的具体实现分四种情况分别处理：设被删除的结点为N，其父结点为P，其兄弟结点为S。由于结点N是黑色的，则结点P和S都有可能是黑色或红色。2022-7-232022-7-23&具体实现具体实现（1）结点S是红色的。此时结点P肯定是黑色。对结点N的父结点P
10、做左旋转，然后把红色兄弟结点转换成结点N的祖父。接着转换结点N的父亲和祖父的颜色。接下去按第二、第三或第四种情况来处理，如图所示。2022-7-232022-7-23&具体实现具体实现（2）结点S及其的孩子全是黑色的。这种情况下，结点P可能是黑色也可能是红色的。此时，首先把结点S赋值为红色。然后要调整以P作为N递归调整树，如图所示。2022-7-232022-7-23&具体实现具体实现（3）S是黑色的，S的左孩子是红色，右孩子是黑色。这种情况下，对结点S做右旋转，这样S的左孩子就成为S的父亲和N的新兄弟。这样就将问题转化到第四种情况。此时N和它的父结点都不受这个变换的影响，如图所示。2022-
11、7-232022-7-23&具体实现具体实现（4）S是黑色的，S的右孩子是红色。这种情况下，对N的父结点做左旋转，这样S成为N的父结点和S右儿子父结点。接着交换N的父结点和S的颜色，并使S的右儿子为黑色。此时，N增加了一个黑色祖先:要么N的父结点变成黑色，要么它是黑色而S增加了一个黑色祖父。所以，通过N的路径都增加了一个黑色结点，如图所示。2022-7-23计算机应用技术研究所计算机应用技术研究所29&特殊根树与算法特殊根树与算法4 平衡树模型平衡树模型4 红黑树模型红黑树模型J B B树模型树模型2022-7-232022-7-23&B B树树【定义】B树中所有结点的孩子结点数目的最大值称为
12、B树的阶，通常用m表示，出于查找效率考虑，要求m3。一棵m阶B树一般具有以下性质：（1）每个结点最多有m个分支，最少分支数要看是否为根结点，若为根结点，则根结点的分支数至少为2，否则非根结点至少有m/2 个分支。（2）结点的分支数等于关键字数加1，即n(knm)个分支的结点含有n1个关键字，它们按递增顺序排列。其中，k=2(根结点)或 m/2 (非根结点)。2022-7-232022-7-23&B B树树2022-7-232022-7-23&例例例如，图表示为一棵5阶B树（即树中任一结点至多含有 4个关键字，5棵子树），下面将以该B树为例详细介绍B树的查找、插入、删除操作。2022-7-232
13、022-7-23&查找操作查找操作根据结点的孩子数做分支界定。比较要查找的值与当前值的大小，若比当前值小则在其左子树，否则在其右子树，递归查找，直到找到相等的结点为止，并返回该结点的位置。如果直到叶子结点仍然没有找到则返回Null。2022-7-232022-7-23&插入操作插入操作插入操作后所构成的新树必须满足B树性质。对于高度为h的m阶B树，新结点一般插在第B层。分两种情况讨论具体的插入算法：（1）若该结点中关键字个数小于m-1，则直接插入即可。（2）若该结点中关键字个数等于m-1，以中间关键字为界将结点一分为二，产生一个新结点，并把中间关键字插入到父结点中；重复上述步骤，直到完成插入过
14、程。最坏情况是一直分裂到根结点，建立一个新的根结点，此时整个B树增加一层。2022-7-232022-7-23&举例说明举例说明【例】插入以下字符到一棵空的5阶B树中（非根结点关键字数小于2个就合并，大于4个就分裂）：A C G N H E K Q M F W L T Z D P R X Y S。2022-7-232022-7-23&举例说明举例说明2022-7-232022-7-23&举例说明举例说明2022-7-232022-7-23&删除操作删除操作第一种情况，若删除前该结点中关键字个数n m/2，那么直接删除该结点。2022-7-232022-7-23&删除操作删除操作2022-7-2
15、32022-7-23&删除操作删除操作2022-7-232022-7-23&删除操作删除操作2022-7-232022-7-23&删除操作删除操作2022-7-232022-7-23&删除操作删除操作2022-7-232022-7-23&本章学习内容本章学习内容 无向树的基本知识无向树的基本知识1 1 根树的基本知识根树的基本知识2 2 特殊根树与算法特殊根树与算法3 3 树模型的应用树模型的应用4 42022-7-23计算机应用技术研究所计算机应用技术研究所45树模型的应用树模型的应用2022-7-23计算机应用技术研究所计算机应用技术研究所46&树模型的应用树模型的应用J 找假币问题找假币
16、问题4 轮流摸牌问题轮流摸牌问题4 关键道路问题关键道路问题2022-7-232022-7-23&决策树决策树2022-7-232022-7-23&决策树决策树 决策树是图论中最常见的模型之决策树是图论中最常见的模型之一，它把做出判决的逻辑关系用树的一，它把做出判决的逻辑关系用树的形式表现出来，形式表现出来，最后的结果都集中在最后的结果都集中在叶子上，叶子上，条理清晰，一目了然。条理清晰，一目了然。2022-7-232022-7-23&例例【例】女孩子被父母安排相亲，为了确定见与不见，他可能会考虑诸如：年龄、长相、收入等问题。图所示的决策树就是她可能的一种决策过程。2022-7-232022-
17、7-23&找假币问题找假币问题1 1【例】现有5枚外观相同的硬币，其中有1枚是假的，假币与真币在重量上有差异，但不知孰重孰轻。问如何使用一架无砝码天平找出假币并判别其与真币的重量关系？【分析】用天平来称A和B两枚硬币，只有AB三种可能的情形，因此可构造3元决策树来解决。如图所示。2022-7-232022-7-23&找假币问题找假币问题1 12022-7-232022-7-23&找假币问题找假币问题2 2 【例例】已知有已知有1212个金币，其中有个金币，其中有一个是假的，且不知道假币和金币的一个是假的，且不知道假币和金币的重量关系，现在要求用一个天平，只重量关系，现在要求用一个天平，只称称3
18、 3次，把假币找出来。次，把假币找出来。2022-7-232022-7-23&找假币问题找假币问题2 2【解解】把球分成三份：把球分成三份：2022-7-23计算机应用技术研究所计算机应用技术研究所54&树模型的应用树模型的应用4 找假币问题找假币问题J 轮流摸牌问题轮流摸牌问题4 关键道路问题关键道路问题2022-7-232022-7-23&博弈树博弈树作为一种经典的博奕类游戏，下面我们介绍轮流摸牌问题2022-7-232022-7-23&轮流摸牌问题轮流摸牌问题【例】图所示为初始的三堆扑克牌数量。第一堆和第二堆的扑克牌数量都为3张，第三堆扑克牌的数量为1张，组成了初始状态(3，3，1)。2
19、022-7-232022-7-23&轮流摸牌问题轮流摸牌问题其在给定初始状态（3，3，1）扩展下的所有对弈策略博弈树如图所示2022-7-232022-7-23&轮流摸牌问题轮流摸牌问题一般结论：若某个初始局面为先手必胜，那么每走一步都必须使后首落在必败点。因此对于每一个局面，要么为胜局面，要么为负局面。用非0表示表示胜局面，0表示负局面。对于某一个局面，若为非0局面，它的任务就是要寻找某一种取法，使局面变为0局面。那么其对手无论怎么取，都会使局面又变为0局面。2022-7-232022-7-23&轮流摸牌问题轮流摸牌问题轮流摸扑克牌游戏为典型的尼姆博弈问题。尼姆博弈的关键在于游戏开始时游戏处
20、于何种状态（平衡或非平衡）和先手是否能够按照取子游戏的获胜策略来进行游戏。2022-7-23计算机应用技术研究所计算机应用技术研究所60&树模型的应用树模型的应用4 找假币问题找假币问题4 轮流摸牌问题轮流摸牌问题J 关键道路问题关键道路问题2022-7-232022-7-23&关键道路关键道路一项工程往往由许多作业构成，其中某些作业可以同时进行，而某些作业却必须按照一定先后顺序执行。例如，在建筑工程中，室内装修却必须在砌墙立屋之后才能动工等。这样就存在问题：为了使工期最短、成本最低，我们应该采取什么方法安排各个作业实施？先引入一些概念来对关键道路相关问题进行建模2022-7-232022-7
21、-23&PERTPERT图图2022-7-232022-7-23&PERTPERT图图2022-7-232022-7-23&关键路径关键路径采用生成树方法计算源到其它结点的最长道路即关键道路，计算思路如下：（1）构造一棵以源s为根的生成根树T，且求出s到根树的各个结点v的距离L(v)。（2）对任何一条权为W(u,v)的弦 u,v，若L(v)L(u)+W(u,v)，则从T中去掉以v为终点的有向边，而以有向边 u,v 代之，同时使以v为根的子树中的各结点距离都增加W(u,v)，如此反复进行，直到考察完所有的弦。2022-7-232022-7-23&例题例题【例】求上图所示的作业网络的关键路径【解】2022-7-232022-7-23计算机应用技术研究所计算机应用技术研究所6666
