动态查找表分析

1、8.2 8.2 动态查找表动态查找表 也即树表的查找。也即树表的查找。 本节介绍一种以树的形式来组织查找表的方法，本节介绍一种以树的形式来组织查找表的方法，以实现动态高效率的查找。以实现动态高效率的查找。 1、二叉排序树、二叉排序树 2、平衡二叉树、平衡二叉树 3、B树树 4、B+树树 455310061123907837248.2.1 8.2.1 二叉排序树二叉排序树一、二叉排序树的定义一、二叉排序树的定义 BST: Binary Sort(Search) Tree 二叉排序树或空，或满足如下性质：二叉排序树或空，或满足如下性质： （1）有一个根，若根的左子树非空，则左）有一个根，若根的左子

2、树非空，则左子树上所有结点的关键字值均小于根结点的值子树上所有结点的关键字值均小于根结点的值。若根的右子树非空，则右子树上的所有结点。若根的右子树非空，则右子树上的所有结点的关键字值均大于根结点的值。的关键字值均大于根结点的值。 （2）左右子树同样是二叉排序树。）左右子树同样是二叉排序树。455310061123907837248.2.1 8.2.1 二叉排序树二叉排序树二、二叉排序树的特点二、二叉排序树的特点 中序遍历得一有（升）序序列。中序遍历得一有（升）序序列。三、二叉排序树的查找三、二叉排序树的查找 查找方法：查找方法： 若根结点的关键字值等于查找的关若根结点的关键字值等于查找的关键字

3、，查找成功。键字，查找成功。 否则，若小于根结点的关键字值，否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字的查其左子树。若大于根结点的关键字的值，则查其右子树。值，则查其右子树。 在左右子树上的操作类似。在左右子树上的操作类似。 455310061123907837248.2.1 8.2.1 二叉排序树二叉排序树例例: 查找查找k=24455310061123907837248.2.1 二叉排序树二叉排序树三、二叉排序树的查找三、二叉排序树的查找 查找方法：查找方法： 若根结点的关键字值等于查找的关若根结点的关键字值等于查找的关键字，查找成功。键字，查找成功。 否则，若小于根结

