动态查找表讲述

《动态查找表讲述》由会员分享，可在线阅读，更多相关《动态查找表讲述（49页珍藏版）》请在金锄头文库上搜索。

1、8.2 动态查找表 也即树表的查找。 本节介绍一种以树的形式来组织查找表的方法， 以实现动态高效率的查找。 1、二叉排序树 2、平衡二叉树 3、B树 4、B+树 45 53 100 61 12 3 90 78 37 24 8.2.1 二叉排序树 一、二叉排序树的定义 BST: Binary Sort(Search) Tree 二叉排序树或空，或满足如下性质： （1）有一个根，若根的左子树非空，则左 子树上所有结点的关键字值均小于根结点的值 。若根的右子树非空，则右子树上的所有结点 的关键字值均大于根结点的值。 （2）左右子树同样是二叉排序树。 45 53 100 61 12 3 90 78 3

2、7 24 8.2.1 二叉排序树 二、二叉排序树的特点 中序遍历得一有（升）序序列。 三、二叉排序树的查找 查找方法： 若根结点的关键字值等于查找的关 键字，查找成功。 否则，若小于根结点的关键字值， 查其左子树。若大于根结点的关键字的 值，则查其右子树。 在左右子树上的操作类似。 45 53 100 61 12 3 90 78 37 24 8.2.1 二叉排序树 例: 查找k=24 45 53 100 61 12 3 90 78 37 24 8.2.1 二叉排序树 三、二叉排序树的查找 查找方法： 若根结点的关键字值等于查找的关 键字，查找成功。 否则，若小于根结点的关键字值， 查其左子树。

3、若大于根结点的关键字的 值，则查其右子树。 在左右子树上的操作类似。 例: 查找k=60 结点结构及类型定义 struct bnode keytype key; struct bnode *lchild; struct bnode *rchild; ; 45 53 100 61 12 3 90 78 37 24 lchild key rchild typedef struct bnode bstnode; 算法设计 bstnode *bstsearch(bstnode *t, keytype K) / t:指向根结点, k:待查找关键字 if (t=NULL | t-key= k) retur

4、n(t)； else if (t-key k) return(bstsearch(t-lchild,k); / 在左子树上查找 else return(bstsearch(t-rchild,k); / 在右子树上查找 45 53 100 61 12 3 90 78 37 24 45 53 100 61 12 3 90 78 37 24 四、二叉排序树的插入 若二叉树为空。则生成根结点。 若二叉树非空 （1）首先执行查找算法，找出被插结点的 父结点。 （2）判断被插结点是其父结点的左、右儿 子，将其作为叶子结点插入。 例1：在二叉排序树中插入60 60 45 53 100 61 12 3 90

5、78 37 24 四、二叉排序树的插入 若二叉树为空。则先生成根结点。 若二叉树非空 （1）首先执行查找算法，找出被插结点的 父亲结点。 （2）判断被插结点是其父亲结点的左、右儿 子，将其作为叶子结点插入。 例2：以 45,53,12,37,24,100,3,61,90,78 构造二叉排序树。 12 53 9337 24 45 五、二叉排序树的查找分析 12 53 93 37 24 45 （1）以 45, 53, 24, 12, 93, 37 顺序建立二叉排序树。 ASL=(1+2+2+3+3+3)/6=14/6 ASL=(1+2+3+4+5+6)/6=21/6 （2）以 12,24,37,4

6、5, 53, 93 顺序建立二叉排序树。 在一般情况下，P（i）为具有 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个关键字第一个关键字 53 9337 24 45 12 P（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) 是具有

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

8、树的删除 （2）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如100 45 53 100 61 12 3 90 78 37 24 45 53 12 337 24 六、二叉排序树的删除 61 90 78 （3）删除子树的根结点且被删结点的左子树和右子树均不空。如12 45 53 100 61 12 3 90 78 37 24 45 53 100 61 3 90 78 37 24 六、二叉排序树的删除 一般情况: F P 被删结点 C CL PR Q QL S SL F S C CL PR Q QL SL F C CL PR Q QL S SL 删除方法（1）删除方法（1） 删除方法（

9、2） 53 9337 24 45 12 一、什么是平衡二叉树 平衡二叉树(Balanced Binary Tree ) 又称AVL树。 它或是空树，或是具有下列性质的二叉排序树。 它的左子树和右子树都是平衡二叉树，且左子树和右 子树的深度之差的绝对值不超过1。 8.2.2 平衡二叉树(AVL树) 二、平衡因子（Balance Factor) 左子树的深度 - 右子树的深度 即平衡二叉树中每一结点的平衡因 子为：0，1，-1。 0 -1 0 00 0 53 9337 24 45 12 0 -1 三、平衡二叉树的查找 平衡二叉树的查找方法 与二叉排序树查找方法相同。 0 00 0 8.2.2 平衡

