数据结构与算法 课件-Unit 08 二叉排序树

Unit08二叉排序树BinarySortTree某超市会员积分清理活动规则是按照积分区间赠送抵扣劵，如100～199分抵扣10元券，200～299分抵扣20元券，300～399分抵扣30元券，400～499分抵扣40元券，……，以此类推。在计算抵扣券时，需要查找每一个会员的积分区间及对应抵扣券面额，面对庞大的会员数量，为了提高查找对应抵扣券面额的效率，请设计适合的数据结构存储积分区间数据。①理解和运用顺序表、链表、数组、二叉树等。②认识、理解和运用平衡二叉树、二叉树排序树算法。③运用大O表示法分析二叉树排序树的时间复杂度。查找表（SearchTable）1．静态查找表（StaticSearchTable）静态查找表是在查找前表结构已经生成，如果表中存在关键字等于给定值的记录，则查找成功并返回其在表中的位置；否则给出相应的信息。静态查找可以采用顺序查找、二分查找和分块查找等技术。分块查找（BlockingSearch）是一种对顺序查找进行改进的方法，称为索引顺序查找技术。分块查找算法设计：按照表内记录的某种属性把表分成n（n>1）个块（子表），并建立一个相应的索引表，索引表的每个元素对应一个块，其中包括该块内最大的关键字值和第一个记录的位置；且后一个块中所有记录的关键字值都应该比前一个块中所有记录的关键字值大，块内的关键字值的大小可以无序。下图所示为分块查找。图中所示，子表（0-4)存放的是不大于34的数据元素，子表（5-9)块存放的是不大于63但都大于34的数据元素，而子表（10-14)存放的是不大于89但都大于63的数据元素。2．动态查找表（DynamicSearchTable）动态查找表是在查找过程中表结构是动态生成的，如果表中存在关键字与查找目标一致，则查找成功并返回其在表中的位置；否则将查找目标的记录插入表中。在静态查找表中，二分查找效率最高，其时间复杂度是O(log2n)，但维护表的有序性的时间复杂度为O(n)，这对庞大的查找表来说，效率还是不理想，所以二分查找只适用于静态查找表，而不适用于动态查找表。如果要对动态查找表进行高效率查找，则可以采用以下几种特殊的二叉树作为表的组织形式：①二叉排序树②平衡二叉树（1）二叉排序树（BinarySortTree）。二叉排序树又称为二叉查找树，它是一颗空的二叉树，或者是具有下列性质的二叉树。如果其左子树不空，则左子树上的所有节点的值均小于根节点的值。如果其右子树不空，则右子树上的所有节点的值均大于根节点的值。其左右子树也都是二叉排序树。如下图所示显然，这是递归定义。由二叉排序树定义可知：①空树被认为是有序树②二叉排序树的中序遍历结果是线性有序的（2）平衡二叉树（BalancedBinaryTree）平衡二叉树又称为AVL树，它是一颗空的二叉排序树，或者是具有下列性质的二叉排序树。根节点的左子树和右子树的深度最多相差1。根节点的左子树和右子树也都是平衡二叉排序树。如果二叉树上任一节点的左右子树深度均相同，如满二叉树，则二叉树是完全平衡的。通常，只要二叉树深度为O(log2n)，就可以看作是平衡树。如果将二叉树上节点的平衡因子BF（BalanceFactor）定义为该节点左子树深度减去其右子树深度，则平衡二叉树上所有节点的平衡因子只可能是0、1和-1。因此，只要二叉树上有一个节点的平衡因子的绝对值大于1，就可以判定该二叉树不是平衡二叉树。最小不平衡子树（MinimalUnbalanceSubtree）是指在平衡二叉树的构造过程中，以距离插入节点最近的、且平衡因子的绝对值大于1的节点为根的子树。图中所示，插入新节点33时，距离它最近的平衡因子绝对值大于1的节点是24，因此以24节点为根的子树就是最小不平衡子树（虚线框内）。平衡二叉树的构建1．平衡二叉树的调整在构造二叉排序树的过程中，每当插入一个节点后，要检查是否因插入而使得平衡被破坏（节点的平衡因子的绝对值大于1）。如果是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各个节点之间的链接关系，进行相应的旋转，使之成为新的平衡树。一般情况下，对最小不平衡子树进行平衡调整有下列4种调整方法。注：图中圆形代表节点，方形代表子树，方形高度表示树的深度。如图所示，X为插入的新节点。插入节点X在最小不平衡子树P的左子树L的左边LL。调整方法：向右沿顺时针方向旋转，子树的根节点由P改为L，P成为L的右孩子，与L原来的右子树LR冲突，修改LR使之成为P节点的左子树。（1）单向右旋平衡处理（又称LL型调整）如图所示，插入新节点X在最小不平衡子树P的右子树R的右边RR。调整方法：向左沿逆时针方向旋转，子树的根节点由P改为R，P成为R的右孩子，与R原来的左子树RL冲突，修改RL为P节点的右子树。（2）单向左旋平衡处理（又称RR型调整）（3）双向先左后右平衡处理（又称LR型调整）。插入新节点X在最小不平衡子树P的左子树L的右边LR（虚线框）。调整方法：第一次旋转，根节点P不动，先调整其左子树L，向左沿逆时针方向旋转子树L，修改S为P的新左子树的根，修改L为S的左孩子，S原来的左子树SL改为L的右子树；第二次旋转，调整最小不平衡子树P，向右沿顺逆时针方向旋转，修改S为子树的根节点，修改P为S的右孩子，修改SR为P的左子树。（4）双向先右后左平衡处理（又称RL型调整）插入新节点X在最小不平衡子树P的右子树R的左边RL（虚线框）。调整方法：第一次旋转，根节点P不动，先调整其右子树R，向右顺时针方向旋转子树R，修改S为P的新右子树的根，修改R为S的右孩子，修改S原来的右子树SR为R的左子树；第二次旋转，调整最小不平衡子树P，向左逆逆时针方向旋转，修改S为子树的根节点，修改P为S的左孩子，修改SL为P的右子树。2．平衡二叉树的插入实现算法设计：在平衡二叉树T上插入一个值为key新节点的步骤如下。（1）如果T是颗空树，则直接插入值为key的节点为根节点，树的深度增加1。（2）如果树中已经有值为key的节点，则不进行插入。（3）如果key小于节点T的数据域，且T的左子树中不存在值为key的节点，则插入到T的左子树上，左子树深度增加1，此时分以下几种情况进行处理：①当T的根节点的BF为-1时，修改BF为0，T的深度不变。②当T的根节点的BF为0时，修改BF为1，T的深度增加1。③当T的根节点的BF为1时，根据以下情况进行判断：如果T的左子树的BF为1，则做LL型调整（单向右旋），修改旋转后的根节点及其右子树的根节点的BF为0，树的深度不变。如果T的左子树的BF为-1，则做LR型调整（双向先左后右旋转），修改旋转后的根节点及其左、右子树的根节点的BF为0，树的深度不变。（4）如果key大于节点T的数据域，且T的右子树中不存在值为key的节点，则插入到T的右子树上，右子树深度增加1，此时根据情况进行处理，与步骤（3）中所列是对称，也即：①当T的根节点的BF为1时，修改BF为0，T的深度不变。②当T的根节点的BF为0时，修改BF为-1，T的深度增加1。③当T的根节点的BF为-1时，根据以下情况进行判断：如果T的右子树的BF为-1，则做RR型调整（单向左旋），修改旋转后的根节点及其右子树的根节点的BF为0，树的深度不变。如果T的右子树的BF为1，则做RL型调整（双向先左后右旋转），修改旋转后的根节点及其左、右子树的根节点的BF为0，树的深度不变。例题08-01已知一组关键字序列为{62，45，36，18，29，83，91，77，74}的节点，依次把节点插入到初始状态为空的平衡二叉树中，使得每一次插入后依然保持该树是平衡二叉树。以下是图示①

