《数据结构与算法》第九章查找

1、 找到找到-查找成功查找成功 找不到找不到-查找不成功查找不成功：根据某个给定的值，：根据某个给定的值， 在查找表中确定一个关键字值等于给定值的数在查找表中确定一个关键字值等于给定值的数据元素。据元素。 typedef float KeyType; /实型实型 typedef int KeyType; /整型整型 typedef char *KeyType ; /字符串型字符串型 typedef struct KeyType ; /关键字域关键字域 . /其它域其它域 ;： 查找表的组织查找表的组织 查找表的数据结构查找表的数据结构ADT StaticSearchTableD：D是具有相同特性

2、的数据元素的集合。是具有相同特性的数据元素的集合。 各个数据元素均含有相同类型、各个数据元素均含有相同类型、 可唯一标识数据元素的关键字。可唯一标识数据元素的关键字。 R：数据元素同属一个集合。：数据元素同属一个集合。 P： 操作结果：构造一个含操作结果：构造一个含n n个元素的静态查找表个元素的静态查找表STST。typedef struct ElemType *; /数据元素存储空间基址，数据元素存储空间基址， /建表时按实际长度分配，建表时按实际长度分配， / 0号单元保留不用号单元保留不用 int ; /表长度表长度SSTable;21)1(111, 1,.111ninnASLnpcp

3、ASLincplengthSTnniiniiiinii如果int Search_Bin(SSTable ST, KeyType key) /在顺序表在顺序表ST中折半查找其关键字等于中折半查找其关键字等于key的数据元素。的数据元素。 /若找到，则函数值为该元素在表中的位置，否则为若找到，则函数值为该元素在表中的位置，否则为0。 low=1; high=ST.length;/置区间初值置区间初值 while (lowdata.key) return (T); /查找结束查找结束 else if (LT(key,T-data.key) return (SearchBST(T-lchild, ke

4、y); /在左子树中继续查找在左子树中继续查找 else return(SearchBST(T-rchild, key); /在右子树中继续查找在右子树中继续查找/SearchBST 二叉查找树是一种动态的树，是在查找过程二叉查找树是一种动态的树，是在查找过程中不断地插入、添加而构造成的。新插入的结中不断地插入、添加而构造成的。新插入的结点一定是新添加的叶子结点，且是查找不成功点一定是新添加的叶子结点，且是查找不成功时访问的最后一个结点的左时访问的最后一个结点的左/ /右孩子。右孩子。pfpLfpLpfpLfpLpfpRfpRpfpRfpRpfpLpRtfpLpRt或令或令* *p p的直接后

5、继代替的直接后继代替* *p ppfpRttfpR或令或令* *p p的直接前驱代替的直接前驱代替* *p ppfpRqssfpRq 一棵平衡二叉树或者是一棵空树一棵平衡二叉树或者是一棵空树 或者是具有以下性质的二叉树：或者是具有以下性质的二叉树： 它的左右子树都是平衡二叉树它的左右子树都是平衡二叉树 000-21113，24，37，90，5313243713243790531324539037132471324753201324755320132475pplc132471324713902453759013245375由于由于* *p p的右子树的右子树上插入结点的右子树的右子树上插入结点使

6、使* *p p的平衡因子由的平衡因子由-1-1增至增至-2-2rcprc=p-rchild;p-rchild=rc-lchild;rc-lchild=p; p=rc;p131071013713202453755320132475101371320245375rc由于由于* *p p的右子树的左子树上插入结点的右子树的左子树上插入结点使使* *p p的平衡因子由的平衡因子由-1-1增至增至-2-2pldif(ld-bf=1) p-bf=0; rc-bf=-1; ld-bf=0;pprcrcldldif(ld-bf= =-1) p-bf=1; rc-bf=0; ld-bf=0;rcpldrcpld

7、rcpldh-1h-2rcpldprcldrcpldrcpldrc=p-rchild; ld=rc-lchild;switch(ld-bf)case 1: p-bf=0; rc-bf=-1; ld-bf=0; break; case -1: p-bf=1; rc-bf=0 ; ld-bf=0; break;R_Rotate(p-rchild);L_Rotate(p);rcpldrcpld171228171228132864233519642823351913171228641328352319lcprdlcprdlcprdif(rd-bf=1) p-bf=-1; lc-bf=0; rd-bf=

8、0; lcprdlcprdlcprdif(rd-bf=-1) p-bf=0; lc-bf=1; rd-bf=0;lc=p-lchild; rd=lc-rchild;swirch(rd-bf)case 1: p-bf=-1; lc-bf=0; rd-bf=0; break; case -1: p-bf=0; lc-bf=1; rd-bf=0; break;L_Rotate(p-lchild);R_Rotate(p);rcvoid L_Rotate(BSTree &p)/对以对以*p为根的二叉排序树做左旋处理为根的二叉排序树做左旋处理 /处理后处理后p指向新的树根结点，即旋转之前的右子树的根结点指

9、向新的树根结点，即旋转之前的右子树的根结点rc=p-rchild; /rc 指向的指向的p右子树根结点右子树根结点 p-rchild=rc-lchild; /rc 的左子树挂接为的左子树挂接为p的右子树的右子树rc-lchild=p; p=rc; /p指向新的根结点指向新的根结点/L_Rotatepvoid R_Rotate(BSTree &p) /对以对以*p为根的二叉排序树做右旋处理为根的二叉排序树做右旋处理 /处理后处理后p指向新的树根结点，即旋转之前的左子树的根结点指向新的树根结点，即旋转之前的左子树的根结点 lc=p-lchild; /lc指向的指向的p左子树根结点左子树根结点 p-

10、lchild=lc-rchild; /lc的右子树挂接为的右子树挂接为p的左子树的左子树 lc-rchild=p; p=lc; /p指向新的根结点指向新的根结点R_Rotatelcif (!T) /插入新结点，树长高，置插入新结点，树长高，置taller为为TRUE T=(BSTree)malloc(sizeof(BSTNode); T-data=e; T-lchild=T-rchild=NULL; T-bf=EH; taller=TRUE; else if(EQ(e.key, T-data.key) taller=FALSE; return 0; /树中已存在关键字为树中已存在关键字为e的结

11、点的结点,则不插入则不插入#define LH +1/左高左高#define EH 0/等高等高#define RH -1/右高右高Status InsertAVL(BSTree &T, ElemType e, Boolean &taller)/若在平衡的二叉排序树若在平衡的二叉排序树T中不存在和中不存在和e有相同关键字的结点，则插入一个有相同关键字的结点，则插入一个 /数据元素为数据元素为e的新结点，并返回的新结点，并返回1，否则返回，否则返回0。若因插入而使二叉排序树。若因插入而使二叉排序树 /失去平衡，则做平衡旋转处理。布尔变量失去平衡，则做平衡旋转处理。布尔变量taller反映反映 T

12、长高与否长高与否if(LT(e.key, T-data.key) ) /应继续在应继续在*T的左子树中进行搜索的左子树中进行搜索 if (!InsertAVL(T-lchild, e, taller) return 0; /未插入未插入*T的左子树的左子树 if (taller) /已插入到已插入到*T的左子树中且左子树长高的左子树中且左子树长高 switch(T-bf) /检查检查*T的平衡度的平衡度 case LH: LeftBalance(T); taller=FALSE;break; /原本左子树比右子树高，作左平衡处理原本左子树比右子树高，作左平衡处理 case EH:T-bf=LH

13、; taller=TRUE; break; /原本左右子树等高，现左子树长高原本左右子树等高，现左子树长高 case RH:T-bf=EH；taller=FALSE; break; /原本右子树比左子树高，现等高原本右子树比左子树高，现等高 /switch(T-bf) /ifif GT(e.key, T-data.key) /应继续在应继续在*T的右子树中进行搜索的右子树中进行搜索 if(!InsertAVL(T-rchild, taller) return 0; /未插入未插入 if (taller) /已插入到已插入到T的右子树且右子树长高的右子树且右子树长高 switch(T-bf) /

14、检查检查T的平衡度的平衡度 case RH: RightBalance(T); taller=FALSE; break; /原本左子树比右子树高，现等高原本左子树比右子树高，现等高 case EH:T-bf=RH; taller=TRUE; break; /原本左右子树等高，现有子树长高原本左右子树等高，现有子树长高 case LH:T-bf=EH; taller=FALSE; break; /原本右子树比左子树高，作右平衡处理原本右子树比左子树高，作右平衡处理 /switch(T-bf) /else/else return 1;/InsertAVLvoid LeftBalance(BSTre

15、e &T) /对以指针对以指针T所指结点为根的二叉树作左平衡处理，所指结点为根的二叉树作左平衡处理， /本算法结束时，指针本算法结束时，指针T指向新的根结点指向新的根结点 lc=T-lchild; /lc指向指向*T的左子树的根结点的左子树的根结点 switch(lc-bf) /检查检查*T的左子树的平衡度，并作相应处理的左子树的平衡度，并作相应处理 case LH: T-bf=lc-bf=EH; R_Rotate(T); break; /新结点插入在新结点插入在*T的左孩子的左子树上，作单右旋处理的左孩子的左子树上，作单右旋处理 case RH: /新结点插入在新结点插入在*T的左孩子的右子

16、树上，作双旋处理的左孩子的右子树上，作双旋处理 rd=lc-rchild; /rd指向指向*T的左孩子的右子树根的左孩子的右子树根 switch(rd-bf) /修改修改*T及其左孩子的平衡因子及其左孩子的平衡因子 case LH: T-bf=RH; lc-bf=EH; break; case RH:T-bf=EH；lc-bf=LH; break; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild); /对对*T的左子树做左旋平衡处理的左子树做左旋平衡处理 R_Rotate(T); /对对*T作右旋平衡处理作右旋平衡处理/switch(lc-bf) /Lef

17、tBalance一棵一棵m m阶的阶的B B- -树或为空树或为满足下列特性的树或为空树或为满足下列特性的：(1)(1)树中每个结点至多有树中每个结点至多有m m棵子树棵子树(2)(2)若根结点不是叶子结点，则至少有两棵子树若根结点不是叶子结点，则至少有两棵子树(3)(3)除根外的所有非终端结点至少有除根外的所有非终端结点至少有 m/2m/2 棵子树棵子树( (向向上取整上取整) ) 4阶阶B_树树135118243781111271393475364199FFFFFFFFFFFF24378243784阶阶B_树树135118243781111271393475364199FFFFFFFFFF

18、FF135118243781111271393475364199FFFFFFFFFFFFint Search(BTree p, KeyType K) /在在p p结点中的查找算法结点中的查找算法 n=p-keynum; if (GT(K, p-keyn) return n; if(LT(K,p-key1) return 0; i=1; while(ikeyi) i+; if(EQ(K,p-keyi) return i; else return i-1;Result SearchBTree(BTree T, KeyType K) /在在m阶阶B树树T上查找关键字上查找关键字K，返回结果，返回结果

19、若查找成功，若查找成功， /则特征值则特征值tag=1，指针，指针pt所指结点中第所指结点中第i个关键字等于个关键字等于K；否则特征值；否则特征值tag=0，/等于等于K的关键字应插入在指针的关键字应插入在指针pt所指结点中第所指结点中第i和第和第i+1个关键字之间个关键字之间 p=T; q=NULL; /初始化，初始化，p指向待查结点，指向待查结点，q指向指向p的双亲的双亲 found=FALSE; i=0; while(p & !found) n=p-keynum; /关键字个数关键字个数 i=Search(p,K);/在在p-key1.keynum中查找中查找i ,使得使得p-keyi=

20、Kkeyi+1 if(i0&p-keyi=K)found=TRUE; /找到待查的关键字找到待查的关键字 else q=p; p=p-ptri; if(found) return (p,i,1);/查找成功查找成功 else return(q,i,0);/查找不成功，返回查找不成功，返回K的插入位置信息的插入位置信息/SearchBTree查找分析查找分析查找查找在在B_B_树上找结点树上找结点在结点中找关键字在结点中找关键字在磁盘中进行在磁盘中进行在内存中进行在内存中进行在磁盘上查找的次数在磁盘上查找的次数= =关键字所在结点的层数关键字所在结点的层数含含N N个关键字的个关键字的m m阶阶

21、B_B_树的深度树的深度最大最大是多少？是多少？)21N(log12/m 1 1个关键字个关键字2 2个关键字个关键字3 3个关键字个关键字4 4个关键字个关键字5 5个关键字个关键字6 6个关键字个关键字7 7个关键字个关键字( (二二) B) B- -树的插入和删除树的插入和删除1 1插入插入先找到插入的位置先找到插入的位置(p,i)-(p,i)-总在最高层的非终端结点总在最高层的非终端结点30 37插入插入303045243 12375010061 7053 90插入插入2626452430 373 125010061 7053 9026 30 37453 125010061 7053

22、9024 302637插入插入8561 70 8545 70 61 708553 70 90 53 7090453 125010061 7024 30263753 90插入插入7 73 7 127 24 30 7 2430 3 7123 1224 30263710050 8545 7053906124 45 70 3 712 70 2430 45263710050 85539061若若p p中关键字个数小于中关键字个数小于m-1m-1，插入相应位置，插入相应位置若若p p中关键字个数等于中关键字个数等于m-1m-1，插入后分裂结点，插入后分裂结点m A0(k1,A1) . (km,Am)而关键

23、字而关键字k km/2m/2和指针和指针p p一起插入到一起插入到p p的双亲中去的双亲中去并且双亲也可能分裂，分裂可能一直进行到根结点，并且双亲也可能分裂，分裂可能一直进行到根结点，使树的深度增加使树的深度增加分裂成分裂成: :m/2-1 A0(k1,A1) . (km/2-1,Am/2-1) pm-m/2Am/2(km/2+1,A1) (km,Am) pStatus InsertBTree(BTree &T, KeyType K, BTree q, int i) /在在m阶阶B树树T上结点上结点*q的的keyi和和keyi+1之间插入关键字之间插入关键字K /若引起结点过大，则沿双亲链进行

24、必要的结点分裂调整使若引起结点过大，则沿双亲链进行必要的结点分裂调整使T仍是仍是m阶阶B树树 x=K;ap=NULL; finish=FALSE; /ap为为K所指向叶子的指针所指向叶子的指针 while(q & !finish) Insert(q,i,x,ap); if(q-keynumm) finish=TRUE; /插入后未溢出插入完成插入后未溢出插入完成4524 3 3710061 70 906124 3 3710070 9045243 12375010061 7053 9045243 123753100 7061 90删去删去505045243 123753100 7061 90删去删去535345243 123710061 70 9045243 123710061 70 90删去删去12124524 3 3710061 70 904524 3 37100