数据结构chapter 11(2)查找

《数据结构chapter 11(2)查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上堂课要点回顾¢查找¢基本概念¢平均查找长度ASL¢顺序查找¢折半查找¢要求查找表有序¢用二叉判定树分析折半查找的效率¢分块查找¢要求表分块有序¢建立索引表¢查找¢二叉搜索树查找¢结点插入与树的建立¢结点删除¢查找第二十一次课阅读：朱战立，第293-298页习题：作业19project3数据结构课程内容⎧顺序查找⎪折半查找⎪⎪⎪索引查找⎨⎪二叉排序树查找和平衡二叉树⎪B树查找⎪⎪⎩哈希查找二叉搜索树的多样性¢同一个关键字集合，其关键字插入二叉搜索树的次序不同，就构成不同的二叉搜索树。¢n个关键字的集合，可以有n!种不同的关键字排列法，因此可以构成n!个二

2、叉搜索树(其中互不相同1n的有c2n个)，可以用ASL度量不同树的查找效率n+1例：关键字分别为1,2和3的记录可能构成五种二叉搜索树I：(1,2,3)II：(2,1,3)或III：(3,1,2)V：(1,3,2)IV：(3,2,1)1(2,3,1)3132213213322111.3.2平衡二叉搜索树(AVL)¢二叉搜索树BST受输入顺序影响¢最好O(log2n)¢最坏O(n)¢二叉搜索树的改进——怎样使得BST始终保持O(logn)级的平衡状态？2¢Adelson-Velskii和Landis发明了AVL树¢一种自平衡的二叉搜索树¢任何结点的左子树和

3、右子树的高度最多相差1¢AVL树是对二叉搜索树的操作规则做部分的改进以使树保持在一种类似于平衡的状态，从而达到较好的效率AVL树的性质¢可以为空¢具有n个结点的AVL树，高度为O(logn)¢如果T是一棵AVL树¢那么它的左右子树T、T也是AVL树LR¢并且h-h≤1LR¢h、h是它的左右子树的高度LR平衡因子(balancefactor,bf)¢为方便起见，每个结点x增加数据域bf，表示结点的平衡因子，定义为：bf(x)=x的右子树的高度-x的左子树的高度¢AVL树中任一个的结点的平衡因子可能取值为：0，1和-1¢每插入或删除结点要修改前驱结点的平衡因

4、子例：判断右侧二叉树是否是AVL树？AVL树结点的插入和平衡旋转¢插入与BST一样¢新结点作叶结点，时间代价O(log2n)¢但有可能造成结构失衡，此时需要自调整，使之恢复平衡，我们称调整的过程为重构（restructuring）。调整方法是通过称为旋转(rotation)的局部操作，这种调整规则必须保持二叉搜索树的中序遍历顺序¢旋转可以归纳为四类：¢LL型（单）旋转(singlerotation)¢RR型（单）旋转¢LR型（双）旋转(doublerotation)¢RL型（双）旋转11））LLLL平衡旋转：平衡旋转：A若在结点(设A)的左子树的根(设B

5、B)的左子树上插入结点(设C)，使A的平衡因子从-1增加至-2，CA需要进行一次顺时针旋转。(以B为旋转轴）危急结点A左重22））RRRR平衡旋转：平衡旋转：若在结点(设A)的右子树的根(设AB)的右子树上插入结点(设C)使AB的平衡因子从1增加至2，需要进行一次逆时针旋转。AC(以B为旋转轴）危急结点A右重这种调整规则可以保证二叉搜索树的中序遍历顺序不变33））LRLR平衡旋转：平衡旋转：若在结点(设A)的左子树的根(设AB)的右子树上插入结点(设C)，CBCB使A的平衡因子从-1增加至-2，需要先进行逆时针旋转，再顺时BACAC针旋转。(以插入的结点

6、C为旋转轴）44））RLRL平衡旋转：平衡旋转：若在结点(设A)的右子树的根(设B)A的左子树上插入结点(设C)，使ACBCB的平衡因子从1增加至2，需要先进行顺时针旋转，再逆时针旋转。ACACB(以插入的结点C为旋转轴）这种调整规则可以保证二叉搜索树的中序遍历顺序不变旋转运算的实质把树做任何一种旋转（RR、RL、LL、LR）¢目的1：平衡¢保持插入前子树的高度不变¢原来二叉树在A结点上面的其余部分（若还有的话）总是保持平衡的¢目的2：新树保持了原来的中序遍历顺序¢旋转的时间代价：O(1)¢处理中仅需改变少数指针插入单词：cup，cop，copy，hit

7、，hi，his和hia后得到的AVL树插入单词：cup，cop，copy，hit，hi，his和hia后得到的AVL树AVL树结点的删除¢删除是插入的逆操作。从删除结点的意义上来说，AVL树的删除操作与BST一样，因此具体删除过程可参考BST结点的删除¢但是AVL树的删除比较复杂，因为要保持平衡¢由于情况较多，列举说明AVL结点删除后的调整¢删除结点后AVL树需要调整¢删除结点可能导致子树的高度以及平衡因子的变化，因此需要调整¢此外，这个调整可能会导致被删结点的祖先发生新的不平衡,，因此需要沿着被删除结点到根结点的路径来调整这种变化¢调整策略¢从被删除的

8、结点开始单旋转或者双旋转操作¢连续调整¢向上查找到其祖父结点，进行单旋转或者双旋