工业894专业课辅导数据结构讲义四

数据结构讲义（第四讲内容：查值K找失败，返回特定的值，该值表示查找失败0缺点：平均查找长度较大，特别是当顺序表的长度很大时，查找效率较低时间复杂度为2、二分查找（又称折半查找算法的基本思想（key1/2keyintBiSearch(DataTypea[],intn,KeyTypea[0]--a[n-1]key//查找成功时返回该元素的下标序号；失败时返回-{intlow=0,high=n- intwhile(low<={mid=(low+high)/2; if(a[mid].key==key)returnmid; elseif(a[mid].key<key)low=mid+1;elsehigh=mid-}return- }时间复杂度为折半查找要求表是顺序的，为保持表的有序性，在进行插入和删除操作时，索引表中的数据元素由两个域key域的最大值link域第一个数据元素的位置编号。分块查找过程分两步进行：首先查找索引表，确定待查记录所在块（子表（可用折半查找法或顺序查找法在相应块（子表）录。分块查找的主要代价是：需要增加一个辅助数组的空间和将初始表分衡二叉树等。树结构有B-树、B+树等。左的所有结点均小于根的值右的所有结点均大于根的值它的左右也分别为二叉排序树intSearch(BiTreeNode*root,DataType{BiTreeNode*p;if(root!={p=root;while(p!=NULL){if(p->data.keyitem.key)return1;//查找成功if(item.key>p->data.key)p=p-> //在右继p=p-> //在左继}}return }插入算法设计如intInsert(BiTreeNode**root,DataTyperootitemitem{BiTreeNode*current,*parent=NULL,*p;current=*root;while(current!={if(current->data.key==item.key)return0;parent=current;if(current->data.key<item.key)current=current->elsecurrent=current-}P=(BiTreeNode*)malloc(sizeof(BiTreeNode));if(p==NULL){}P->data=P->leftChild=P->rightChild=if(parent==NULL)*root=p; elseif(item.key<parent->data.key)parent->leftChild=p; parent->rightChild= return}值大于要删除结点数据元素关键字的最小值即寻找要删除结点右的最左结在情况下，二叉排序树的平均查找长度为O(n)。在一般情况下，二叉排序树的平均查找长度为O(log2n)。2（AVL树高度相差不到1。所以此树总是平衡的。平衡二叉树(BalancedbinarytreeAVL左右深度之差的绝对值不超过左右仍然为平衡二叉树平衡因子BF=左深度－右深度平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则找出插入新结点后失去平衡的最小根结点的指针。然后再调整这个中有关结点之间的关系，使之成为新的平衡。当失去平衡的最小被调整为平衡后，原有其他所有不平衡无需调整，整个二叉排序树就又失去平衡的最小是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的。假设用A表示失去平衡的最小的根结点，则调整该子1）LL由于在A的左孩子B的左上插入结点F，使A的平衡因子由1增至2 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右的根结点。而原来B的右子树则变成A的左。RR由于在A的右孩子C的右上插入结点F，使A的平衡因子由-1减至-2AC代替A作为根结点，A向左下旋转成为C的左的根结点。而原来C的左子树则变成A的右。LR由于在ABF，使A12而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A的左孩子B的右的根结点D向左上旋转提升到B结点的位置，然后再把该DALL型，再按LL的左上，此时成为LL型，再按LL型处理成平衡型RL由于在A的右孩子C的左上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A的右孩子C的左的根结点D向右上旋转提升到C结点的位置，然后再把该DARR型，再按RRA的左上，此时成为RR型，再按RR型处理成平衡型B_二叉排序树那样的分支现象。因此B_树的动态查找效率更高。B_B_mB_树或者是一棵空树，或者是满足下列要求的m树：树中每个结点至多有m个孩子结点（至多含有m-1个关键字除根结点外，其他结点至少有m/2个孩子结点（符号“”表示上取整若根结点不是叶结点，则根结点至少有结点查找算B_xx.keyKi若x.key=Ki则查找成功若key<K1则沿着指针P0所指的继续查找若Ki<key<Ki+1则沿着指