动态查找表详解.ppt

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,37,2

2、4,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) return(t)； els

4、e 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,78,37,24

5、,四、二叉排序树的插入,若二叉树为空。则先生成根结点。 若二叉树非空 （1）首先执行查找算法，找出被插结点的 父亲结点。 （2）判断被插结点是其父亲结点的左、右儿 子，将其作为叶子结点插入。,例2：以 45,53,12,37,24,100,3,61,90,78 构造二叉排序树。,12,53,93,37,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,45, 53, 9

6、3 顺序建立二叉排序树。,在一般情况下，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个关键字 第一个关键字,n-i-1个关键字 第一个关键字,53,93,37,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

7、)、P(2) 是具有 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

8、,24,六、二叉排序树的删除,（2）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如100,45,53,100,61,12,3,90,78,37,24,45,53,12,3,37,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,S,C,Q,QL,SL,F,C,Q,QL,S,SL,删除方法（1）,删除方法（1）,删除方法（2）,53,93,37,24,45,12,一、什么是平

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

10、结点； （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旋转,再左旋,T3,T4,Th-1,Th-2,Th

12、 : 高度 h 结点个数最少的AVL树 左子树为 Th1 右子树为Th2,五、平衡二叉排序树的查找分析,T2,T1,设以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）除根结点外的所有非叶子结点至少有 m/2 个子树； （4）所有的非叶子结点中包含

13、的数据信息为： (n,A0,K1,R1,A1,K2,R2,A2, ,Kn,Rn,An） 其中，n: 关键字的个数 Ki：关键字 Ri：关键字 = Ki 的数据记录在硬盘中的地址 Ai： Ki且 Ki+1 的结点地址 K1 =K2 = . = Kn, A0：K1 的结点的地址 （5）所有的叶子结点都出现在同一层上，且不带信息。,8.2.3 B-树,每一对(Ki ,Ri)形成一个索引项,例： 4（m = 4） 阶 B-树。,1,35,1,18,1,11,1,27,1,39,3,47,64,F,58,1,99,2,43,78,F,F,F,F,F,F,F,F,F,F,F,B-树是一个m叉平衡排序树。,

14、1,35,1,18,1,11,1,27,1,39,3,47,64,F,58,1,99,2,43,78,F,F,F,F,F,F,F,F,F,F,F,B-树的查找类似于二叉树的查找,二、B-树的查找,查找47,1,35,1,18,1,11,1,27,1,39,3,47,64,F,58,1,99,2,43,78,F,F,F,F,F,F,F,F,F,F,F,B-树的查找类似于二叉树的查找,二、B-树的查找,查找30,B-树查找算法,result srch_mbtree(mblink t; keytp k) /在B-树中查找k p=t; q=NULL; i=0; /初始化 while ( p ) i=S

15、earch(p,k); /在p-key1.n中进行查找, /直至p-keyi keyi+1 止, 00) return(q,i,0)/查找不成功, 返回插入位置信息 /srch_mbtree,三、B-树查找分析,B-树主要用作文件的索引，因此，它的查找涉及到外存的存取。,B-树通常存储在磁盘上。,从上述算法可知：在B-树上进行查找包含两种基本操作：(1)在B-树中找结点；(2)在结点中找关键字。,因此，第(1)步查找操作是在磁盘上进行的。第(2)是在内存中进行的。即在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于K的关键字。,显然，在磁盘上进行一次查

16、找比在内存中进行一次查找耗费时间多得多，因此，在磁盘上进行查找的次数、即待查关键字所在结点在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（

17、 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 = 3； 最多 3 次访问外存可找到所有的记录。,四、B-树的插入,1,35,1,18,1,11,2,27,1,39,3,47,64,F,58,1,99,2,43,78,F,F,F,F,F,F,F,F,F,F,F,F,30,注意：叶子要在同一层上。,插入,插入30,四、B-树的插入,1,35,1,18,1,11,2,27,1,39,3,47,64,F,58,1,99,2,43,78,F,F,F,F,F,F,F,F,F,F

18、,F,F,F,30,问题：若插入一元素时，使得某一结点m叉？ 例如插入60。 解决方法：分裂！将一个结点分成两个结点。,B-树插入举例：2-3树（3阶B-树）及插入。 （1）插入14；,B-树插入举例：2-3树（3阶B-树）及插入。 （2）插入55；,（3）插入19,例：2-3 树的删除操作。,3,24,45,53 90,37,100,50,61，70,删50,3,24,45,61 90,37,100,53,70,再删除53,3,24,45,90,37,100,61，70,再删除37,3，24,45,90,100,61，70,3，24,45 90,100,61，70,合并,合并,合并,五、B-树的删除,8.2.4 B+树 B+树是 B-树的变形树。在实现文件索引结构方法比B-树使用得更普遍。 m 阶 B+树与m阶B-树的差异在于： （1）有n个子树的结点中含有n个关键字； （2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接； （3）所有