《动态查找表详解》由会员分享，可在线阅读，更多相关《动态查找表详解（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,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=Search(p,k); /在p-key1n中进行查找, /直至p-keyi keyi+1 止, 00) return(q,i,0)/查找不成功, 返回插入位置信息 /srch_mbtree,三、B-树查找分析,B-树主要用