4、点的关键字值，否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字的查其左子树。若大于根结点的关键字的值，则查其右子树。值，则查其右子树。 在左右子树上的操作类似。在左右子树上的操作类似。 例例: 查找查找k=60 结点结构及类型定义结点结构及类型定义 struct bnode keytype key; struct bnode *lchild; struct bnode *rchild;45531006112390783724lchild key rchild typedef struct bnode bstnode;算法设计算法设计bstnode *bstsearch(bstno

5、de *t, keytype K) / t:指向根结点指向根结点, k:待查找关键字待查找关键字 if (t=NULL | t-key= k) return(t)； else if (t-key k) return(bstsearch(t-lchild,k); / 在左子树上查找在左子树上查找 else return(bstsearch(t-rchild,k); / 在右子树上查找在右子树上查找 4553100611239078372445531006112390783724四、二叉排序树的插入四、二叉排序树的插入若二叉树为空。则生成根结点。若二叉树为空。则生成根结点。若二叉树非空若二叉树非空

6、（1）首先执行查找算法，找出被插结点的）首先执行查找算法，找出被插结点的 父结点。父结点。（2）判断被插结点是其父结点的左、右儿）判断被插结点是其父结点的左、右儿 子，子，将其作为叶子结点插入。将其作为叶子结点插入。例例1：在二叉排序树中插入：在二叉排序树中插入606045531006112390783724四、二叉排序树的插入四、二叉排序树的插入若二叉树为空。则先生成根结点。若二叉树为空。则先生成根结点。若二叉树非空若二叉树非空（1）首先执行查找算法，找出被插结点的）首先执行查找算法，找出被插结点的 父亲结点。父亲结点。（2）判断被插结点是其父亲结点的左、右儿）判断被插结点是其父亲结点的左、

7、右儿 子，子，将其作为叶子结点插入。将其作为叶子结点插入。例例2：以：以 45,53,12,37,24,100,3,61,90,78 构造二叉排序树。构造二叉排序树。 125393372445五、二叉排序树的查找分析五、二叉排序树的查找分析 125393372445（1）以）以 45, 53, 24, 12, 93, 37顺序建立二叉排序树。顺序建立二叉排序树。ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6（2）以）以 12,24,37,45, 53, 93 顺序建立二叉排序树。顺序建立二叉排序树。 在一般情况下，在一般情况下，P（i）为具有为

8、具有 i 个结点二叉排序树的平均查找长度。个结点二叉排序树的平均查找长度。 P（n,i）= 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) / n n-1 P（n）= P（n,i）/ n i=0 = 1.465log2n i个关键字个关键字第一个关键字第一个关键字539337244512P（n,i）= P（6, 3） = 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 / 6 = 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 / 6注意：这里注意：这里 P(3)、P(2) 是具有是具有 3 个结点、

9、个结点、2 个结点的个结点的二叉排序树的平均查找长度。二叉排序树的平均查找长度。 在一般情况下，在一般情况下，P（i）为具有为具有 i 个结点二叉排序树的平均查找个结点二叉排序树的平均查找 长度。长度。 P(3) （1+2+2）/ 3 = 5/3 P(2) （1+2）/ 2 = 3/2 六、二叉排序树的删除六、二叉排序树的删除 （1）删除叶子结点：直接删除。例如删除）删除叶子结点：直接删除。例如删除244553100611239078372445531006112390783724 （2）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如）删除子树的根结点：若被删结点的左儿子为空或者右

10、儿子为空。如100 4553100611239078372445531006112390783724六、二叉排序树的删除六、二叉排序树的删除 （2）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如100 4553100611239078372445531233724六、二叉排序树的删除六、二叉排序树的删除 619078 （3）删除子树的根结点且被删结点的左子树和右子树均不空。如）删除子树的根结点且被删结点的左子树和右子树均不空。如12 45531006112390783724455310061390783724六、二叉排序树

11、的删除六、二叉排序树的删除 一般情况一般情况:FP被删结点被删结点CCLPRQQLSSLFSCCLPRQQLSLFCCLPRQQLSSL删除方法（删除方法（1）删除方法（删除方法（1）删除方法（删除方法（2） 539337244512一、什么是平衡二叉树一、什么是平衡二叉树 平衡二叉树平衡二叉树(Balanced Binary Tree ) 又称又称AVL树。树。它或是空树，或是具有下列性质的它或是空树，或是具有下列性质的二叉排序树二叉排序树。 它的左子树和右子树都是平衡二叉树，且左子树和右它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过子树的深度之差的绝对值不超过1

12、。8.2.2 8.2.2 平衡二叉树平衡二叉树(AVL(AVL树树) )二、平衡因子二、平衡因子（Balance Factor) 左子树的深度左子树的深度 - 右子树的深度右子树的深度 即平衡二叉树中每一结点的平衡因即平衡二叉树中每一结点的平衡因子为：子为：0，1，-1。0-10000 5393372445120-1三、平衡二叉树的查找三、平衡二叉树的查找 平衡二叉树的查找方法平衡二叉树的查找方法 与二叉排序树查找方法相同。与二叉排序树查找方法相同。00008.2.2 平衡二叉树平衡二叉树(AVL树树) （1）找插入位置；）找插入位置； （2）插入结点；）插入结点； （3）若插入后导致不平衡，

13、则进行调整。）若插入后导致不平衡，则进行调整。4590100781236137240100001-1-1插入插入 504590100781236137240100001-10500四、平衡的二叉树的插入四、平衡的二叉树的插入4590100781236137240100001-1-1插入插入 154590100781236137240100011-20500152 （1）找插入位置；）找插入位置； （2）插入结点；）插入结点； （3）若插入后导致不平衡，则进行调整。）若插入后导致不平衡，则进行调整。四、平衡的二叉树的插入四、平衡的二叉树的插入4590100781236137240100110LL

14、旋转旋转4590100781236124370-100001-2050015250001500 （1）找插入位置；）找插入位置； （2）插入结点；）插入结点； （3）若插入后导致不平衡，则进行调整。）若插入后导致不平衡，则进行调整。四、平衡的二叉树的插入四、平衡的二叉树的插入 例：以例：以30,35,39,15,10,28,16,29,17建立平衡二叉树。建立平衡二叉树。平衡旋转平衡旋转1、LL旋转旋转LL旋转的结果旋转的结果平衡旋转平衡旋转2、RR旋转旋转RR旋转的结果旋转的结果平衡旋转平衡旋转3. LR旋转旋转LR旋转后旋转后平衡旋转平衡旋转4. RL旋转旋转再左旋再左旋T3T4Th-1T

15、h-2Th : 高度高度 h 结点个数最少的结点个数最少的AVL树树 左子树为左子树为 Th1 右子树为右子树为Th2五、平衡二叉排序树的查找分析五、平衡二叉排序树的查找分析T2T1 设以设以Nh表示深度为表示深度为h的二叉平衡树中的最少结点数。的二叉平衡树中的最少结点数。 显然，显然，N0=0, N1=1, N2=2 Nh=Nh-1+Nh-2+1 可以证明，可以证明，n个结点的个结点的AVL树的最大深度为：树的最大深度为： log (5 (n+1) ) - 2。 其中，其中，=(1+ 5 )/2五、平衡二叉排序树的查找分析五、平衡二叉排序树的查找分析 一、一、B-树的定义树的定义 m 阶阶