10、二叉树(AVL树) （1）找插入位置； （2）插入结点； （3）若插入后导致不平衡，则进行调整。 45 90 100 78 12 3 61 37 24 0 1 0 0 0 0 1 -1 -1 插入 50 45 90 100 78 12 3 61 37 24 0 1 0 0 0 0 1 -1 0 50 0 四、平衡的二叉树的插入 45 90 100 78 12 3 61 37 24 0 1 0 0 0 0 1 -1 -1 插入 15 45 90 100 78 12 3 61 37 24 0 1 0 0 0 1 1 -2 0 50 0 15 2 （1）找插入位置； （2）插入结点； （3）若插入后

11、导致不平衡，则进行调整。 四、平衡的二叉树的插入 45 90 100 78 12 3 61 37 24 0 1 0 0 1 1 0 LL旋转 45 90 100 78 12 3 61 24 37 0 -1 0 0 0 0 1 -2 0 50 0 15 2 50 0 0 15 0 0 （1）找插入位置； （2）插入结点； （3）若插入后导致不平衡，则进行调整。 四、平衡的二叉树的插入 例：以30,35,39,15,10,28,16,29,17建立平衡二叉树。 平衡旋转 1、LL旋转 LL旋转的结果 平衡旋转 2、RR旋转 RR旋转的结果 平衡旋转 3. LR旋转 LR旋转后 平衡旋转 4. RL

12、旋转 再左旋 T3 T4 Th-1Th-2 Th : 高度 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 阶 B-树满足或空，或满足 （1）树中每个结点最多有m个子树 ； （2）若根结点不是叶子结点，则至少有2个子树； （3）除根结点外的所有非叶子结点至少有

13、m/2 个子树； （4）所有的非叶子结点中包含的数据信息为： (n,A0,K1,R1,A1,K2,R2,A2, ,Kn,Rn,An） 其中，n: 关键字的个数 Ki：关键字 Ri：关键字 = Ki 的数据记录在硬盘中的地址 Ai： Ki且 Ki+1 的结点地址 K1 =K2 = . keyi = k keyi+1 止, 0ptri; return(q,i,0)/查找不成功, 返回插入位置信息 /srch_mbtree 三、B-树查找分析 B-树主要用作文件的索引，因此，它的查找涉及到外存的存取。 B-树通常存储在磁盘上。 从上述算法可知：在B-树上进行查找包含两种基本操作：(1)在B-树中找

14、结点；(2)在结点中找关键字。 因此，第(1)步查找操作是在磁盘上进行的。第(2)是在内存中进行的。 即在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再 利用顺序查找或折半查找查询等于K的关键字。 显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多， 因此，在磁盘上进行查找的次数、即待查关键字所在结点在B-树上的层次 数，是决定B-树查找效率的首要因素。 考虑最坏情况，即待查结点在B-树上的最大层次数，即含N个关键字的m 阶B-树的最大深度是多少？ 三、B-树查找分析 设关键字的总数为 N ，求 m阶 B-树的最大层次 L。 层次结点数 11 22 3 2（ m/2 ） 4 2（ m/2 ） 2 . . . . L 2（ m/2 ）L-2 L+1 2（ m/2 ）L-1 （这一层是叶子层，若m阶B-树中有N个关键字，则查找不成功的结点为N+1) 所以，N+12 *( m/2 L-1 ) (N=1 2 2（ m/2 -1） +.+