数据结构课程讲义9课件

n这这也也是是线线性性表表的的基基本本运运算算之之一一。通通常常称称为为检检索索、查询等。查询等。n1线性查找线性查找n11顺序检索顺序检索n基本思想：基本思想：n从从线线性性表表的的一一端端开开始始，逐逐个个地地将将待待查查找找元元素素的的关关键键字字与与每每个个元元素素的的关关键键字字进进行行比比较较，若若找找到到，则则返返回回1，否则返回否则返回0。n该算法的时间该算法的时间复杂度为复杂度为O(n).1 线性查找顺序查找采用顺序查找采用顺序查找采用顺序查找采用从头至尾逐个比较从头至尾逐个比较从头至尾逐个比较从头至尾逐个比较最快最快最快最快O(1)O(1)最慢最慢最慢最慢O(n)O(n)查找成功的查找成功的查找成功的查找成功的等概率平均时间复杂性等概率平均时间复杂性等概率平均时间复杂性等概率平均时间复杂性 O(O(n+1)/2(n+1)/2)1/n(1+2+3+n)=(n+1)/21/n(1+2+3+n)=(n+1)/2查找失败查找失败查找失败查找失败O(n+1)O(n+1)查找的等概率平均时间复杂性查找的等概率平均时间复杂性查找的等概率平均时间复杂性查找的等概率平均时间复杂性 O(O(3(n+1)/43(n+1)/4)查找成功失败各半查找成功失败各半查找成功失败各半查找成功失败各半1/21/2n(1+2+n)+n(n+1)=n(1+2+n)+n(n+1)=3(n+1)/43(n+1)/4 1 线性查找 1 线性查找n12二分查找二分查找n亦亦亦亦称称称称折折折折半半半半查查查查找找找找，是是是是基基基基于于于于提提提提高高高高查查查查找找找找速速速速度度度度的的的的一一一一种种种种方方方方法法法法。检索时要求元素是排序的。检索时要求元素是排序的。检索时要求元素是排序的。检索时要求元素是排序的。n基本思想：基本思想：n每每次次将将待待查查找找元元素素的的关关键键字字与与已已排排序序元元素素序序列列的的中中间间点点元元素素进进行行比比较较，如如相相等等，则则返返回回1，否否则则修修改改高高点点或低点，重新进行查找比较。或低点，重新进行查找比较。n该算法的时间复杂度为该算法的时间复杂度为O(n).这是有序表的查找查找这是有序表的查找查找对已排序的查找结构先确定中点，比较待查关对已排序的查找结构先确定中点，比较待查关对已排序的查找结构先确定中点，比较待查关对已排序的查找结构先确定中点，比较待查关键字与中点关键字的大小，反复直到成功。键字与中点关键字的大小，反复直到成功。键字与中点关键字的大小，反复直到成功。键字与中点关键字的大小，反复直到成功。求求求求n n个数据折半查找的等概率成功查找的平均个数据折半查找的等概率成功查找的平均个数据折半查找的等概率成功查找的平均个数据折半查找的等概率成功查找的平均时时时时间复杂性间复杂性间复杂性间复杂性 123456789101234567891012233334441+2*2+4*3+3*4=29 O(29/10)n个元素的折半查找个元素的折半查找2k-1n2k+1-1查找成功平均概率时间复杂性 介于 log2(2k)-1 和 log2(2k+1)-1 之间即 k-1 和 k 之间 k=log2(n+1)n个元素的折半查找成功平均概率时间复杂性 log2(n+1)-1/2 1 线性查找n n1 133分块查找分块查找分块查找分块查找n亦亦亦亦称称称称索索索索引引引引顺顺顺顺序序序序查查查查找找找找。也也也也是是是是基基基基于于于于提提提提高高高高查查查查找找找找速速速速度度度度的的的的一一一一种种种种方方方方法法法法。检检检检索索索索时时时时要要要要求求求求元元元元素素素素构构构构成成成成的的的的块块块块间间间间是是是是排排排排序序序序的的的的，而而而而块块块块内内内内是是是是未排好序的。未排好序的。未排好序的。未排好序的。n n基本思想：基本思想：基本思想：基本思想：n将将将将所所所所有有有有元元元元素素素素按按按按关关关关键键键键字字字字值值值值划划划划分分分分成成成成若若若若干干干干块块块块，块块块块之之之之间间间间是是是是排排排排序序序序的的的的，而而而而块块块块内内内内暂暂暂暂时时时时是是是是无无无无序序序序的的的的。查查查查找找找找时时时时候候候候，首首首首先先先先折折折折半半半半查查查查找找找找确确确确定定定定元元元元素素素素所所所所在在在在的的的的块块块块，然然然然后后后后再再再再在在在在块块块块内内内内进进进进行行行行顺顺顺顺序序序序查查查查找找找找即即即即可可可可比比比比较。较。较。较。3、索引顺序查找 分块有序 后一子表中的关键字都大于前一子表中的关键字22 48 86 1 7 132212138920334244382448605874498653 最大关键字 起始地址索引表索引顺序表的查找索引顺序表的查找 查找 关键字key=38 1.先检索索引表 确定子表位置 2.再在子表中查找22 48 86 1 7 132212138920334244382448605874498653索引表分块查找成功的平均概率时间复杂性分块查找成功的平均概率时间复杂性 索引表查找时间索引表查找时间+子表查找时间子表查找时间设索引表长为设索引表长为s，查找表长为查找表长为n,被被平均分成平均分成s块，块，每块长每块长n/s,索引表平均查找时间索引表平均查找时间(s+1)/2子表平均查找时间子表平均查找时间(n/s+1)/2(s+1)+(n/s+1)=(s+n/s)+1当当s=n时时有最小值有最小值n+1当索引顺序表已经排序时，子块查找可以用折半当索引顺序表已经排序时，子块查找可以用折半当索引顺序表已经排序时，子块查找可以用折半当索引顺序表已经排序时，子块查找可以用折半查找。查找。查找。查找。平均查找时间：平均查找时间：平均查找时间：平均查找时间：(s+1)/2+log(s+1)/2+log2 2(1+n/s)-1/2(1+n/s)-1/2=log=log2 2(1+n/s)+s/2(1+n/s)+s/2索引也用折半查找，平均查找时间索引也用折半查找，平均查找时间索引也用折半查找，平均查找时间索引也用折半查找，平均查找时间loglog2 2(s+1)-1/2+log(s+1)-1/2+log2 2(1+n/s)-1/2(1+n/s)-1/2=log=log2 2(s+1)(1+n/s)-1(s+1)(1+n/s)-1当当当当s=ns=n时时时时22loglog2 2(n+1)-1(n+1)-1 2 树形结构的查找n21二叉排序树及其查找过程二叉排序树及其查找过程n二二叉叉树树BT是是二二叉叉排排序序树树，只只要要BT是是满满足足如如下下的的条条件件：n（1）若若BT的的左左子子树树非非空空，则则其其左左子子树树上上所所有有结结点点的的值值均均小小于于其其根根结结点点的的值值；（2）若若其其右右子子树树上上所所有有结结点点的的值值均均大大于于其其根根结结点点的的值值；（3）其其左左右右子子树树均均为为二二叉叉排序树。排序树。n对二叉排序树的中序遍历的结果就是一个升序序列。对二叉排序树的中序遍历的结果就是一个升序序列。n二叉排序树又称为二叉查找树。二叉排序树又称为二叉查找树。n于于是是，只只要要将将元元素素序序列列组组织织成成二二叉叉排排序序树树，在在进进行行查查找找时时，让让待待查查找找元元素素与与根根结结点点值值进进行行比比较较，若若相相等等，则则查查找找成成功功，否否则则，如如果果比比根根结结点点小小，则则只只需需要要在在左左子子树树中中查查找找即即可可；如如果果比比根根结结点点大大，则则只只需需要要在在右右子子树树中中查找即可。查找即可。2 树形结构的查找n其所涉及到的数据结构如下：其所涉及到的数据结构如下：ntypedefstructbtnodenkeytypekey;ndatatypeother;nstructbtnode*lchild,*rchild;nnBSTNODE;nBSTNODE*ptr;n则则*ptr就表示一棵二叉排序树。就表示一棵二叉排序树。2 树形结构的查找n22二叉排序树实现查找运算二叉排序树实现查找运算n根根据据二二叉叉排排序序树树的的定定义义和和性性质质，不不难难得得到到其其查查找找算算法：法：nintbstsearch(*Pt,x)npkey=x)return(1);nif(p-keyx)prchild;nelseplchild;nnn二叉查找树的查找分析二叉查找树的查找分析平均等概率查找时间(1+2+2+3+3+3)/6=14/6451257820604512820311(1+2+3+4+5+6)/6=7/2随机二叉查找树等概率平均查找时间随机二叉查找树等概率平均查找时间 P(n)2(1+1/n)P(n)2(1+1/n)lnlnn n O(logO(log2 2n)n)最坏最坏最坏最坏O(n/2)O(n/2)特点：用于频繁进行插入、删除、查找的所谓特点：用于频繁进行插入、删除、查找的所谓动态查找表。动态查找表。12225030011020099二叉排序树二叉排序树LNPEMCY105230216查找步骤：若根结点的关键字值等于查查找步骤：若根结点的关键字值等于查找的关键字，成功。找的关键字，成功。否则，若小于根结点的关键字值，查其否则，若小于根结点的关键字值，查其左子树。左子树。若大于根结点的关键字值，查其右子树。若大于根结点的关键字值，查其右子树。在左右子树上的操作类似。在左右子树上的操作类似。12225030011020099105230216 2 树形结构的查找n2.2二叉排序树的插入运算二叉排序树的插入运算n由由于于插插入入运运算算是是二二叉叉树树的的基基本本运运算算之之一一，所所以以利利用用二二叉叉树树的的插插入入运运算算就就可可以以实实现现在在线线性性升升序序序序列列中中插插入入结结点，使之仍然是升序的功能。点，使之仍然是升序的功能。n其其实实现现过过程程为为：若若二二叉叉排排序序树树为为空空，则则待待插插入入结结点点*s就就作作为为根根结结点点插插入入到到空空二二叉叉树树中中；若若二二叉叉树树非非空空，则则比比较较s-key:p-key,若若，就插入到右子树中，若，就插入到右子树中，若=则不必插入。则不必插入。n该该过过程程是是递递归归的的，很很容容易易得得到到递递归归算算法法，也也可可以以得得到非递归算法。到非递归算法。2 树形结构的查找nvoidinsertbst(*pt,*s)np=pt;nwhile(p!=NULL)nfkeykey)nplchild;nelseprchild;nif(pt=NULL)ptkeykey)f-lchildrchildrchild=NULL,则则就就相相当当于于将将空空树树连接到连接到*fath的左（右）链域中。的左（右）链域中。2 树形结构的查找n（2）若若*p有有左左子子树树，则则*p也也可可能能有有右右子子树树，需需要要将将*p的的左左、右右子子树树按按照照二二叉叉排排序序树树的的特特性性，连连接接到到合合适适的的位位置置。此此时时可可以以采采用用两两种种处处理理方方法法：一一种种是是令令p的的左左子子树树直直接接连连接接到到*p的的双双亲亲*fath的的左左（右右）链链域域上上，而而*p的的右右子子树树下下接接到到*p的的中中序序前前趋趋结结点点*s的的右右链链域域上上。（这这里里*s是是*p的的左左子子树树中中最最右右下下的的结结点点，其其右右链链域域肯肯定定为空）。为空）。n另另外外一一种种处处理理方方法法是是：采采用用以以*p的的中中序序前前趋趋*s顶顶替替*p(相相当当于于将将*s的的内内容容复复制制到到*p中中)，将将*s的的左左子子树树直直接接上接到上接到*s的双亲的双亲*q左（右）链域上，再删去左（右）链域上，再删去*s。叶子结点：直接删除，更改它的父亲结点的相应指针域为空。叶子结点：直接删除，更改它的父亲结点的相应指针域为空。如：删除关键字为如：删除关键字为15、70的结点。的结点。15607030205060302050子树的根结点：通常的做法：选取子树的根结点：通常的做法：选取“替身替身”取代被删结取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点点。有资格充当该替身的是谁哪？左子树中最大的结点或或右子树中最小的结点，参看图。右子树中最小的结点，参看图。要点：维持二叉排序树的特性不变。在中序周游中紧靠要点：维持二叉排序树的特性不变。在中序周游中紧靠着被删结点的结点才有资格作为着被删结点的结点才有资格作为“替身替身”。12225030011020099105230216400450500子树的根结点：若被删结点的左儿子为空或者右儿子树的根结点：若被删结点的左儿子为空或者右儿子为空。子为空。如下图所示，删除结点的关键字为如下图所示，删除结点的关键字为99、200的结点。的结点。被删结点被删结点122250300200230216400450500110105删除删除9912225030011020099105230216400450500被删结点被删结点子树的根结点：若被删结点的左儿子为空或者右儿子树的根结点：若被删结点的左儿子为空或者右儿子为空。子为空。如下图所示，删除结点的关键字为如下图所示，删除结点的关键字为99、200的结点。的结点。122250300230216400450500删除删除20011099105 12225030011020099105230216400450500被删结点被删结点子树的根结点：若被删结点的左儿子为空或者右子树的根结点：若被删结点的左儿子为空或者右儿子为空。儿子为空。如下图所示，删除结点的关键字为如下图所示，删除结点的关键字为99、200的结的结点。点。结论：结论：将被删结点的另一儿将被删结点的另一儿子作为它的父子作为它的父亲结点的儿子，究竟是作为左亲结点的儿子，究竟是作为左儿子儿子还是右儿子依原替身结点和其还是右儿子依原替身结点和其父亲父亲结点的关系而定。结点的关系而定。释放被删结点的空间。释放被删结点的空间。被删结点被删结点 子树的根结点：若被删结点的左、右子树皆不空，通常的做子树的根结点：若被删结点的左、右子树皆不空，通常的做法：选取法：选取“替身替身”取代被删结点。有资格充当该替身的是谁取代被删结点。有资格充当该替身的是谁哪？哪？左子树中最大的结点左子树中最大的结点(被删结点的左子树中的最右的结被删结点的左子树中的最右的结点，其右儿子指针域为空点，其右儿子指针域为空)或或右子树中最小的右子树中最小的结点结点(被删结被删结点的右子树中的最左的结点，其左儿子指针域为空点的右子树中的最左的结点，其左儿子指针域为空)，参看，参看下图。下图。要点：维持二叉排序树的特性不变。在中序周游中紧靠着被要点：维持二叉排序树的特性不变。在中序周游中紧靠着被删删结点的结点才有资格作为结点的结点才有资格作为“替身替身”。12225030011020099105230216400450500被删结点被删结点替身替身替身替身11025030010520099230216400450500做法：将替身的关键字复制到被删结做法：将替身的关键字复制到被删结点的关键字。点的关键字。将结点将结点的左儿子作为的左儿子作为的父结点的父结点的右儿子。的右儿子。11011099注意：结点注意：结点右儿子必为空右儿子必为空结点结点的父结点为的父结点为11011099 12225030011020099105230216400450500被删结点被删结点替身替身替身替身20025030011099105230216400450500做法：将替身的关键字复制到被删结做法：将替身的关键字复制到被删结点的关键字。点的关键字。将结点将结点的右儿子作为的右儿子作为的父结点的父结点的左儿子。的左儿子。注意：结点注意：结点左儿子必为空左儿子必为空结点结点的父结点为的父结点为200200200200250 12225030011020099105230216400450500被删结点被删结点替身替身替身替身结论：结论：先将替身的关键字复制到被删结先将替身的关键字复制到被删结点点将原替身的另一儿子作为它的父将原替身的另一儿子作为它的父亲亲结点的儿子，究竟是作为左儿子还结点的儿子，究竟是作为左儿子还是右儿子依原替身结点和其父亲结是右儿子依原替身结点和其父亲结点的关系而定。点的关系而定。释放原替身结点的空间。释放原替身结点的空间。FP被删结点被删结点PRPLFP被删结点被删结点CCLPRQQLSSLFSCCLPRQQLSLFCCLPRQQLSSLFPRPL、PR皆皆空，空，直接删除直接删除。PL或或PR为空，为空，PL为空，删除为空，删除后的情况。后的情况。1.删除法删除法2.删除法删除法 2 树形结构的查找n24平衡二叉树简介平衡二叉树简介n由由于于二二叉叉排排序序树树的的结结构构形形态态直直接接影影响响到到查查找找的的效效率率，所所以以必必须须构构造造出出平平衡衡二二叉叉树树。只只要要满满足足平平衡衡因因子子（即即任任何何两两个个子子树树的的高高度度之之差差）只只能能是是-1，0，1的的，则则称称为为平平衡二叉树。衡二叉树。n通通常常情情况况下下，平平衡衡二二叉叉树树的的深深度度是是很很低低的的，所所以以其其查找效率是最高的。查找效率是最高的。DGEDABCFEGBA平衡二叉排序树平衡二叉排序树起因：提高查找速度，避免最坏情况出现。如右图情况的出现。起因：提高查找速度，避免最坏情况出现。如右图情况的出现。虽然完全树的树型最好，但构造困难。常使用平衡树。虽然完全树的树型最好，但构造困难。常使用平衡树。CF平衡因子（平衡度）：结点的平衡度是结点的左子树的高度右子树的高度。平衡因子（平衡度）：结点的平衡度是结点的左子树的高度右子树的高度。平衡二叉树：每个结点的平衡因子都为平衡二叉树：每个结点的平衡因子都为1、1、0的二叉树。或者说每个的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。结点的左右子树的高度最多差一的二叉树。注意：完全树必为平衡树，平衡树不一定是完全树。注意：完全树必为平衡树，平衡树不一定是完全树。平衡树的平衡树的Adelson算法的本质特点：算法的本质特点：以插入为例：以插入为例：在左图所示的平衡树中插入关键字为在左图所示的平衡树中插入关键字为2的结点。的结点。插入之后仍应保持平衡排序二叉树的性质不变。插入之后仍应保持平衡排序二叉树的性质不变。141253928635360501718730+1+1-1-1-100000000平衡树平衡树平衡树平衡树141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为0危机结点危机结点如何用最简单、最有效的办法保如何用最简单、最有效的办法保持平衡排序二叉树的性质不变？持平衡排序二叉树的性质不变？平衡树的平衡树的Adelson算法的本质特点：算法的本质特点：以插入为例：以插入为例：在左图所示的平衡树中插入关键字为在左图所示的平衡树中插入关键字为2的结点。的结点。插入之后仍应保持平衡排序二叉树的性质不变。插入之后仍应保持平衡排序二叉树的性质不变。141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为0危机结点危机结点如何用最简单、最有效的办法保如何用最简单、最有效的办法保持平衡排序二叉树的性质不变？持平衡排序二叉树的性质不变？解决方案：解决方案：不涉及到危机结点的父亲结点，即以危机结点不涉及到危机结点的父亲结点，即以危机结点为根的子树的高度应保持不变（左图为为根的子树的高度应保持不变（左图为3）。）。新结点插入后，找到第一个平衡度不为新结点插入后，找到第一个平衡度不为0的结的结点（如左图结点点（如左图结点）即可。新插入的结点和）即可。新插入的结点和第一个平衡度不为第一个平衡度不为0的结点（也可能是危机结的结点（也可能是危机结点）之间的结点，其平衡度皆为点）之间的结点，其平衡度皆为0在调整中，仅调整那些在平衡度变化的路径上在调整中，仅调整那些在平衡度变化的路径上的结点（如：的结点（如：），其它结点不），其它结点不予调整。予调整。仍应保持排序二叉树的性质不变。仍应保持排序二叉树的性质不变。9359141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为0危机结点危机结点如何用最简单、最有效的办法保如何用最简单、最有效的办法保持平衡排序二叉树的性质不变？持平衡排序二叉树的性质不变？23597122359712不可以以结点不可以以结点为子树的根为子树的根结点！虽然，对本例来说是可结点！虽然，对本例来说是可以行得通的。以行得通的。7141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为0危机结点危机结点关键：将导致出现关键：将导致出现危机结点的情况危机结点的情况危机结点的情况危机结点的情况全部分析全部分析清除，就可以使得平衡排序二叉树的性质保清除，就可以使得平衡排序二叉树的性质保持不变！持不变！14932528635360501718730+1+1-1-1-1000000012002.52.5 非平衡二叉树的平衡处理方法非平衡二叉树的平衡处理方法非平衡二叉树的平衡处理方法非平衡二叉树的平衡处理方法 若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比衡因子又比衡因子又比衡因子又比1 1大或比大或比大或比大或比-1-1小的结点。我们分四种情况讨论平衡处理。小的结点。我们分四种情况讨论平衡处理。小的结点。我们分四种情况讨论平衡处理。小的结点。我们分四种情况讨论平衡处理。1 1、LLLL型型型型 的处理的处理的处理的处理(左左型左左型左左型左左型)如如如如下下下下图图图图所所所所示示示示，在在在在A A的的的的左左左左孩孩孩孩子子子子B B上上上上插插插插入入入入一一一一个个个个左左左左孩孩孩孩子子子子结结结结点点点点C C，使使使使A A的的的的平平平平衡衡衡衡因因因因子子子子由由由由1 1变变变变成成成成了了了了2 2，成成成成为为为为不不不不平平平平衡衡衡衡的的的的二二二二叉叉叉叉树树树树序序序序树树树树。这这这这时时时时的的的的平平平平衡衡衡衡处处处处理理理理为为为为：将将将将A A顺顺顺顺时时时时针针针针旋旋旋旋转转转转，成成成成为为为为B B的的的的右右右右子子子子树树树树，而而而而原原原原来来来来B B的的的的右右右右子子子子树树树树则则则则变变变变成成成成A A的的的的左左左左子子子子树树树树，待待待待插插插插入入入入结结结结点点点点C C作作作作为为为为B B的的的的左左左左子子子子树树树树。(注注注注：图图图图中中中中结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子)，即左改组。，即左改组。，即左改组。，即左改组。左改组（新插入结点出现在危机结点的左子树上进行的左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：调整）的情况分析：1、LL情况：（情况：（LL：表示新插入结点在危机结点的左子表示新插入结点在危机结点的左子树的左子树上）树的左子树上）AB+1h-10+2+1hh-1h-1LL改组改组BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点改组前：高度为改组前：高度为h+1中序序列：中序序列：ABBLBRAR改组后：高度为改组后：高度为h+1中序序列：中序序列：ABBLBRAR注意：改组后注意：改组后平衡度为平衡度为0AB2 2、LRLR型的处理型的处理型的处理型的处理(左右型左右型左右型左右型)如如如如下下下下图图图图所所所所示示示示，在在在在A A的的的的左左左左孩孩孩孩子子子子B B上上上上插插插插入入入入一一一一个个个个右右右右孩孩孩孩子子子子C C，使使使使的的的的A A的的的的平平平平衡衡衡衡因因因因子子子子由由由由1 1变变变变成成成成了了了了2 2，成成成成为为为为不不不不平平平平衡衡衡衡的的的的二二二二叉叉叉叉排排排排序序序序树树树树。这这这这是是是是的的的的平平平平衡衡衡衡处处处处理理理理为为为为：将将将将C C变变变变到到到到B B与与与与AA之之之之间间间间，使使使使之之之之成成成成为为为为LLLL型型型型，然然然然后后后后按按按按第第第第(1)(1)种情形种情形种情形种情形LLLL型处理。此型处理。此型处理。此型处理。此LRLR型又存在下列三种情形：型又存在下列三种情形：型又存在下列三种情形：型又存在下列三种情形：左改组（新插入结点出现在危机结点的左子树上进行的调左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：整）的情况分析：2、LR情况：（情况：（LR：表示新插入结点在危机结点的左子树表示新插入结点在危机结点的左子树的右子树上）的右子树上）情形情形1：AB+1h-10+2-1h-1LR改组改组BLAR危机结点危机结点改组前：改组前：高度为高度为h+1中序序列：中序序列：注意：改组后注意：改组后平衡度为平衡度为0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改组后：改组后：高度为高度为h+1中序序列：中序序列：ABBLARCCLCRA左改组（新插入结点出现在危机结点的左子树上进行的调左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：整）的情况分析：2、LR情况：（情况：（LR：表示新插入结点在危机结点的左子树表示新插入结点在危机结点的左子树的右子树上）的右子树上）情形情形2：AB+1h-10+2-1h-1LR改组改组BLAR危机结点危机结点改组前：改组前：高度为高度为h+1中序序列：中序序列：注意：改组后注意：改组后平衡度为平衡度为+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACRh-1CLh-2+10ABBLARCCRCL改组后：改组后：高度为高度为h+1中序序列：中序序列：AABBLARCCRCL左改组（新插入结点出现在危机结点的左子树上进行的调左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：整）的情况分析：2、LR情况：（情况：（LR：表示新插入结点在危机结点的左子树表示新插入结点在危机结点的左子树的右子树上）的右子树上）情形情形3：AB+10+2-1LR改组改组危机结点危机结点改组前：改组前：高度为高度为2中序序列：中序序列：注意：改组后注意：改组后平衡度为平衡度为0,0,0CBC0ABCA新插入结点新插入结点ABC改组后：改组后：高度为高度为2中序序列：中序序列：CB0A00四种情况的区分：四种情况的区分：如果如果的平衡度为的平衡度为1则为则为LL型改组；型改组；否则为否则为LR型改组：若型改组：若的平衡度为的平衡度为1、1、0；则分别为；则分别为LRA、LRB、LRC型改组。型改组。BC3 3、RRRR型的处理型的处理型的处理型的处理(右右型右右型右右型右右型)如如如如图图图图下下下下所所所所示示示示，在在在在A A的的的的右右右右孩孩孩孩子子子子B B上上上上插插插插入入入入一一一一个个个个右右右右孩孩孩孩子子子子C C，使使使使A A的的的的平平平平衡衡衡衡因因因因子子子子由由由由-1-1变变变变成成成成-2-2，成成成成为为为为不不不不平平平平衡衡衡衡的的的的二二二二叉叉叉叉排排排排序序序序树树树树。这这这这时时时时的的的的平平平平衡衡衡衡处处处处理理理理为为为为：将将将将A A逆逆逆逆时时时时针针针针旋旋旋旋转转转转，成成成成为为为为B B的的的的左左左左子子子子树树树树，而而而而原原原原来来来来B B的的的的左左左左子树则变成子树则变成子树则变成子树则变成A A的右子树，待插入结点的右子树，待插入结点的右子树，待插入结点的右子树，待插入结点C C成为成为成为成为B B的右子树。的右子树。的右子树。的右子树。4 4、RLRL型的处理型的处理型的处理型的处理(右左型右左型右左型右左型)如如如如下下下下图图图图所所所所示示示示，在在在在A A的的的的右右右右孩孩孩孩子子子子B B上上上上插插插插入入入入一一一一个个个个左左左左孩孩孩孩子子子子C C，使使使使A A的的的的平平平平衡衡衡衡因因因因子子子子由由由由-1-1变变变变成成成成-2-2，成成成成为为为为不不不不平平平平衡衡衡衡的的的的二二二二叉叉叉叉排排排排序序序序树树树树。这这这这时时时时的的的的平平平平衡衡衡衡处处处处理理理理为为为为：将将将将C C变变变变到到到到A A与与与与B B之之之之间间间间，使使使使之之之之成成成成为为为为RRRR型型型型，然然然然后后后后按按按按第第第第3 3种种种种情形情形情形情形RRRR型处理。型处理。型处理。型处理。这里的右改组方法（新插入结点出现在危机结点的右子这里的右改组方法（新插入结点出现在危机结点的右子这里的右改组方法（新插入结点出现在危机结点的右子这里的右改组方法（新插入结点出现在危机结点的右子树上进行的调整）的情况分析：树上进行的调整）的情况分析：树上进行的调整）的情况分析：树上进行的调整）的情况分析：1 1、RRRR情况：（情况：（情况：（情况：（RRRR：表示新插入结点在危机结点的右子表示新插入结点在危机结点的右子表示新插入结点在危机结点的右子表示新插入结点在危机结点的右子树的右子树上）树的右子树上）树的右子树上）树的右子树上）处理图形和处理图形和处理图形和处理图形和 LLLL镜象相似镜象相似镜象相似镜象相似2 2、RLRL情况：（情况：（情况：（情况：（RLRL：表示新插入结点在危机结点的右子表示新插入结点在危机结点的右子表示新插入结点在危机结点的右子表示新插入结点在危机结点的右子树的左子树上）树的左子树上）树的左子树上）树的左子树上）1 1、处理图形和处理图形和处理图形和处理图形和 LRALRA镜象相似镜象相似镜象相似镜象相似 2 2、处理图形和处理图形和处理图形和处理图形和 LRBLRB镜象相似镜象相似镜象相似镜象相似3 3、处理图形和处理图形和处理图形和处理图形和 LRCLRC镜象相似镜象相似镜象相似镜象相似。例例例例2 2，给定一个关键字序列，给定一个关键字序列，给定一个关键字序列，给定一个关键字序列4,5,7,2,1,3,64,5,7,2,1,3,6，试生成一棵平衡二叉树。，试生成一棵平衡二叉树。，试生成一棵平衡二叉树。，试生成一棵平衡二叉树。分分分分析析析析：平平平平衡衡衡衡二二二二叉叉叉叉树树树树实实实实际际际际上上上上也也也也是是是是一一一一棵棵棵棵二二二二叉叉叉叉排排排排序序序序树树树树，故故故故可可可可以以以以按按按按建建建建立立立立二二二二叉叉叉叉排排排排序序序序树树树树的的的的思思思思想想想想建建建建立立立立，在在在在建建建建立立立立的的的的过过过过程程程程中中中中，若若若若遇遇遇遇到到到到不不不不平平平平衡衡衡衡，则则则则进进进进行行行行相相相相应应应应平平平平衡衡衡衡处处处处理理理理，最最最最后后后后就就就就可可可可以以以以建建建建成成成成一一一一棵棵棵棵平平平平衡衡衡衡二二二二叉叉叉叉树树树树。具具具具体体体体生成过程见下图。生成过程见下图。生成过程见下图。生成过程见下图。2 26 6平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析 平衡二叉树本身就是一棵二叉排序树，故它的查找与二平衡二叉树本身就是一棵二叉排序树，故它的查找与二平衡二叉树本身就是一棵二叉排序树，故它的查找与二平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找叉排序树完全相同。但它的查找叉排序树完全相同。但它的查找叉排序树完全相同。但它的查找 性能优于二叉排序树，不像性能优于二叉排序树，不像性能优于二叉排序树，不像性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度二叉排序树一样，会出现最坏的时间复杂度二叉排序树一样，会出现最坏的时间复杂度二叉排序树一样，会出现最坏的时间复杂度O(n)O(n)，它的时间它的时间它的时间它的时间复杂度与二叉排序树的最好时间复杂相同，都为复杂度与二叉排序树的最好时间复杂相同，都为复杂度与二叉排序树的最好时间复杂相同，都为复杂度与二叉排序树的最好时间复杂相同，都为O(logO(log2 2n)n)。例例例例3 3对对对对例例例例2 2给给给给定定定定的的的的关关关关键键键键字字字字序序序序列列列列4,5,7,2,1,3,64,5,7,2,1,3,6，试试试试用用用用二二二二叉叉叉叉排排排排序序序序树树树树和和和和平平平平衡衡衡衡二二二二叉叉叉叉树树树树两两两两种种种种方方方方法法法法查查查查找找找找，给给给给出出出出查查查查找找找找6 6的的的的次次次次数数数数及及及及成成成成功功功功的的的的平平平平均查找长度。均查找长度。均查找长度。均查找长度。分析：由于关键字序列的顺序己经确定，故得到的二叉排分析：由于关键字序列的顺序己经确定，故得到的二叉排分析：由于关键字序列的顺序己经确定，故得到的二叉排分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的序树和平衡二叉树都是唯一的序树和平衡二叉树都是唯一的序树和平衡二叉树都是唯一的,得到的平衡二叉树见上图，得得到的平衡二叉树见上图，得得到的平衡二叉树见上图，得得到的平衡二叉树见上图，得到的二叉排序树见下图。到的二叉排序树见下图。到的二叉排序树见下图。到的二叉排序树见下图。从从从从上上上上图图图图的的的的二二二二叉叉叉叉排排排排序序序序树树树树可可可可知知知知，查查查查找找找找6 6需需需需4 4次次次次，平平平平均均均均查查查查找找找找长长长长度度度度ASL=(1+2+2+3+3+3+4)/7=18/72.57ASL=(1+2+2+3+3+3+4)/7=18/72.57。从图从图从图从图8-148-14的平衡二叉树可知，查找的平衡二叉树可知，查找的平衡二叉树可知，查找的平衡二叉树可知，查找6 6需需需需2 2次，平均查找长度次，平均查找长度次，平均查找长度次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。从结果可知，平衡二叉树的查找性能优于二叉排序树。从结果可知，平衡二叉树的查找性能优于二叉排序树。从结果可知，平衡二叉树的查找性能优于二叉排序树。1、为什么采用、为什么采用B_树和树和B+树：树：大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次内存。因此，要多次访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。主要矛盾变为减少访外次数。在在1970年由年由Rbayer和和Emacreight提出用提出用B_树作为索引组织文件。提高访树作为索引组织文件。提高访问速度、减少时间。问速度、减少时间。内存内存E.G:用二叉树组织文件，当文件的记录个数为用二叉树组织文件，当文件的记录个数为100，000时，要找到给定关键字的记录，需访时，要找到给定关键字的记录，需访问外存问外存17次（次（log100,000）,太长了！太长了！502510751535609020304055708095索索引引文文件件数数据据文文件件文件头，可常驻内存文件头，可常驻内存文件访问示意图：索引文件、数据文件存在盘上文件访问示意图：索引文件、数据文件存在盘上8.2.2B_树和树和B+树树2、B_树是一种多分支数，首先介绍树是一种多分支数，首先介绍m阶阶B_树：树：定义：定义：m阶阶B_树满足或空，或：树满足或空，或：A、根结点要么是叶子，要么至少有两个儿子根结点要么是叶子，要么至少有两个儿子B、除根结点和叶子结点之外，每个结点的儿子个数为除根结点和叶子结点之外，每个结点的儿子个数为:m/2=s=mC、有有s个儿子的非叶结点具有个儿子的非叶结点具有n=s1个关键字，即个关键字，即:s=n+1这些结点的数据信息为：这些结点的数据信息为：（n,A0,K1,R1,A1,K2,R2,A2,Kn,Rn,An）这里：这里：n:关键字的个数关键字的个数A0：K1且且Kn的结点的地址（指在该的结点的地址（指在该B_树中）树中）注意：注意：K1=K2=.=KnD、所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。例如：例如：m=4阶阶B_树。树。除根结点和叶子结点之外，每个除根结点和叶子结点之外，每个结点的儿子个数结点的儿子个数至少为至少为m/2=2个；结点的关键字个数至少为个；结点的关键字个数至少为1。该该B_树的深度为树的深度为4。叶子结点都在第叶子结点都在第4层上。层上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第第1层层第第2层层第第3层层(L层层)第第4层层(L1层层)3、B_树的查找代价分析：树的查找代价分析：查找过程，类似于二叉树的查找。如查找关键字为查找过程，类似于二叉树的查找。如查找关键字为KEY的记录。的记录。从根开始查找，如果从根开始查找，如果Ki=KEY则查找成功，则查找成功，Ri为关键字为为关键字为KEY的记录的地址。的记录的地址。若若KiKEYKi+1;查找查找Ai指向的结点指向的结点若若KEYKn;查找查找An指向的结点指向的结点若若找到叶子，则查找失败。找到叶子，则查找失败。注意：每次查找将去掉注意：每次查找将去掉（s-1）/s个分支，比二分查找快得多。个分支，比二分查找快得多。设关键字的总数为设关键字的总数为N，求求m阶阶B_树的最大层次树的最大层次L。层次层次结点数结点数关键字的个数（最少）关键字的个数（最少）111222（m/2-1）32（m/2）2（m/2）（m/2-1）42（m/2）22（m/2）2（m/2-1）L2（m/2）L-22（m/2）L-2（m/2-1）L+12（m/2）L-1所以，所以，N=12（m/2-1）+.+2（m/2）L-2（m/2-1）=2m/2L-1-1故：故：Llog（N+1）/2）+13、B_树的查找代价分析：树的查找代价分析：设关键字的总数为设关键字的总数为N，求求m阶阶B_树的最大层次树的最大层次L。故：故：Llogm/2（N+1）/2）+1设设N1000，000且且m256，则则Lm-1,则该结点满。必须分裂成两个结点。否则不满结束。则该结点满。必须分裂成两个结点。否则不满结束。如结点原为：如结点原为：（m-1,A0,(K1,A1),(K2,A2),(Km-1,Am-1)）插入一个关键字之后变为：插入一个关键字之后变为：（m,A0,(K1,A1),(K2,A2),(Km,Am)）该结点将进行分裂：该结点将进行分裂：.(Km/2,p).（m/2-1,A0,(K1,A1),(Km/2,Am/2)）（m-m/2,Am/2,(Km,Am)）生成新结点生成新结点p,将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。PPP P(KKm/2m/2,p,p)数据数据数据数据项插入上层结点之项插入上层结点之项插入上层结点之项插入上层结点之中中中中B-B-树的插入方法树的插入方法树的插入方法树的插入方法 设要插入关键值为设要插入关键值为设要插入关键值为设要插入关键值为k k的记录，指向的记录，指向的记录，指向的记录，指向k k所在记录的指针为所在记录的指针为所在记录的指针为所在记录的指针为p p。首首首首先先先先找找找找到到到到k k应应应应插插插插入入入入的的的的叶叶叶叶子子子子结结结结点点点点，将将将将 k k和和和和p p插插插插入入入入。然然然然后后后后，判判判判断断断断被被被被插插插插入入入入结结结结点点点点是是是是否否否否满满满满足足足足mm叉叉叉叉B-B-树树树树的的的的定定定定义义义义，即即即即插插插插入入入入后后后后结结结结点点点点的的的的分分分分支支支支数数数数是是是是否否否否大大大大于于于于mm（结结结结点点点点的的的的关关关关键键键键字字字字数数数数是是是是否否否否大大大大于于于于m-1)m-1)，若若若若不不不不大大大大于于于于，则则则则插插插插入结束；否则，要把该结点分裂成两个。方法是：入结束；否则，要把该结点分裂成两个。方法是：入结束；否则，要把该结点分裂成两个。方法是：入结束；否则，要把该结点分裂成两个。方法是：申申申申请请请请一一一一个个个个新新新新结结结结点点点点，由由由由指指指指针针针针pp指指指指向向向向，将将将将插插插插入入入入后后后后的的的的结结结结点点点点按按按按照照照照关关关关键键键键字字字字的的的的值值值值大大大大小小小小分分分分成成成成左左左左、中中中中、右右右右三三三三部部部部分分分分，中中中中间间间间只只只只含含含含一一一一项项项项，左左左左边边边边的的的的留留留留在在在在原原原原结结结结点点点点，右右右右边边边边的的的的移移移移入入入入新新新新结结结结点点点点，中中中中间间间间的的的的构构构构成成成成新新新新的的的的插插插插入入入入项项项项，插插插插入入入入到到到到它它它它们们们们的的的的双双双双亲亲亲亲结结结结点点点点中中中中，若若若若双双双双亲亲亲亲结结结结点点点点在在在在插插插插入入入入后后后后也也也也要要要要分分分分裂裂裂裂，则则则则在在在在分分分分裂后再往上插入。裂后再往上插入。裂后再往上插入。裂后再往上插入。例如：例如：3阶阶B_树的插入操作。树的插入操作。m=3,m/2-1=1;至少至少1个关键字，二个儿子结点。个关键字，二个儿子结点。3，127243024，3045，7053902610039506185345，70539026100395061851230324457053902610039506185127303245390261003950618512745707插入插入5、B_树的删除操作树的删除操作1、查找具有给定键值的关键字、查找具有给定键值的关键字Ki2、如果如果在在第第L层，可直接删除（注意：第层，可直接删除（注意：第L+1层为叶子结点），转层为叶子结点），转4。3、否则，则首先生成、否则，则首先生成“替身替身”。用。用的右子树中的最左面的结点的关键字值，即的右子树中的最左面的结点的关键字值，即处于第处于第L层上的最层上的最小小关键字值取代关键字值取代。然后，删除第。然后，删除第L层上的该关键字。层上的该关键字。4、从第、从第L层开始进行删除。层开始进行删除。A、不动：若删除关键字值的那个结点的关键字的个数仍处于不动：若删除关键字值的那个结点的关键字的个数仍处于m/2-1和和m-1之间。则结束。之间。则结束。B、借：若删除关键字值的那个结点的关键字的个数原为借：若删除关键字值的那个结点的关键字的个数原为m/2-1。而它们的左或右邻居结而它们的左或右邻居结点的关键字的个数点的关键字的个数m/2-1;则借一个关键字过来。处理结束。则借一个关键字过来。处理结束。C、并：若该结点的左或右邻居结点的关键字的个数为并：若该结点的左或右邻居结点的关键字的个数为m/2-1;则执行合并结点的操作。则执行合并结点的操作。如结点原为：如结点原为：（.(Ki,Ai),(Ki+1,Ai+1),.）（A0,(K1,A1)）（A0,(K1,A1)）K1L第第第第 LL层：找到了被删结点的替身。层：找到了被删结点的替身。层：找到了被删结点的替身。层：找到了被删结点的替身。例如：例如：3阶阶B_树的删除操作。树的删除操作。m=3,m/2-1=1;至少至少1个关键字，二个儿子结点。个关键字，二个儿子结点。324455390371005061，70被删关键字被删关键字324456190371005370借：向被删结点方向旋转借：向被删结点方向旋转假定再删除该关键字假定再删除该关键字32445903710061，70假定再删除该关键字假定再删除该关键字3，24459010061，703，24459010061，70并并并并并并并：和父结点的一个关键字、及邻居合并。有可并：和父结点的一个关键字、及邻居合并。有可能进行到根，使能进行到根，使B_树的深度降低一层！树的深度降低一层！3 散列查找n由由于于前前两两种种查查找找方方法法中中，记记录录在在结结构构中中的的相相对对位位置置是是随随机机的的，和和其其关关键键码码值值之之间间没没有有直直接接的的联联系系，因因此此在在进进行行检检索索时时，必必须须采采用用“比比较较”手手段段来来实实现现，显显然然，查查找的效率依赖于检索过程中进行比较的次数。找的效率依赖于检索过程中进行比较的次数。n于于是是，理理想想的的查查找找是是不不经经过过任任何何比比较较或或少少经经过过比比较较就就能能够够得得到到所所查查找找的的元元素素，则则必必须须在在记记录录与与其其关关键键字字值值之之间间建建立立一一个个确确定定的的对对应应关关系系h，使使得得每每个个关关键键字字和和结结构构中中的的一一个个唯唯一一的的存存储储位位置置相相对对应应，这这样样在在检检索索时时，找找到到给给定定值值K的的影影象象H（K），若若记记录录中中存存在在关关键键码码和和k相相等等的的记记录录，则则必必然然存存储储在在h(k)的的存存储储位位置置上上，因因此此不不需需要要进进行行比比较较即即可可直直接接得得到到所所查查找找的的记记录录。通通常常称称这这个个对对应应关关系系h为为散散列列函函数数，采采用用该该散散列列函函数数所所建建立立的的表表称称为为散列表。散列表。3 散列查找n实践表明实践表明实践表明实践表明：n n （1 1）如如如如果果果果散散散散列列列列表表表表是是是是一一一一一一一一对对对对应应应应的的的的函函函函数数数数，则则则则根根根根据据据据散散散散列列列列函函函函数数数数对对对对给给给给定定定定的的的的值值值值进进进进行行行行某某某某种种种种运运运运算算算算，即即即即可可可可得得得得到到到到待待待待查查查查找找找找元元元元素素素素的的的的位位位位置；置；置；置；n n（2 2）散列表占用的空间可能比结点空间多；）散列表占用的空间可能比结点空间多；）散列表占用的空间可能比结点空间多；）散列表占用的空间可能比结点空间多；n n （3 3）散散散散列列列列函函函函数数数数的的的的构构构构造造造造原原原原则则则则：运运运运算算算算尽尽尽尽量量量量简简简简单单单单，而而而而且且且且所所所所占用空间均匀分布；占用空间均匀分布；占用空间均匀分布；占用空间均匀分布；n n （4 4）不不不不同同同同的的的的关关关关键键键键字字字字值值值值可可可可能能能能得得得得到到到到相相相相同同同同的的的的函函函函数数数数值值值值，即即即即可可可可能有冲突产生能有冲突产生能有冲