第23讲 二叉排序树和平衡二叉树

数据结构主讲：信息工程大学电子技术学院402教研室范新峰第23讲第9章查找9.1静态查找表9.2动态查找表9.2.1二叉排序树和平衡二叉树9.2.2B-树和B+树9.3哈希表9.2动态查找表特点表结构在查找过程中动态生成。要求对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key的记录。动态查找表主要有二叉树结构和树结构两种类型。二叉树结构有二叉排序树、平衡二叉树等。树结构有B-树、B+树等。9.2.1二叉排序树和平衡二叉树1.二叉排序树1）什么是二叉排序树或是一棵空树；或是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左、右子树也分别为二叉排序树。15303778535063902970二叉排序树实例：二叉排序树的数据类型描述structBtreeNode{ElemTypekey;//关键字BtreeNode*lchild,*rchild;//左、右孩子}BtreeNode,*Bitree;2）二叉排序树的查找15303778535063902970例：查找63506353637063二叉排序树的查找算法BiTreeSearchBST(BiTreeT,KeyTypekey){if((!T)||EQ(key,T-key))return(T);//查找结束elseifLT(key,T-key)return(SearchBST(T-lchild,key));//在左子树中继续查找elsereturn(SearchBST(T-rchild,key));//在右子树中继续查找}//SearchBST例：在图示的二叉排序树中查找关键字等于100的记录。153037785350639029703）二叉排序树的插入若二叉排序树为空，则作为根结点插入，否则，若待插入的值小于根结点值，则作为左子树插入，否则作为右子树插入。将二叉排序树的查找算法改写，以便能在查找不成功时返回插入位置。算法描述为：二叉排序树的插入算法StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){if(!T){p=f;returnFALSE;}//查找不成功elseifEQ(key,T-key){p=T;returnTRUE;}//查找成功elseifLT(key，T-key)SearchBST(T-lchild,key,T,p);//在左子树中继续查找elseSearchBST(T-rchild,key,T,p);//在右子树中继续查找}//SearchBST二叉排序树的插入算法StatusInsertBST(BiTree&T，ElemTypekey){//当二叉排序树T中不存在关键字=key的元素时，//插入key并返回TRUE，否则返回FALSEif(!SearchBST(T,key,NULL,p){//查找不成功s=(BiTree)malloc(sizeof(BiTNode))；s-key=key;s-lchild=s-rchild=NULL;if(!p)T=s;//被插结点*s为新的根结点，原树为空elseifLT(key,p-key)p-lchild=s;//*s为左孩子elsep-rchild=s//被插结点*s为右孩子returnTRUE；}elsereturnFALSE;//树中已有关键字相同的结点，不再插入}//InsertBST例：关键字序列{10、18、3、8、12、2、7、3}生成二叉排序树过程。1018381227注：二叉排序树与关键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不一样。4）二叉排序树的建立二叉排序树的建立的算法反复调用二叉排序树的插入算法即可BitreeCreat(intn){//建立含有n个结点的二叉排序树BitreeT=NULL;for(inti=1;i=n;i++){cinx;//输入关键字序列InsertBST(T,x);}returnBST;}说明：1.中序遍历二叉排序树可得到一个关键字的有序序列；2.进行插入操作时，不必移动其它结点，仅需改动某个结点的指针。表明，二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。153037785350639029705）二叉排序树上的删除对于二叉排序树，删去树上一个结点相当于删去有序序列中的一个记录，在删除某个结点之后依旧要保持二叉排序树的特性。如何在二叉排序树上删去一个结点呢?设在二叉排序树上被删除结点为*p(指向结点的指针为p)，其双亲结点为*f(结点指针为f)，设*p是*f的左孩子。FPCQSCLQLSLPRfpqsc分三种情况进行讨论：(1)若*p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针。(2)若*p结点只有左子树PL或者只有右子树PR。只需令PL或PR直接成为其双亲结点*f的左子树即可。(3)若*p结点的左子树和右子树均不空。FPCQSCLQLSLPRfpqscFCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法1:SSL①令*p左子树为*f的左子树，而*p右子树为*s的右子树②是令*p的直接前驱(或直接后继)替代*p，然后再从二叉排序树中删去它的直接前驱(或直接后继)。二叉排序树的删除算法StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnFALSE;//不存在关键字等于key的数据元素else{ifEQ(key,T-key){returnDelete(T)};//查找成功elseifLT(key，T-key)returnDeleteBST(T-lchild,key);elsereturnDeleteBST(T-rchild,key);}}//DelectBST二叉排序树的删除算法StatusDelete(BiTree&p){if(!p-rchild){//右子树空则只需重接它的左子树q=p;p=p-lchild;free(q);}elseif(!p-lchild){//左子树空则只需重接它的右子树q=p;p=p-rchild;free(q);}else{q=p;s=p-lchild;while(s-rchild){q=s;s=s-lchild;}//转左,然后向右到尽头p-data=s-data;if(q!=p)q-rchild=s-lchild;elseq-lchild=s-lchild;deletes;}ReturnTRUE;}//delete6）二叉排序树上的查找分析15303778535063902970例：查找63二叉排序树的查找分析含有n个结点的二叉排序树不唯一，ASL也不相同最差的情况是（n+1)/2（类似顺序查找）；O(n)。最好的情况是和log2n成正比（类似折半查找的判定树）O(log2n)为了保证树型查找有较高的查找速度，我们希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化单支树。9.2.1二叉排序树和平衡二叉树2.平衡二叉树1）什么是平衡二叉树也称为AVL树，是种附加了一定限制条件的二叉树，定义二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子。所谓平衡二叉树，是指一个二叉树其任一结点的平衡因子值只能是+1，0或-1，即任一结点的左、右子树高度之差不超过1。-1110-1003-200-2-10（a）平衡二叉树（b）不平衡的二叉树2）如何使构成的二叉排序树成为平衡二叉树？假设给平衡二叉树某个结点的左子树插入一新结点，且此新结点使左子树的高度加1，可能会遇到的情况：(A)如果原来其左子树高度hl与右子树高度hr相等，即原来此结点的平衡因子等于0，插入新结点后将使平衡因子变成+1，仍符合平衡二叉树的条件，不必对其调整；(B)如果原来hlhr，即原来此结点的平衡因子等于+1,插入新结点后将使平衡因子变成+2，破坏了平衡二叉树的限制条件，需对其加以调整；(C)如果原来hlhr，即原来此结点的平衡因子等于-1，插入新结点后将使平衡因子变成0，平衡更加改善，不必加以调整。第二次向左逆时针转平衡之-124053090037013平衡树的生成过程：(13，24，37，90，53)Φ空树插入13插入24-013-113024-213-124037插入37024037013-224-2371900530132437539013相继插入90和53向左逆时针右旋转平衡第一次向右顺时针旋转如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。平衡旋转可以归纳为四类：LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转LL平衡旋转由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。BARBR+2+1BLABRARABBL00LR平衡旋转由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根结点的子树失去平衡，则需进行两次旋转(先左旋后右旋)操作。CR-1ARBC+2ACL+1CRARACBLCLB00-1BL-1BLALB-2ABRRR平衡旋转由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作。BALA00BLBRACLRL平衡旋转由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需进行两次旋转(先右旋后左旋)操作。CR+1ALBC-2+1BRCLBRBCALA00-1CR3）查找性能平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。