16、B-树满足或空，或满足树满足或空，或满足（1）树中每个）树中每个结点结点最多有最多有m个子树个子树 ；（2）若根结点不是叶子结点，则至少有）若根结点不是叶子结点，则至少有2个子树；个子树； （3）除根结点外的所有非叶子结点至少有）除根结点外的所有非叶子结点至少有 m/2 个子树；个子树； （4）所有的非）所有的非叶子叶子结点中包含的结点中包含的数据信息为：数据信息为： (n,A0,K1,R1,A1,K2,R2,A2, ,Kn,Rn,An） 其中，其中，n: 关键字的个数关键字的个数 Ki：关键字关键字 Ri：关键字关键字 = Ki 的数据记录在硬盘中的地址的数据记录在硬盘中的地址 Ai： Ki

17、且且 Ki+1 的结点地址的结点地址 K1 =K2 = . = Kn, A0：key1.n中进行查找, /直至p-keyi = k keyi+1 止, 0=i0)&(p-keyi=K) return(p,i,1)；/查找成功 else q=p; p=p-ptri; return(q,i,0)/查找不成功, 返回插入位置信息 /srch_mbtree三、三、B-树查找分析树查找分析B-树主要用作树主要用作文件的索引文件的索引，因此，它的查找涉及到外存的存取。，因此，它的查找涉及到外存的存取。B-树通常树通常存储在磁盘上存储在磁盘上。从上述算法可知：在从上述算法可知：在B-树上进行查找包含

18、树上进行查找包含两种两种基本操作：基本操作：(1)在在B-树中找树中找结点；结点；(2)在结点中找关键字。在结点中找关键字。因此，第因此，第(1)步查找操作是在磁盘上进行的。第步查找操作是在磁盘上进行的。第(2)是在内存中进行的。是在内存中进行的。即在磁盘上找到指针即在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于利用顺序查找或折半查找查询等于K的关键字。的关键字。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，因此，在磁盘上进

19、行查找的次数、即待因此，在磁盘上进行查找的次数、即待查关键字所在结点在查关键字所在结点在B-树上的层次树上的层次数，是决定数，是决定B-树查找效率的首要因素。树查找效率的首要因素。考虑最坏情况，考虑最坏情况，即待查结点在即待查结点在B-树上的最大层次数，即含树上的最大层次数，即含N个关键字的个关键字的m阶阶B-树的最大深度是多少？树的最大深度是多少？三、三、B-树查找分析树查找分析 设关键字的总数为设关键字的总数为 N ，求求 m阶阶 B-树的最大层次树的最大层次 L。层次层次结点数结点数11223 2（ m/2 ）4 2（ m/2 ） 2. . . .L 2（ m/2 ）L-2 L+1 2（

20、 m/2 ）L-1 （这一层是叶子层，若（这一层是叶子层，若m阶阶B-树中有树中有N个关键字，则查找不成功的结点为个关键字，则查找不成功的结点为N+1)所以，所以，N+12 * *( ( m/2 L-1 )(N=1 2 2（ m/2 -1） +.+ 2（ m/2 ）L-2 = 2 m/2 L-1 -1故：故：Llog m/2 （N+1）/2 + 1）设设 N 1000000 且且 m256 ，则则 L m叉？叉？ 例如插入例如插入60。解决方法：分裂！将一个结点分成两个结点。解决方法：分裂！将一个结点分成两个结点。B-树插入举例：树插入举例：2-3树（树（3阶阶B-树）及插入。树）及插入。 （

21、1）插入）插入14；B-树插入举例树插入举例：2-3树（树（3阶阶B-树）及插入。树）及插入。 （2）插入）插入55；（3）插入）插入19 例：例：2-3 树的删除操作。树的删除操作。3244553 90371005061，70删删503244561 90371005370再删除再删除5332445 903710061，70再删除再删除373，2445 9010061，703，24 45 9010061，70合并合并合并合并合并合并五、五、B-树的删除树的删除8.2.4 B+树树 B+树是树是 B-树的变形树。树的变形树。在实现文件索引结构方法比在实现文件索引结构方法比B-树使树使用得更普遍。用得更普遍。m 阶阶 B+树与树与m阶阶B-树的树的差异差异在于：在于：（1）有）有n个子树的结点中含有个子树的结点中含有n个关键字；个关键字；（2）所有的所有的叶子结点叶子结点中包含了全部关键字的信息中包含了全部关键字的信息，及指向，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；自小