第-7-章-集合与搜索数据结构课件.ppt

1、 1)定义 2)外侧-一次旋转 内侧-二次旋转 3)AVL树的插入 插入一定在叶子结点 找到发生不平衡的最小子树 进行单旋或双旋 例子：colour=red,orange,yellow,green,black,blue,purple,white 集合的特点：集合的成员必须互不相同 集合中的成员一般是无序的即没有先后次 序关系，并用，括住,如 s=s1 ,s2,s3,sm 集合中的所有成员有相同的数据类型 集合的性质：成员原子（单元素）集合firstA.first 求交集A.firstparent:0.63.静态搜索表otherkeyelement 01.:Currentsize-1Arrays

2、ize-1;搜索表的类定义template class searchList:public dataList public:0 1 2 3 CurrentSize ArraySizeelementxa1a2a.查找Xn-1i=0i=0n-11n1nn-1i=01nn(n+1)2n+1 21n：内部结点，：外部结点 二叉搜索树 （扩充二叉树）4 0-118601012 3124106782531 22 23 24 2 0123hn-1i=0ii1nn-1i=01nh-1h-212h1n1n1nh hn+1 n10045123533724617890查找37，找到查找5，49 找不到二叉搜索树:r

3、oot根指针,Refvalue数据输入停止的标志,用于输入 主要操作:搜索,插入,删除.*二叉搜索树如果按中序遍历，则得一有序序列。2)二叉搜索树上的搜索（寻找x)方法：从根结点开始，沿某一个分支逐层向下比较。如果相等，则当前结点就是;如果x 当前结点的key,则沿左子树进行搜索;否则沿右子树进行搜索。Leftchild data righchildPtr temp5317452378658781948809以下算法取右子树中的最小节点值填补上去：以下算法取右子树中的最小结点值填补上去1510811242117232726252832353331302016122918n2n142025485

4、36076845325762048 608414 如果按上述次序 2838485868422）AVL树的定义：是一棵二叉搜索树。树中每个结点的左右子树高度之差的绝对值小于等于1。树的高度：根结点到叶结点的最大路径长。结点的平衡因子：结点的右子树高度 结点的左子树高度。每个结点leftdatarightbalanceABCDE+0hhhABCDEhhh+1ABCDE1345678910111213456789101112左单旋转调整后:树高不变.原h+2,插入后h+3,调整后h+2,不平衡不会向外传递.h+1+ABCDEhhhACD13456789101112ACD13456789101112C

5、右下旋A左下旋C右旋转A左旋转ABCDEGFhhh-1 h-1orABCDEGFhhh-1h-1orACD13468910111257BACDEGFhhh-1 h-1or134567891011121518202224没有变化 *调整只要在包含插入结点的最小不平衡子树中进行,即从根到达插入结点的路径上,离插入结点最近的,并且平衡系数0的结点为根的子树。-113456 781011121518202224+100009ABCDEhhhABhCDEhhA右下旋ABCDEFGhhh-1 h-1ABCDEFGhhorh-1h-1DhABCEFGhh-1h-1orB左下旋A右下旋orh-1h-1ABCD

6、EFGhhhh-1h-1ABCDEFGhorh-1 hh-1ABCDEFGhor 4)AVL树的插入（Insert)把元素x插入到以tree为根的AVL树中 template int AVLTree:Insert(AVLNode*&tree,Type x,int&tallar)从空的AVL树建树的算法。我们先从一个例子出发：7个关键码发生四种转动 A，Z，C，W，D，X，YAAZAZCAZCWAZC右内右双旋转ADZCW左外左单旋转左双旋转右单旋转ACDZW右外ACDZXWACDZXWY左内ACDZXWAYCDZXWWX 假设被删除结点为W,它的中序后继为X,则用X代替W,并 删除X.所不同的

7、是:删除X后,以X为根的子树高度减1,这一高度 变化可能影响到从X到根结点上每个结点的平衡因子,因此要进 行一系列调整.bacdefghijklmnoprstq现要删除Cab右内defgh(1)abdefghijklmnoprstq右内(2)labdefghijktmnpoqrs 因为删除操作不平衡要传递，所以设置一个布尔变量shorter来指明子树 的高度是否被缩短。在每个结点上的操作取决于shorter的值和结点的平衡 因子，有时还要依赖子女的平衡因子。如果从被删结点（指真正被删结点，如上例中的d）的双亲到根的路径 上的各个结点p，在shorter保持为true时执行下面的操作,如果sho

8、rter变为False,算法终止。综合为一般情况：（假设都在左子树上删除）+_T1T2T3Pqhhh-1情况2：情况3：(1)shorter为false整个子树高度不变shorter为true整个子树高度减少shorter为false高度不变一次旋转PP+T1T2h._T1T1T2T2PPh+1hh.+T1T2T3Pqhh.q b=0P,q的平衡因子符号相同phhh-1+qT1T2T3qhh-1h-1.pT1T2T3rh-1h-1pqT1T2T3T4ph-1hh-1_+qrT1T2T3T4P,q的平衡因子符号不同Shorter为true高度减少Shorter为true高度减少一次旋转双旋转(3

9、)h-1h-2h假设右子树高度为h-1因结点个数最少,左子树高度只能是h-2这两棵左子树,右子树高度分别为h-2,h-1,也一定是结点数最少的:n=7h=3T 3h=1T 1n=2h=2T 2n=4 h=4T 4n=12h=0T 0n=1T h-2T h-1假设N h表示一棵高度为h的Fibonacci树的结点个数，则 N h=N h-1+N h-2+1 N 0=1,N 1=2,N 2=4,N 3=7,N4=12,.N 0+1=2,N 1+1=3,N2+1=5,N 3+1=8,N4+1=13,.N h+1满足费波那契数的定义，并且N h+1=F h+3 f 0 f 1 f 2 f 3 f 4 f 5 f 6 .0 1 1 2 3 5 8 .费波那契数F i 满足下列公式 15 1-5 2iii|1,()相当小1+5 21-5 21-5 2 15 15i N h+1=()+0(1)费波那契数树是具有相同高度的所有平衡二叉树中结点 个数最少的 n+1Nh+1=()+0(1)h log(n+1)+0(1)log(n+1)log 1+5 21+5 21+5 2 15 15132h+3222h+3