平衡二叉树的构建过程(椭圆虚线框为最小不平衡子树)②代码22-1-2-222已知：一组关键字序列为(62，45，36，18，29，83，91，77，74)，运用插入方法构造一颗二叉排序树，并实现查找、插入、删除节点等功能。输入要求：键盘输入节点数n及各个节点的关键字输出要求：（1）构建二叉树后，输出层序和中序遍历结果；（2）在插入节点后，输出二叉排序树的层序、中序遍历结果；（3）在删除节点后，输出变化后的层序、中序遍历结果算法分析1．二叉排序树的构造从空树开始，经过一系列查找、插入节点后，生成一颗二叉排序树。对于关键字为

{62，45，36，18，39，83，91，77，74}的9个节点，第一个节点（62）作为二叉树排序树的根，其他节点按照二叉排序树的定义依次插入到二叉排序树中，如图所示。2、二叉排序树的查找在二叉排序树中查找关键字等于key的节点，从树的根节点开始，如果根节点的关键字等于key，则查找成功。如果根节点的关键字大于key，则在其左子树中继续查找；如果根节点的关键字小于key，则在其右子树中继续查找。若直到整棵树都查找完，依然没有找到关键字等于key的节点，则查找失败。3．二叉排序树的删除在二叉排序树中删除关键字等于key的节点p（目标节点），且仍然要保持二叉排序树的特性，这就需要根据目标节点的不同情况分别进行处理。（1）p的左子树为空如果目标节点的左子树为空，则关键字等于77、36、49、79、91的节点都没有左子树，删除此类节点只需用其右子树替代它的位置即可，如图中（b）所示。节点的删除（2）p的左子树不空，但右子树为空如果目标节点的左子树不空，但是右子树为空，如图中（c）所示，那么节点58有左子树，但没有右子树，直接用它的左子树替代原来的位置即可。（3）p的左子树不空，右子树也不空如果目标节点的左、右子树都不为空，那么关键字等于45、62、83的节点都有左、右子树，删除此类节点需要先找到目标节点的左子树的根和最大值节点，左子树的根替代删除目标节点p的位置，然后用目标节点p的右子树作为找到的最大值节点的右子树。如图中（d）（e）（f）（g）所示为删除目标p节点左右子树均不空，且P还是根节点。1、根据任务要求和算法分析设计程序；2、编码、调试、运行；3、做好记录；4、总结。对动态查找表进行高效率查找，则可以采用二叉排序树、平衡二叉树等特殊的二叉树作为表的组织形式。静态查找表中，二分查找效率最高，其时间复杂度是O(log2n)，但维护表的有序性的时间复杂度为O(n)。静态查找可以采用顺序查找、二分查找和分块查找等技术。二叉排序树的中序遍历结果是线性有序的。通常，只要二叉树深度为O(log2n)，就可以看作是平衡树。单元数据结构算法讲解实操01线性表顺序表数组顺序查找二分查找二分查找02顺序表数组链表简单选择排序简单选择排序03线性表顺序表链表栈递归算法递归算法04线性表顺序表数组链表快速排序快速排序05