《算法与数据结构》第7章 检索及基本算法ppt.ppt

算法与数据结构 第7章 检索及基本算法 第7章 检索及基本算法 7.1 检索的概念 7.2 线性表的检索 7.3 树表的检索 7.4 哈希检索 检索的概念 n检索（searching）也称作查找，是一种常用的基本 运算。 n人们几乎每天都要做检索的工作，如在电话号码 薄中查找某单位或某个人的电话号码，在字典中查 找某个词的含义或读法，在图书馆查找某本书刊的 编号，上网在各种数据库中查找某些需要的文献资 料等等。 n在语言翻译的编译程序中要对符号表查找，在数 据库系统中要用SQL语言为各种应用设计查找程序 ，如此等等。 检索的概念(续) n简言之，检索就是在“大量信息”中查找一个“ 特定的”信息。 n这里的大量信息是检索所依赖的数据结构，称之 为检索表（search table）； n检索表是由同一类型的数据元素（或记录）组成 的集合。 n由于集合是一种松散型数据结构，数据元素除了 同属于一个集合外再无别的关系，所以检索表是 一种非常灵活的数据结构。 检索的概念(续) n对检索表常做的运算和操作有： n 查找某个特定的数据元素是否在检索表中； n 检索某个特定的数据元素的各种属性； n 在检索表中插入一个数据元素； n 从检索表中删去某个数据元素。 n若对查找表只作前两种统称为“检索”的操作，称 此类检索表为静态检索表（static search table） ； n若在检索的过程中同时插入表中不存在的数据元素 ，或者从检索表中删除已存在的某个数据元素，称 此类检索表为动态检索表（dynamic search table ）。 检索的概念(续) n 所谓特定的信息，是指关键字值等于给定值的信 息，信息的单位是数据元素或记录。 n 关键字（key）是数据元素（或记录）中某个数据 项的值，用它可以标识一个数据元素（或记录）。 显然，在一个记录中的每个数据项都可以作为标识 该记录的关键字。如人事档案记录结构为： 它含有五个关键字，其中性别这个关键字标识了 一个职工的性别情况。 检索的概念(续) n主关键字（primary key）是指能惟一标识一个 数据元素（或记录）的关键字。如上述记录中身 份证号码是主关键字，可以惟一标识一条记录； 而姓名、性别、年龄、工资级别不能惟一标识一 条记录，它们都不是主关键字。 n辅关键字（secondary key）是用以标识若干数 据元素（或记录）的关键字，也称作次关键字或 从关键字。如上述记录中的姓名、性别、年龄、 工资级别都是辅关键字。 检索的概念(续) n检索，就是根据给定的某个值，在检索表中查 找一个关键字等于给定值的记录的运算或操作。 n若在检索表中存在这样的记录，则称检索成功 ，检索的结果是找到记录的全部信息（或找到记 录在检索表中的位置）； n若检索表中不存在关键字值等于给定值的记录 ，则称检索失败，给出在检索表中无要查找的记 录的信息提示，并在动态检索时插入关键字等于 给定值的记录于检索表中。 检索的概念(续) n 在检索表中查找某个数据元表（或记录）的过 程，依赖于这个数据元表（或记录）在查找表中 所处的位置；对检索表的检索方法取决于检索表 中数据元表（或记录）的组织策略。 n如在字典中查找一个英文单词，由于字典是按字母顺 序编排的，所以不需从第一个单词顺序查找，而只是 按待查单词中每个字母在字母表中的位置快速找到该 单词； n而在数据元素（或记录）之间无任何关系组织起 来的集合中查找，则需要从第一个元素（或记录 ）开始依次顺序查找。 检索的概念(续) n 在计算机中进行检索是对已存入计算机中的数 据进行检索，取决于采用何种数据结构来组织检 索表；往往需要在数据元素（或记录）之间人为 地加上一些关系，即用非集合结构如数组、文件 、二叉树、散列表等结构来组织检索表，以便按 某种规律来进行检索。 n依数据组织方式不同，检索分为线性表检索、树 表检索和散列表检索等。 n 衡量一个检索算法的优劣，主要依据在检索过 程中给定值和关键字的比较操作次数。为此，我 们引入平均检索长度的概念。 平均检索长度 n检索算法的平均检索长度（average search length），即在检索过程中用给定值和关键字进 行比较的平均比较次数， n或者说是为找到具有给定值关键字的记录所需 要的比较次数的平均值。 n它是为确定记录在检索表中的位置，需要和给 定值进行比较的关键字个数的期望值。 平均检索长度（续） n 对于含有n个记录的检索表，检索成功时的平均 检索长度为 n其中，Pi为检索第i个记录的概率，且 ； 一般在不特殊说明的情况下均认为是等概率，即 检索每个记录的概率相等， 。 nCi为找到第i个记录需要和给定值比较的关键字的 个数，它随检索方法的不同而不同。 第7章 检索及基本算法 7.1 检索的概念 7.2 线性表的检索 7.3 树表的检索 7.4 哈希检索 线性表的检索 n 在检索表的数据组织方式中，线性表是最基本的 ，也是最常用的一种组织方式。本节主要讨论在顺 序存储结构实现的线性表上的检索算法，其类型定 义描述为 typedef struct keytype key; /*关键字类型*/ elemtype other; /*其它域*/ sqlist; sqlist Rn+1; /*顺序表*/ n本节介绍的线性表检索方法有顺序检索、二分法 检索、黄金点检索、精算点检索和分块检索等。 7.2 线性表的检索 7.2.1 顺序检索 7.2.2 二分法检索 7.2.3 黄金分割点检索 7.2.4 精算点检索 7.2.5 分块检索 顺序检索 n 顺序检索（sequential search）是一种最简单的基 本检索方法。 n其基本思路为： n从表的一端开始，用给定值逐个与表中各记录的关键字 值比较。 n若找到某个关键字值等于给定值的记录，则检索成功， 并给出该记录在表中的位置； n若检索完整个表仍未找到关键字值等于给定值的记录， 则检索失败，并给出失败信息。 n 顺序检索方法既适用于线性表的顺序存储结构， 也适用于线性表的链式存储结构。 顺序检索举例 n以顺序存储结构为例，设数据元素存放在数组中 下标从1到n的记录中，0号记录位置留作监视哨， 从下标为n的一端开始向另一端检索，顺序检索算 法可描述如下： int seqsearch(sqlist R,keytype k) int i=n; R0.key=k; /*设置R0为监视哨*/ while(Ri.key != k) i-; return i; /*返回检索结果i*/ 顺序检索举例（续） n 算法中设置监视哨R0，可以使得在检索成功和 检索失败时的处理一致，在检索失败时也能在监视 哨位置找到关键字值为k的记录，可省去在while循 环中的位置越界检查（i=1）。 n若从R0处向后顺序检索，监视哨可设置在Rn 处。 n算法执行之后，非0的函数值表示待查找记录在 数组中的位置（下标）；若函数值为0说明检索表 中没有要查找的记录。 顺序检索（续） n对于具有n个记录的检索表，若待查找记录在Rn 处，需要和给定值k比较一次，即Cn=1； n若待查找记录在Rn-1处，需要和给定值k比较两 次，即Cn-1=2； n一般地，若待查找记录在Ri处，需和给定值k比 较n-i+1次，即Ci=n-i+1。 n因此，在等概率的情况下顺序检索的平均检索长 度为 顺序检索（续） n在检索成功时顺序检索的平均比较次数约为表长 的一半。 n在检索失败时，顺序检索需要进行n+1次的比较 。 n当n很大时，平均检索长度也很大，检索效率较 低，这是顺序检索的主要缺点。 n但由于顺序检索对表的存储结构和元素存放次序 没有要求，且算法简单，在许多实际应用中常被 采用。 7.2 线性表的检索 7.2.1 顺序检索 7.2.2 二分法检索 7.2.3 黄金分割点检索 7.2.4 精算点检索 7.2.5 分块检索 二分法检索 n二分法检索（binary search），也称作折半检索 ，它是一种效率较高的检索方法。它要求检索表是 用顺序存储结构表示，且数据元素的存放要按关键 字值有序排列。 n二分法检索的基本思想是： n在有序表中先取中间位置作为比较对象，若给定值与中间 记录的关键字值相等，则检索成功； n若给定值小于中间记录的关键值则在表的左半区查找， n若给定值大于中间记录的关键字值则在表的右半区查找。 n就这样经过一次的比较缩小一半的检索区间，在每一个检 索区间都是选取中间位置作为比较对象，不断地重复这样 的检索过程直到检索成功，或者检索区间已无记录时检索 失败。 二分法检索举例 n例如：已知一个含15个记录的有序表，其关键字序 列如下： （07 10 14 18 21 23 25 29 31 35 38 42 46 49 52） n现在要检索给定值k为19、46和11的记录，其检索 过程如下： n用low和high分别表示检索区间的下界和上界； n用mid指示中间位置，即mid=(low +high)/2； n检索开始时low=1，high=n；即检索区间为1，n 。 二分法检索举例检索k=18 n检索k=18的过程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=8 high=15 n检索开始时，low=1，high=15，mid=(1+15)/2=8。 由于k=1829=R8.key，所以应在右半区继续检索 ；此时low=mid+1=8+1=9，mid= (9+15)/2=12，即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=9 mid=12 high=15 n由于k=4642=R14.key，所以应在当前区间的右 半区继续检索； 二分法检索举例检索k=46(续) n此时low=12+1 =13，mid=(13+15)/2=14，即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=13mid=14high=15 n由于k=4610=R2.key，应在当前区间的右半区继 续检索；此时low=2+1=3，mid= (3+3)/2=3，即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=3 mid=3 high=3 n由于k=11100，则可有如下近似结果： 二分法检索过程分析（续） n由此可见，二分法检索的效率比顺序检索高得多 ，如n=127时，顺序检索ASL64而二分法则为 ASL6。 n二分法检索只适用于检索表为顺序存储结构之下 的有序表，即这种较高的检索效率是以对检索表预 先按关键字值大小排序为代价的，所以二分法检索 适合于一旦建立很少变动而又需要经常检索的检索 表。 7.2 线性表的检索 7.2.1 顺序检索 7.2.2 二分法检索 7.2.3 黄金分割点检索 7.2.4 精算点检索 7.2.5 分块检索 黄金分割点检索 n黄金分割点检索（gold-partition search），简称黄 金点检索。它是利用我国著名数学家华罗庚院士当 年推广优选法时介绍的黄金分割点的概念，即利用 黄金分割数0.618把检索区间分为两个不等的区间。 n每次用给定值与黄金点上的记录的关键字比较， 若相等检索成功，若给定值小于黄金点关键字值， 继续在黄金点之前的区间检索；若给定值大于黄金 点关键字值，继续在黄金点之后的区间检索。 n通过黄金点逐次缩小检索区间，直到检索成功， 或区间已无记录检索失败时止。 黄金分割点检索举例 n 例如，仍以前面的15个记录为例，检索k46的黄金分割点 检索过程为： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=9 high=15 n开始时low=1，high=15，mid=low+0.618*(high-low+1)- 1=1+0.618*(15-1+1)-1=9.329。给定值k=4631=R9.key，在 黄金点之后的区间继续检索。此时low=9+1=10， mid=10+0.618*(15-10+1)-1=12.70813。即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=10 mid=13 high=15 n 由于k=46=R13.key 检索成功。一个用二分法检索需4次比 较的工作，黄金分割点检索只需两次比较就完成了。 黄金分割点检索算法描述 int goldpartsearch(sqlist R,keytype k) int low,mid,high; low=1; high=n; while(lowRmid.key则 在mid之后检索。 精算点检索（续） n在关键字值均匀分布时，如呈等差数列时一次比 较便可检索成功；在关键字值分布比较均匀时， 若一次比较不能找到也会在mid位置附近，这两种 情况的检索长度与检索表的大小n无关，所以称之 为精算点检索。 n如果关键字值分布不均匀，可缩小检索区间继续 用前面的估算公式确定检索点检索，其检索性能 也优于黄金分割点检索和二分法检索。 精算点检索举例 n例如，对于前述的15个记录的检索表，检索k=14 的记录，low=1，high=15， ， R3.key=14等于给定值，一次比较检索成功；又如 检索k=29时， ，一次比较 Rn.key=29等于给定值检索成功；再如检索k=46时 ， ，一次比较R13.key=46等 于给定值检索成功；等等。 精算点检索举例（续） n既然在关键字值分布较均匀时，即使一次比较不 能检索成功也会在mid位置附近，在算法设计时就只 需一次计算mid的值。 n若k=Rmid.key，则一次比较检索成功； n若kRmid.key，则可由mid后一个记录开始向后 顺序检索，直到检索成功或某个记录的关键字值大 于给定值k时检索失败。 精算点检索算法描述 n这种与顺序检索相结合的精算点检索算法可描述如下： int precisesearch(sqlist R,keytype k) int low,mid,high; low=1; high=n; mid=low+(k-Rlow.key)*(high-low)/ (Rhigh.key-Rlow.key)+0.5; if(k=Rmid.key) return mid; else if(kk) mid-; 精算点检索算法描述（续） if(Rmid.key=k) return mid; /*检索成功返回位置*/ else return 0; /*检索失败返回0*/ else mid+; /*若给定值大于mid时在mid后检索*/ while(Rmid.key50则在右 子树中继续检索；再用80和右子树的根70比 较，8070则继续在当前根结点70的右子树 中检索；当再次和新的当前根结点比较时二 者相等检索成功，返回指向当前根结点的指 针。 n又如检索k=15的记录时，由于15小于根结 点50，在其左子树继续检索；15又小于左子 树的根结点40，继续在当前根结点40的左子 树中检索；15也小于当前根结点40的左子树 的根结点20，当在20的左子树中继续检索时 发现20的左子树为空，检索失败返回NULL。 二叉检索树的二叉链表类型 n 设二叉检索树以如下描述的二叉链表作为存储结 构： typedef struct node keytype key; /*关键字域*/ elemtype other; /*其它数据域*/ struct node *lchild, *rchild; /*左右孩子指针域*/ bstnode; /*定义结点类型bstnode*/ typedef bstnode *bstlist; /*定义二叉检索树表类型bstlist*/ 二叉检索树的检索算法描述 n 二叉检索树的检索算法可描述如下： bstlist bstsearch(bstlist t,keytype k) bstlist p ; p=t; if(p=NULL)|(p-key=k) return p; else if(p-keyrchild,k); else return bstsearch(p-lchild,k); /*bstsearch end*/ 2.二叉检索树的构造过程和插入操作 n对于一组关键字无序的记录，构造其相应的二叉检 索树的方法是：从一棵空的二叉检索树开始，每当读 入一个记录就生成一个结点，然后按关键字值的大小 插入到当前的二叉检索树之中；当所有记录的结点都 已插入二叉检索树中时便构造完毕。 n虽然，插入操作是构造二叉检索树的关键操作。要 保证在一棵二叉检索树中插入一个结点之后，仍然满 足二叉检索树的定义。其插入过程为： n若二叉检索树为空，则插入结点作为新的根结点； n若二叉检索树非空，则在非空的二叉检索树中检索插入结点 ；如果检索成功就不必插入，否则插入结点作为新的叶结点 ，并成为检索路径上最后一个结点的左孩子或右孩子。 二叉检索树的构造过程和插入操作(续 ) n为了实现这一插入过程，在二叉检索树非空时需要 知道检索路径上的最后一个结点位置，才能够准确地 把插入结点作为左孩子或右孩子插入二叉检索树中； 为此；需要在检索过程中设一指针变量记下当前结点 的前趋（即双亲）结点位置。 n插入算法的形式化描述如下： bstlist insertbst(bstlist t,keytype k) bstlist s,p,q; if(t=NULLl) p=(bstlist)malloc(sigeof(bstnode); p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; return p; 二叉检索树的构造过程和插入操作(续 ) p=t; while(p!=NULL) q=p; if(p-key=k) /*检索成功不必插入*/ return t; /*返回原二叉检索树*/ else if(p-keyrchild; else p=p-lchild; p=(bstlist)malloc(sizeof(bstnode); 二叉检索树的构造过程和插入操作(续 ) p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; if(kq-key) q-rchild=p; else q-lchild=p; return t; 二叉检索(排序)树构造过程举例 n从空树出发经过一系列的检索插入操作之后，就可生成一 棵二叉检索树。一个无序序列可以通过构造一棵二叉检索树 而变成一个有序序列（即中序遍历次序序列），构造的过程 就是对无序序列进行排序的过程，所以又称作二叉排序树。 n设关键字序列为（45，22，57，18，29，92），生成二叉 检索树（即二叉排序树）的过程如下图所示。 3.二叉树检索树的删除操作 n在二叉检索树中删除一个结点，相当于在检索表中 删除一个记录，不能把以待删除结点为根结点的子树 全部删去，并且要保证删除某个结点后的二叉树仍然 是一棵二叉检索树。下面，我们分三种情况讨论如何 在二叉检索树中删除一个结点。 待删除结点是度为0的叶子结点 删除一个叶子结点*p，不破坏整棵树的结构，只 需将其双亲结点*f与*p之间相链接的指针域置为空即 可： f-lchild=NULL; 或 f-rchild=NULL; 二叉树检索树的删除操作（续） 待删除结点是度为1的单枝结点 即待删除结点只有左子树或只有右子树的情况，如下图所 示。此时只需将待删除结点*p的惟一后继结点（左孩子或右 孩子）直接链接到其双亲结点*f的相应位置（即左链域或右 链域）上即可： (a) f-lchild=p-lchild; 或 (b) f-lchild=p-rchild; 或 (c) f-rchild=p-lchild; 或 (d) f-rchild=p-rchild; 二叉树检索树的删除操作（续） 待删除结点是度为2的双枝结点 即待删除结点既有左子树又有右子树的情况， 如下图所 示，为了保持二叉检索树的特性，通常有如下四种做法。 二叉树检索树的删除操作方法一 n方法一：找出待删除结点*p的中序前趋结点*q，把*q的关键 字域和数据域的值赋给*p的相应域，即： p-key=q-key; p-other=q-other; n然后删除其中序前趋结点*q，由于*p的中序前趋*q是*p左子 树上的最右下结点，所以*q必是叶子结点或单左枝结点，如 下图所示；其删除方法见和。 二叉树检索树的删除操作方法二 n方法二：找出待删除结点*p的中序后继结点*q，把*q的关键 字域和数据域的值赋给*p的相应域，即： p-key=q-key; p-other=q-other; n然后删除其中序后继结点*q。由于*p的中序后继*q是*p右子 树上的最左下结点，所以*q必是叶子结点或单右枝结点，如 下图所示；其删除方法见和。 二叉树检索树的删除操作方法三 n方法三：将待删除结点*p的右子树链接到它的中 序前趋结点（即左子树上的最右下结点）*q的右孩 子域上，然后把它的左子树直接链接到其双亲结点 *f的左（或右）孩子域上。即： q-rchild=p-rchild; f-lchild（或f-rchild）=p-lchild; 二叉树检索树的删除操作方法四 n 方法四：将删除结点*p的左子树链接到它的中序 后继（即右子树上的最左下结点）*q的左孩子域上 ，然后把它的右子树直接链接到其双亲结点*f的左 （或右）孩子域上。即： q-lchild=p-lchild; f-lchild（或f-rchild）=p-rchild; 二叉树检索树的删除操作（续） n前两种方法是以删除待删除结点*p的中序前趋或 中序后继*q来实现删除结点*p之目的，不需要知道 待删除结点的双亲结点位置； n后两种方法是直接删除待删除结点*p，不仅需要 知道其中序前趋或中序后继*q的位置，还需要在检 索待删除结点*p的同时记住其双亲结点的位置。 二叉树检索树的删除操作（续） n 方法一和方法三中*p的中序前趋*q（即左子树中 的最右下结点）可以如下确定： q=p-lchild; while(q-rchild!=NULL) q=q-rchild; n而方法二和方法四中*p的中序后继*q（即右子树中 的最左下结点）的确定方法为： q=p-rchild; while(q-lchild!=NULL) q=q-lchild; 二叉检索树的删除算法描述 n下面我们给出采用方法四删除双枝结点时的二叉检 索树的删除算法描述如下： bstlist deletebst(bstlist t,keytype k) bstlist p,q,r,f; p=t; f=NULL; while(p!=NULL) if(kkey) p=p-lchild; else p=p-rchild; 二叉检索树的删除算法描述（续） if(p=NULL) break; /*检索失败时不用删除中断执行*/ if(p-lchild=NULL)|(p-rchild=NULL) q=p; /*待删除的*p为叶子结点或单枝结点时*/ else q=p-rchild; while(q-lchild!=NULL) q=q-lchild; if(q-lchild!=NULL) r=q-lchild; else r=q-rchild; 二叉检索树的删除算法描述（续） if(p!=q) q-lchild= p-lchild; if(f-lchild=p) f-lchild=r; else f-rchild=r; return t; /*返回删除操作后的二叉检索树*/ /*deletebst end*/ 4.二叉检索树的检索性能分析 n在二叉检索树上检索关键字值等于给定值k的记录 ，正好是走了一条从根结点到关键字值为k的结点的 路径，和给定值k的比较次数为路径长度加1（或结点 所在层次数），和二分法检索类似，其比较次数不超 过树的深度。 n然而，用二分法检索一个长度为n的检索表其检索 过程的二叉树表示是惟一的，而含有n个结点的二叉 检索树却不惟一。 二叉检索树的检索性能分析举例 n例如，如下图给出了结点值都相同的两棵二叉检索 树，由于构造时的关键字序列不同，前者深度为3， 而后者深度为7；在等概率的情况下，前者的平均检 索长度为ASL=(1+2+2+3+3+3+3)/7=17/7，后者的平均 检索长度为ASL=(1+2+3+4+5+6+7)/7= 28/7=4。 二叉检索树的检索性能分析（续） n 因此，含有n个结点的二叉检索树的平均检索长度 和二叉检索树的形态有关，当先后插入的关键字按值 有序时，构造的二叉检索树蜕变为单枝树； n升序时为单右枝二叉树，降序时为单左枝二叉树； n树的深度为n，平均检索长度为(n+1)/2（和顺序检 索相同），这是最差的情况。最好的情况是二叉检索 树的形态和二分法检索过程得到的树相同，树的高度 和完全二叉树的高度相同，其平均检索长度为 。 二叉检索树的检索性能分析（续） n现在我们考虑在一般情况下二叉检索树的平均检索 长度，假设在含有n个结点的二叉树中，有i个结点关 键字值小于根结点的关键字值，n-i-1个结点关键字值 大于根结点的关键字值。 n在等概率检索的情况下平均检索长度为： n其中，p(i)为含有i个结点的二叉检索树的平均检索长度； p(i)+1为检索左子树中每个结点所用比较次数的平均值， p(n-i-1)+1为检索右子树中每个结点所用比较次数的平均值 。 二叉检索树的检索性能分析（续） n由于根结点的左子树中有0个，1个，n-1个结点 的情况是等概率的，对上式取平均值得： n用数学归纳法可以证明， ，即二叉 检索树的平均长度为 。 7.3 树表的检索 7.3.1 二叉检索树 7.3.2 二叉检索树的平衡性调整 7.3.3 B树和B+树 平衡因子 n平衡因子（balance factor） n二叉树上任一结点的平衡因子，定义为该结点的左子树深 度减去右子树深度的差。 n如下图中给出了一些二叉树，其结点上所示数值为 该结点的平衡因子值。 平衡二叉树 n平衡二叉树（balance binary tree） n如果一棵二叉树中所有结点的平衡因子的绝对值不超过1 ，则称该二叉树为平衡二叉树；平衡二叉树也称作AVL树 。 n显然，AVL树要么是一棵空树，要么其左右子树深 度不超过1且都是AVL树；只要二叉树上有一个结点 的平衡因子的绝对值大于1，该二叉树就是不平衡的 。如前例图中，(a)和(b)都是平衡二叉树（即AVL树 ），而(c)和(d)都不是平衡二叉树（即非AVL树）。 平衡二叉树（续） n由于AVL树具有良好的形态，其左右子树的深度差不 超过1；对于给定的结点数目n，AVL树的平均深度接 近于完全二叉树的深度 ； n所以我们希望由任何初始序列构成的二叉检索树都 是AVL树，使得其平均检索长度接近于 。 n如何使构造的二叉树成为AVL树呢？Adelson- Velskii和Landis提供了一个动态地保持二叉检索树 平衡性的方法； n其基本思想是在构造二叉检索树的过程中，每当插入一个 结点后都去检查是否由于该结点的插入而破坏了二叉检索 树的平衡性；若出现绝对值超过1的平衡因子，则需要在保 持二叉检索树特性的前提下通过调整使之达到新的平衡。 平衡二叉树（续） n在一般情况下，设在插入结点的过程中使二叉检 索树失去平衡的最小子树的根结点为a，即a为离插 入结点最近且平衡因子绝对值超过1的祖先结点； n因插入结点的位置不同而失去平衡需要调整的规 律可归纳为如下四种情况： nLL型平衡旋转（右单旋型） nRR型平衡旋转（左单旋型） nLR型平衡旋转（先左后右双旋型） nRL型平衡旋转（先右后左双旋型） 1.LL型平衡旋转（右单旋型 ） n这种失衡是由于在结点a的左孩子b的左子树上插入结点， 使结点a的平衡因子由1增至2而造成的。 n其调整策略是以a的左孩子b为轴心顺时针旋转（即向右旋 转）一次；使结点a成为其左孩子b的右孩子，而b的右子树 成为a的左子树，如下图所示。这种调整策略既使结点的平 衡因子满足AVL树的要求，又保持了二叉检索树的特性（即 中序遍历次序为上升序列）。 2.RR型平衡旋转（左单旋型 ） n这种失衡是由于在结点a的右孩子b的左子树上插入结点， 使a的平衡因子由-1变成-2而造成的； n其调整策略是以a的右孩子b 为轴心逆时针旋转（即向左旋 转）一次；使a成为b的左孩子，而b的左子树成为a的右子树 ，如下图所示。 3. LR型平衡旋转（先左后右双旋型 ） n这种失衡是由于在结点a的左孩子b的右子树上插入结点， 使a的平衡因子由1增至2造成的。 n设c是b的右孩子，插入结点的位置有三种可能性： nc就是插入结点，这是由于插入前b为叶子结点且a无右孩子而产生的 一种可能； n插入结点在c的左子树上； n插入结点在c的右子树上。 LR型平衡旋转（续） n对这三种导致LR型失衡的情况，其调整策略是一致的： n即以a的左孩子b的右孩子c为轴心，先逆时针（即向左）旋 转一次，再顺时针（即向右）旋转一次；使c的左子树成 为b的右子树，c的右子树成a的左子树，b成为c的左孩子而 a成为c的右孩子，以“插入在c的左子树上”为例，两次旋 转的调整过程如下图所示。 4. RL型平衡旋转（先右后左双旋型 ） n这种失衡是由于在结点a的右孩子b的左子树上插 入结点，使a的平衡因子由-1变成-2造成的，设c是b 的左孩子，插入结点位置的三种可能性如下图所示 ： RL型平衡旋转（续） n对这三种导致RL型失衡的情况，其调整策略为： n以a的右孩子b的左孩子c为轴心，先顺时针（即向右）旋 转一次，再逆时针（即向左）旋转一次；使c的左子树成 为a的右子树，c的右子树成为b的左子树，a成为c的左孩 子而b成为c的右孩子。以“插入在c的左子树上”为例， 两次旋转的调整过程如下图所示： 构造平衡二叉检索树举例 n例如，对于一组记录其关键字