Ch.9查找 §9.2线性表的查找 59.1基本抵志 查找和掉序是两个量要的运算 ●对像，用战性囊作为表的组织形式。 蓝差森登气紧被的岛，〈记录)由多个数排项构成。服设每个 ●分类：静态查找、内部查找 年方式：顺序查找、二分查找、分块查找 蜜款珍产装备的婆老鞋奖莽于曾气生金类 败)，题回相关指示省意。 #define n 100// ■分类： ◆查找过耀中是香修政衰？动态查找、静志查找 59.21顺序查找 ◆查线过鞭是香热在内存中进行？内部查找、外部查找 ·基本思短 。效事：与存储结构、文件状态（有序、无序）有关 平均查找长建(ASL山，即平均的比较次数，作为衡量查找效率的标准 灭美挂老，男营曾 冕指未站，实服 AS=∑PC,C童拉第个销点的比敏次照 P:壹找第个结点的颜率 ■适用范园：原序表、链衰 ■算法： 设P,=1/n,1≤i运n 的定typedef int KeyType: §9.2.1顺序查找 §9.2.1顺序查找 typedef struct{ ■哨兵的作用 KeyType key: InfoType otherinfo;l应用相关 fo中省略了下标越界>=1判定，节约了约一半时间 )NodeType,,SeqList[n+1：小0号单元作为晴兵 量时间分析 int SeqSearch(SeqList R,KeyType K){ 成功：ASL=(n+1)/2,k©y的平均比较次数约为表长的一半 在R风1可中壹找，成功时运回结点位里，失敢时远回0 失败：叶1次比较 intn; ■优缺点 R0]key=K:I设里喇兵 for(nR们key=K;i-片从后往前找 优点：简单，对存情结构、Ky之间的关系均无特殊要求 return士嗜为0，则失敢 缺点：效率低，当n较大时不宜用 §9.2.2二分（折半）查找 §922二分（折半）查找 ■算法： ■适用范园：顺序表、有序 int BinSearch(SeqList R,KeyType K){ 基本思想（分治法） int mid,low=1,high=n; (1)设Row.high)是当前查找区间，首先确定该区间的中点 while(IowR[mid],key:剩右子表Rmid+1.high是新的查找区间 else low=mid+1:1l在右区间中查找 初始的查找区间是R[1.n可，每次查找比较K和中间点元囊， }∥endwhile 若查找成功则返回：否则当前查我区间缩小一半，直至当前查找 区间为空时查找失败。 return0;∥当前查找区间为空时失败 1
1 1 Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算 对象：表、文件等。其中每个结点（记录）由多个数据项构成，假设每个 结点有1个能唯一标识该结点的key。 定义：给定1个值K，在含有n个结点的表中找出关键字等于K的结点，若找 到（查找成功），则返回该结点信息或它在表中的位置；否则（查找失 败），返回相关指示信息。 分类： 查找过程中是否修改表？动态查找、静态查找 查找过程是否均在内存中进行？内部查找、外部查找 效率：与存储结构、文件状态（有序、无序）有关 平均查找长度(ASL)，即平均的比较次数，作为衡量查找效率的标准： Pi ：查找第i个结点的概率 Ci ：查找第i个结点的比较次数 设Pi ＝1/n, 1≤i≤n 约定：typedef int KeyType; ∑ = = n i ASL Pi Ci 1 2 § 9.2 线性表的查找 对象：用线性表作为表的组织形式。 分类：静态查找、内部查找 方式：顺序查找、二分查找、分块查找 ＃define n 100// §9.2.1 顺序查找 基本思想 从表的一端开始，顺序扫描线性表，依次将扫描到的结点的Key与给 定值K进行比较，若当前扫描到结点Key＝K，则查找成功返回；若扫描 完整个表后，仍未找到，则查找失败。 适用范围：顺序表、链表 算法： 3 §9.2.1 顺序查找 typedef struct{ KeyType key; InfoType otherinfo; //应用相关 }NodeType, SeqList[n+1]; //0号单元作为哨兵 int SeqSearch( SeqList R, KeyType K) { //在R[1..n]中查找，成功时返回结点位置，失败时返回0 int n; R[0].key=K; //设置哨兵 for ( i=n; R[i].key != K; i-- ); //从后往前找 return i; //若i为0，则失败 } 4 §9.2.1 顺序查找 哨兵的作用 for中省略了下标越界i>=1判定,节约了约一半时间 时间分析 成功：ASLss=(n+1)/2，key的平均比较次数约为表长的一半 失败：n+1次比较 优缺点 优点：简单，对存储结构、Key之间的关系均无特殊要求 缺点：效率低，当n较大时不宜用 5 § 9.2.2 二分（折半）查找 适用范围：顺序表、有序 基本思想（分治法） （1）设R[low..high] 是当前查找区间，首先确定该区间的中点 位置：mid= (low+high)/2 //整除 （2）将待查的K值与R[mid]比较， ① K＝R[mid].key：查找成功，返回位置mid ② K＜R[mid].key：则左子表R[low..mid-1]是新的查找区间 ③ K＞R[mid],key：则右子表R[mid+1..high]是新的查找区间 初始的查找区间是R[1..n]，每次查找比较K和中间点元素， 若查找成功则返回；否则当前查找区间缩小一半，直至当前查找 区间为空时查找失败。 6 § 9.2.2 二分（折半）查找 算法： int BinSearch( SeqList R, KeyType K ) { int mid, low=1, high=n; while ( low < high ) { //当前查找区间R[low..high]非空 mid= (low+high)/2； //整除 if ( R[mid].key==K ）return mid; //成功返回位置mid if ( K＜R[mid].key ) //两个子问题求解其中的一个 high=mid-1; //在左区间中查找 else low=mid+1；//在右区间中查找 } // endwhile return 0; //当前查找区间为空时失败 }
§9.2.2三分（折半）查找 §92.2二分（折半）查找 费终满的置紫%公新拉提的三骨路密孕第素数湘关， 与 ·时间分析 〔06品2品.品品2)，批2康纳，执85庆藏 ◆查找R同：比较1次；意望R3、R:比较2次；意找RR国、R闪 I0j:比较3次：童找R☒，R、R8图、R1:比较4次 R1 ○内部结点 R[1..5 6 11 外部结点 R111 R[1.516 R7.11 3 9 45 7) 10.11] 31 9 12 45 R78剧 人101 4 7 10 R22 5.51 88周 R1111 1 4 7 10 422 R5.5 Rs8 R11-1 1 234567891011 2345678901 d/ 12234556788910111正 12234约567889105f1市 89.2.2三分（折半）查找 §9.2.2分块查找（索引顺序查找） 时间分折 ■存，结构 ◆总销：查找过程走了一条从判定封的根到放查轴点的路径。 感动：峰止于一个内督结点，所需的Ky比较次数恰为该结点在树中的层 将R[1nj均分成b块，前b一1块中的点数为5=nWb,量后一块中的的 点数可能小于5，引入素引康标记块。 表整货于)十外都铺点。所需的K©y比较次数为演上内部施点总 ■关键字状态 ◆平均童数长度(A3L), 分染有序：块间有序，块内不一定有序 侧子：n=18,b=3,s=6 设n=2-1,则制高h=g(n+1)不计外部结点的满二叉树 第k展上纳点数为2水一，找该层上每个轴点的比较次数为k,在等餐事限 设下， 最大关镜宇 224886 起始地址 7 13 4-20,-2c-之2="出ga+n-1sle+-l n 参量坏时间，意线失败，不超过树高g(+1 在链表上可做折半查找网？ 2212389203324382448505874498653 §9.2.2分块查找（索引顺序查找） §9.3树上的查找（动态查找） 查找过程（两步查找） 于新学艺效导世。本节计论适用 ◆家引豪意线：南定块。n较大时用折半查找，较小时用顺序查找， 女柴内意线：只能原序查找。 59.3.1二叉查找树(BST) ·性能分析 ■定义：二叉查找制树成是空树，或满足下述B$T性质的二叉树： ◆以新半查载南定染 ①惹它的左子树非空，则左子树上所有结点的k©ys均小于根 ASL=ASLm+ASL=Ig(b+1)-1+(s+12lg(n/s+1)+s/2 的key ②装它的右子树非空，则右子制上所有结点的k©ys均大于根 ◆以顺序查找确定禁 的key ASL=ASL+ASL=(b+12+(s+1)/2=(s2+2s+n/(2s) 图左右子树又都是二叉查找树 当s=,万时，ASL取银小值√n+1 Note:性质1或2中，可以将“”改为“≥州 不一定等分 BST性质 二叉查找树的中序序列是一个递增有序序列 2
2 7 § 9.2.2 二分（折半）查找 查找过程 判定(比较)树：分析查找过程的二叉树，形态只与结点数相关，与 输入实例的取值无关（为什么？）。例如n＝11的形态如下图所示。 1 2 3 4 5 6 7 8 9 10 11 （05,13,19,21,37,56,64,75,80, 88, 92），找21成功，找85失败。 6 R[1..11] 1 9 4 3 7 10 2 R[1..5] R[7..11] R[10..11] Φ R[5..5] R[11..11] -1 1-2 2-3 4-5 3-4 R[1..2] R[2..2] Φ 5 8 R[4..5] Φ Φ Φ 5-6 6-7 7-8 Φ Φ Φ 11 R[7..8] Φ R[8..8] 8-9 9-10 Φ Φ 10-11 11- Φ ＜ ＝ ＞ 内部结点 外部结点 8 § 9.2.2 二分（折半）查找 时间分析 查找R[6]：比较1次; 查找R[3]、R{9]：比较2次; 查找R[1]、R[4]、R[7]、 R[10]：比较3次; 查找R[2]、R[5]、R[8]、R[11]：比较4次 6 R[1..11] 1 9 4 3 7 10 2 R[1..5] R[7..11] R[10..11] Φ R[5..5] R[11..11] -1 1-2 2-3 4-5 3-4 R[1..2] R[2..2] Φ 5 8 R[4..5] Φ Φ Φ 5-6 6-7 7-8 Φ Φ Φ 11 R[7..8] Φ R[8..8] 8-9 9-10 Φ Φ 10-11 11- Φ ＜ ＝ ＞ 9 § 9.2.2 二分（折半）查找 时间分析 总结：查找过程走了一条从判定树的根到被查结点的路径。 成功：终止于一个内部结点，所需的Key比较次数恰为该结点在树中的层 数; 失败：终止于一个外部结点，所需的Key比较次数为该路径上内部结点总 数。（层数－1） 平均查找长度（ASL）： 设n＝2h-1, 则树高h＝lg(n+1) //不计外部结点的满二叉树 第k层上结点数为2k－1，找该层上每个结点的比较次数为k，在等概率假 设下： 最坏时间：查找失败，不超过树高 lg(n+1) 在链表上可做折半查找吗？ ∑ ∑∑ = == − + − ≈ + − + = = = = n i n i h k k bs i i i n n n n k n C n ASL PC 1 11 1 lg( 1) 1 lg( 1) 1 1 2 1 1 10 § 9.2.2 分块查找（索引顺序查找） 存储结构 将R[1..n]均分成b块，前b－1块中结点数为s＝ n/b ，最后一块中的结 点数可能小于s，引入索引表标记块。 关键字状态 分块有序：块间有序，块内不一定有序; 例子：n＝18，b＝3，s＝6 1 7 13 最大关键字 22 48 86 起始地址 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 11 § 9.2.2 分块查找（索引顺序查找） 查找过程（两步查找） 索引表查找：确定块。n较大时用折半查找，n较小时用顺序查找。 块内查找：只能顺序查找。 性能分析 以折半查找确定块： ASL＝ ASLbs＋ASLss＝lg(b＋1) －1＋(s＋1)/2≈lg(n/s＋1)＋s/2 以顺序查找确定块： ASL＝ ASLss＋ASLss＝(b＋1)/2＋(s＋1)/2＝(s2＋2s＋n)/(2s) 当s＝ 时，ASL取极小值 ＋1 块不一定等分 n n 12 § 9.3 树上的查找（动态查找） 折半查找效率最高，但它不适应插删操作。本节讨论适用 于动态查找，即查找过程中动态维护表结构。 § 9.3.1 二叉查找树（BST） 定义：二叉查找树或是空树，或满足下述BST性质的二叉树： ①若它的左子树非空，则左子树上所有结点的keys均小于根 的key ②若它的右子树非空，则右子树上所有结点的keys均大于根 的key ③左右子树又都是二叉查找树 Note：性质1或2中，可以将“﹤” 改为“≤”；或“﹥”改为“≥” BST性质 二叉查找树的中序序列是一个递增有序序列
S9.3.1二叉查找树(BST) S9.3.1二叉查找树(BST) 5, ·举例 ⑤ 1.查找 ② ⑦ :都本思想 处督德商开的喜生肉牌棉控把冲技我 功，返回该点的指 查结点，则失数宇某个空指针上。 ■存储结构： ■算法 typedef struct node BSTNode*SearchBST(BSTree T,KeyType key K 在T上查找k@y=K的节点，成功时逗回该节点，否刚远回NULL KeyType key; if (T==NULLI key=T-key)return TT为空，意找失香刚功 InfoType otherinfo if(kaykay】 return SearchBST(T->ichild,key方童找左子侧 struct node"lchild,"rchild; else }BSTNode,'BSTree; return SearchBST(T->rchild,.kay片责找右子铜 S93.1二叉查找树(BST) ⑤ 2、BST的插入和生成 ③ T 1.查找 ■插入 ② ④ ⑨ ■时间 ◆算法思想保正新结点插入后满足BST性质，基本思想如 下， 若成功，则走了一条从根到待查节点的路径 若T为空，则为特播入的Ky申请一个新结点，并令其为 若失败，则走了一条从根到叶子的路径？（不一定） 报： ◆上界：O(h) ,否则，从根开始向下查找插入位置，直到发现树中已有 K©y,或找到=个空指针为止： ◆分析：与树高相关 ①最坏情况：单支树，S=(+1)/2,与顺序查找相同 ,将新结点作为叶子插入空指针的位量。 查找过程是一个关输字的比较过程，易于写出递归或非递 ②最好情况：ASL≈gm,形态与折半查找的判定制相似 归算法，也可以调用查找操作。 ®平均情况：假定n个koys所形成的nl种排列是等摄率的， 则可正明由这n!个序列产生的n!棵sT(其中有的形态相 同)的平均高度为O(1gn),故查找时间仍为O(1gn ◆算法实现 2、BST的插入和生成 2、BST的插入和生成 void InsertBST(BSTree*T,KeyType key){rT是根 ■生成 BSTNode*f,“p=T;p指向粮结点 while(p)(∥当时排空时，查找报入位夏 ◆算法：从空树开始，每输入一个数据蚊调用一次插入算法， 许(p->kay=kay)retur;树中已有key,不允许置复须入 BSTree CreateBST(void ) f=p!∥和p为父子关暴 BSTree T=NULL;物始时r为空 p=(key key )p->lchild;p>rchild; KeyType key; }加注意：制为空时，无须童找 scanf("%d",&key ) p=(BSTNode*)malloc(sizeof(BSTNode)); whie(key)(餐设key=0豪示输入结家 p->kay=key;p->lchild=p>rchild=NULL;性减新罐点 InsertBST(&T,key):将key擂入树T中 计(T=NUL儿L)·T=p;原树为空新储点为根 scanf(“%d”,&key ):I婆入下一个关输字 es白川原制排空，新神点作为的左或右孩子霜入 } if key key f->lchild=p; return T:∥返回餐物针 else f->rchild=p; )时同为0() 3
3 13 § 9.3.1 二叉查找树（BST） 举例 存储结构： typedef struct node { KeyType key; InfoType otherinfo; struct node *lchild, *rchild; } BSTNode, *BSTree; 5 3 7 2 4 9 14 § 9.3.1 二叉查找树（BST） 1.查找 基本思想 从根结点开始比较，若当前结点的key与待查的key相等，则查找成 功，返回该结点的指针；否则在左子树或右子树中继续查找。若树中没有待 查结点，则失败于某个空指针上。 算法 BSTNode *SearchBST( BSTree T, KeyType key ){ //在T上查找key=K的节点，成功时返回该节点，否则返回NULL if ( T==NULL || key==T->key ) return T; //若T为空，查找失败；否则成功 if ( key key ) return SearchBST ( T->lchild, key ); //查找左子树 else return SearchBST ( T->rchild, key ); //查找右子树 } 5 3 7 2 4 9 15 § 9.3.1 二叉查找树（BST） 1.查找 时间 若成功，则走了一条从根到待查节点的路径 若失败，则走了一条从根到叶子的路径？（不一定） 上界：O(h) 分析：与树高相关 ①最坏情况：单支树，ASL=(n+1)/2,与顺序查找相同 ②最好情况：ASL≈lgn，形态与折半查找的判定树相似 ③平均情况：假定n个keys所形成的n!种排列是等概率的， 则可证明由这n!个序列产生的n!棵BST（其中有的形态相 同）的平均高度为O(lgn)，故查找时间仍为O(lgn) 5 3 7 2 4 9 16 2、BST的插入和生成 插入 算法思想 保证新结点插入后满足BST性质，基本思想如 下： ¾若T为空，则为待插入的Key申请一个新结点，并令其为 根； ¾否则，从根开始向下查找插入位置，直到发现树中已有 Key，或找到一个空指针为止； ¾将新结点作为叶子插入空指针的位置。 查找过程是一个关键字的比较过程，易于写出递归或非递 归算法，也可以调用查找操作。 算法实现 17 2、BST的插入和生成 void InsertBST( BSTree *T, KeyType key ) { //*T是根 BSTNode *f, *p=*T; //p指向根结点 while( p ) { //当树非空时，查找插入位置 if ( p->key==key ) return; //树中已有key，不允许重复插入 f＝p；// f和p为父子关系 p＝( key key ) ? p->lchild; p->rchild; } //注意：树为空时，无须查找 p = (BSTNode *) malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; //生成新结点 if ( *T ==NULL ) * T=p; //原树为空,新结点为根 else //原树非空, 新结点作为*f的左或右孩子插入 if ( key key ) f->lchild=p; else f->rchild=p; } //时间为O（h） 18 2、BST的插入和生成 生成 算法： 从空树开始，每输入一个数据就调用一次插入算法。 BSTree CreateBST( void ) { BSTree T＝NULL; //初始时T为空 KeyType key; scanf( “%d”, &key ); while( key ) { //假设key＝0表示输入结束 InsertBST ( &T, key ) ; //将key插入树T中 scanf( “%d”, &key )；// 读入下一个关键字 } return T；// 返回根指针 }
2、BST的插入和生成 2、BST的插入和生成 ■举例 量一般情况 轴入实例10,18,3,8,12,2,7,3到 不同的输入实例（数据集不同、或排列不同），生成的 树的形态一般不同。对n个结点的同一数据集，可生成n!棵 BST. ⑧ ■例外情况 但有时不同的实例可能生成相同的BST,例如：（2,3， 7,8,5,4)和(2,3,7,5,8,4)可构造同一棵BST。 ⑧ ⑧② ⑧ ■排序树名称的由来 因为B$T的中序序列有序，所以对任意关键字序列，构造 BST的过程，实际上是对其排序。 生成n个结点的BST的平均时间是O(nlgn,但它约为堆排 序的2一3倍，因此它并不适合排序。 3、 BST的删除 3、BST的副除 保证测一结点不能将以该结点为根的子制侧去，且仍须满足ST性质，即： ■基本思想 一结点相当于有序序列中的一个结点。 c3:*p有2个孩子，有2种处理方式： 基本思短 ①找到*p的中序后健或前驱，用*p的右或左)子树取代*p与其双亲 音垫碧资学之me清肉关限秦（彻值U),著找不到侧通 连接： 左或右)子则作为的左或右)子树与连 在测障*p时处理其子树的连接问■，同时保持BST性质不变。 parent case产p是叶子，无须连接子树，只需将*parent中指向产p的指针置空 parent cse2:*p只有1个孩子，只须连获障一的1裸子制，放可令此孩子取代*p与 其双亲连接（种状态） /PL\/SR 只有左孩子 p风南右被子 3、BST的副除 3、BST的酬除 ■基本思想 ②中q听p:找*q的中序后望p,并变parent指向*p的双来，将p的右子制取代 ■算法 与其双亲*parenti挂接，将产p的内客copy到*q中，相当于副去了*q:将*q的 作转换为的媒作，对称地，也可找*的中序前驱 void DelBSTNode(BSTree "T,KeyType key))(rT是根 BSTree'q,*child,"parent=NULL,*p=*T; while(p)(找特结点 if(p->key=key)break;∥已找到 parent=p;川循环不变式是parent为rp的双亲 p=(key p->key )p->Ichild;p->rchild; if(p)return;1找不到被结点，返回 “q的中序后撞城是其右孩于 qp;g记住被结点p if(q->lchild&&q->rchild)//case3,找*q的中序后罐 for(parent=qpq->rchild:p->lchild;parent-p,pp->lchild); 4
4 19 2、BST的插入和生成 举例 10 10 18 10 3 18 10 3 18 8 10 3 18 8 12 10 3 18 2 8 12 10 3 18 2 8 12 7 10 3 18 2 8 12 7 3 输入实例 {10， 18， 3， 8， 12， 2， 7， 3} 20 2、BST的插入和生成 一般情况 不同的输入实例（数据集不同、或排列不同），生成的 树的形态一般不同。对n个结点的同一数据集，可生成n！棵 BST。 例外情况 但有时不同的实例可能生成相同的BST，例如：（2，3， 7，8，5，4）和（2，3，7，5，8，4）可构造同一棵BST。 排序树名称的由来 因为BST的中序序列有序，所以对任意关键字序列，构造 BST的过程，实际上是对其排序。 生成n个结点的BST的平均时间是O(nlgn), 但它约为堆排 序的2－3倍，因此它并不适合排序。 21 3、BST的删除 保证删一结点不能将以该结点为根的子树删去，且仍须满足BST性质。即： 删一结点相当于删有序序列中的一个结点。 基本思想 查找待删结点*p，令parent指向其双亲（初值NULL）；若找不到则返 回，否则进入下一步。 在删除*p时处理其子树的连接问题，同时保持BST性质不变。 case1:*p是叶子，无须连接子树，只需将*parent中指向*p的指针置空 case2:*p只有1个孩子，只须连接唯一的1棵子树，故可令此孩子取代*p与 其双亲连接（4种状态） parent p child child parent p parent p child parent p child *p只有左孩子 *p只有右孩子 22 3、BST的删除 基本思想 case3: *p有2个孩子，有2种处理方式： ①找到*p 的中序后继(或前驱)*s，用*p的右(或左)子树取代*p与其双亲 *parent连接；而*p的左(或右)子树PL则作为*s的左(或右)子树与*s连 接。缺点：树高可能增大。 PL sR s pr parent PL sR p parent s pr 23 3、BST的删除 基本思想 ②令q=p，找*q的中序后继*p，并令parent指向*p的双亲，将*p的右子树取代*p 与其双亲*parent连接。将*p的内容copy到*q中，相当于删去了*q，将删*q的 操作转换为删*p的操作。对称地，也可找*q的中序前驱 因为*p最多只有1棵非空的子树，属于case2。实际上case1也是case2的特 例。因此，case3采用该方式时，3种情况可以统一处理为case2。 q=p parent p child q=p p child *q的中序后继就是其右孩子 24 3、BST的删除 算法 void DelBSTNode( BSTree *T, KeyType key) { //*T是根 BSTree *q, *child, *parent=NULL, *p=*T; while ( p ) { //找待删结点 if ( p->key ==key ) break; //已找到 parent=p; //循环不变式是*parent为*p的双亲 p＝( key key ) ? p->lchild; p->rchild; } if ( !p ) return; //找不到被删结点，返回 q=p; //q记住被删结点*p if (q->lchild && q->rchild ) //case3，找*q的中序后继 for(parent=q,p=q->rchild; p->lchild; parent=p, p=p->lchild);
3、BST的刷除 3、平衡二叉树和平衡的二叉查找树 现在3种情况已绕一到情况2，被副结点p最多只有1个非空的孩子 ”平衡二叉树 child中(p->Ichild)?p->lchild;p->rchild;lfcase1时child空，香测非空 任一结点的左右子树高度大致相同，即只要二叉制高度为0g,则可认为 它是平衡的。 f(Iparent)”p的限亲为空，说明p是根，即根结点 ◆ 充全平衡二又树 *T=child;嗜是情况1，则树为空：否则child)取代p成为根 任一结点的左右子树高度亮全相同（满二叉树） els0(广p非授，它的孩子取代它与'p的双亲连接，即p 平街的二叉查找树 if p==parent->Ichild parent->lchild=child; 满足B$T性质的平衡二又制 else parent->rchild=child; ◆AVL到，任一结点的左右子树的高度之整的绝对值不如过1，h则1.44Ig肌 计(p=q)情况3，将p的数据copy到rq中 ◆红幕制：h2lgn q->key=p>key;I嗜有其他败据赤得copy ■平衡机制 AVL制：4种莫转 free(p方除p 红鼎树：2种城转 )时间Cm 5
5 25 3、BST的删除 //现在3种情况已统一到情况2，被删结点*p最多只有1个非空的孩子 child=(p->lchild)？p->lchild; p->rchild; //case1时child空，否则非空 If ( !parent ) //*p的双亲为空，说明 *p是根，即删根结点 *T=child; //若是情况1，则树为空；否则*child取代*p成为根 else { //*p非根，它的孩子取代它与*p的双亲连接，即删 *p if ( p==parent->lchild ) parent->lchild=child; else parent->rchild=child; if ( p != q ) //情况3，将*p的数据copy到*q中 q->key=p->key; //若有其他数据亦需copy } free( p ); //删除*p } //时间O(h) 26 3、平衡二叉树和平衡的二叉查找树 平衡二叉树 任一结点的左右子树高度大致相同，即只要二叉树高度为O(lgn)，则可认为 它是平衡的。 完全平衡二叉树 任一结点的左右子树高度完全相同（满二叉树） 平衡的二叉查找树 满足BST性质的平衡二叉树 AVL树：任一结点的左右子树的高度之差的绝对值不超过1，h≈1.44lgn 红黑树：h≈2lgn 平衡机制 AVL树：4种旋转 红黑树：2种旋转