《动态查找表详解》由会员分享，可在线阅读，更多相关《动态查找表详解（49页珍藏版）》请在金锄头文库上搜索。
1、8.2 8.2 动态查找表动态查找表 也即树表的查找。也即树表的查找。本节介绍一种以树的形式来组织查找表的方法，本节介绍一种以树的形式来组织查找表的方法，以实现动态高效率的查找。以实现动态高效率的查找。1、二叉排序树、二叉排序树2、平衡二叉树、平衡二叉树3、B树树4、B+树树8.2.1 二叉排序二叉排序树树一、二叉排序树的定义一、二叉排序树的定义BST: Binary Sort(Search) Tree 二叉排序树或空，或满足如下性质：二叉排序树或空，或满足如下性质：312376190784553100（1）有一个根，若根的左子树非空，则左）有一个根，若根的左子树非空，则左子树上所有结点的关键
2、字值均小于根结点的值子树上所有结点的关键字值均小于根结点的值24。若根的右子树非空，则右子树上的所有结点。若根的右子树非空，则右子树上的所有结点的关键字值均大于根结点的值。的关键字值均大于根结点的值。（2）左右子树同样是二叉排序树。）左右子树同样是二叉排序树。8.2.1 二叉排序二叉排序树树二、二叉排序树的特点二、二叉排序树的特点中序遍历得一有（升）序序列。中序遍历得一有（升）序序列。324123761907845531008.2.1 二叉排序二叉排序树树三、二叉排序树的查找三、二叉排序树的查找查找方法：查找方法：若根结点的关键字值等于查找的关若根结点的关键字值等于查找的关键字，查找成功。键字
3、，查找成功。32412376190784553100否则，若小于根结点的关键字值，否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字的查其左子树。若大于根结点的关键字的值，则查其右子树。值，则查其右子树。在左右子树上的操作类似。在左右子树上的操作类似。例例: 查找查找k=248.2.1 二叉排序树二叉排序树三、二叉排序树的查找三、二叉排序树的查找查找方法：查找方法：若根结点的关键字值等于查找的关若根结点的关键字值等于查找的关键字，查找成功。键字，查找成功。32412376190784553100否则，若小于根结点的关键字值，否则，若小于根结点的关键字值，查其左子树。若大于根结点的关
4、键字的查其左子树。若大于根结点的关键字的值，则查其右子树。值，则查其右子树。在左右子树上的操作类似。在左右子树上的操作类似。例例: 查找查找k=60结点结构及类型定义结点结构及类型定义lchild key rchild 1245533724619078100struct bnode keytype key;struct bnode *lchild;struct bnode *rchild;typedef struct bnode bstnode;3算法设计算法设计bstnode *bstsearch(bstnode *t, keytype K)45/ t:指向根结点指向根结点, k:待查找关键
5、字待查找关键字if (t=NULL | t-key= k) return(t)；3else if (t-key k) return(bstsearch(t-lchild,k);/ 在左子树上查找在左子树上查找/ 在右子树上查找在右子树上查找123724619053100else return(bstsearch(t-rchild,k); 78四、二叉排序树的插入四、二叉排序树的插入若二叉树为空。则生成根结点。若二叉树为空。则生成根结点。若二叉树非空若二叉树非空（1）首先执行查找算法，找出被插结点的）首先执行查找算法，找出被插结点的1232437614553100父结点。父结点。（2）判断被插结
6、点是其父结点的左、右儿）判断被插结点是其父结点的左、右儿子，子，将其作为叶子结点插入。将其作为叶子结点插入。609078例例1：在二叉排序树中插入：在二叉排序树中插入60四、二叉排序树的插入四、二叉排序树的插入若二叉树为空。则先生成根结点。若二叉树为空。则先生成根结点。若二叉树非空若二叉树非空（1）首先执行查找算法，找出被插结点的）首先执行查找算法，找出被插结点的4512375310061父亲结点。父亲结点。（2）判断被插结点是其父亲结点的左、右儿）判断被插结点是其父亲结点的左、右儿3子，子，将其作为叶子结点插入。将其作为叶子结点插入。249078例例2：以：以 45,53,12,37,24,
7、100,3,61,90,78 构造二叉排序树。构造二叉排序树。五、二叉排序树的查找分析五、二叉排序树的查找分析452412 375393122437455393ASL=(1+2+3+4+5+6)/6=21/6（2）以）以 12,24,37,45, 53, 93顺序建立二叉排序树。顺序建立二叉排序树。（1）以）以 45, 53, 24, 12, 93, 37顺序建立二叉排序树。顺序建立二叉排序树。ASL=(1+2+2+3+3+3)/6=14/6在一般情况下，在一般情况下，P（i）为具有）为具有 i 个结点二叉排序树的平均查找长度。个结点二叉排序树的平均查找长度。P（n,i）= 1+ ( P(i)
8、 + 1) * i + ( P(n-i-1) + 1) * (n-i-1) / nP（n）= P（n,i）/ ni=0n-1= 1.465log2n i个关键字个关键字第一个关键字第一个关键字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) 是具有是具有 3 个结点、个结点、2 个结点的个结点的二叉排序树的平均查找长度。二叉排序树的平均查找长度。 在一般情况下，在一般情况下，452412375393P（i）为具
9、有）为具有 i 个结点二叉排序树的平均查找个结点二叉排序树的平均查找 长度。长度。P(3) （1+2+2）/ 3 = 5/3P(2) （1+2）/ 2 = 3/2 六、二叉排序树的删除六、二叉排序树的删除451210061249078（1）删除叶子结点：直接删除。例如删除）删除叶子结点：直接删除。例如删除247832490451233753533761100六、二叉排序树的删除六、二叉排序树的删除4512100612490787832490451233753533761100（2）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空
10、。如 100六、二叉排序树的删除六、二叉排序树的删除451210061249078（2）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如）删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如 1003247845123375353619037六、二叉排序树的删除六、二叉排序树的删除45310061249078782490451233753533761100（3）删除子树的根结点且被删结点的左子树和右子树均不空。如）删除子树的根结点且被删结点的左子树和右子树均不空。如 12一般情况一般情况:被删结点被删结点FP删除方法（删除方法（1）PR删除方法（删除方法（1）删除方法（删除方法
11、（2）CCLFSSCCLPRCLFCQQLSLQQLSLQQLSLSPR8.2.2 平衡二叉平衡二叉树树(AVL 树树)一、什么是平衡二叉树一、什么是平衡二叉树平衡二叉树平衡二叉树(Balanced Binary Tree ) 又称又称AVL树。树。它或是空树，或是具有下列性质的它或是空树，或是具有下列性质的二叉排序树二叉排序树。它的左子树和右子树都是平衡二叉树，且左子树和右它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过子树的深度之差的绝对值不超过1。二、平衡因子二、平衡因子（Balance Factor)左子树的深度左子树的深度 - 右子树的深度右子树的深度即平衡
12、二叉树中每一结点的平衡因即平衡二叉树中每一结点的平衡因子为：子为：0，1，-1。00045240-15301237938.2.2 平衡二叉树平衡二叉树(AVL树树)三、平衡二叉树的查找三、平衡二叉树的查找平衡二叉树的查找方法平衡二叉树的查找方法与二叉排序树查找方法相同。与二叉排序树查找方法相同。00452400-1530123793四、平衡的二叉树的插入四、平衡的二叉树的插入（1）找插入位置；）找插入位置；（2）插入结点；）插入结点；（3）若插入后导致不平衡，则进行调整。）若插入后导致不平衡，则进行调整。045-11203024137-1610781900100插入插入 50045190-11
13、2030241370061500780100四、平衡的二叉树的插入四、平衡的二叉树的插入（1）找插入位置；）找插入位置；（2）插入结点；）插入结点；（3）若插入后导致不平衡，则进行调整。）若插入后导致不平衡，则进行调整。045-11203024137-1610781900100插入插入 15145190-212031240152370061500780100四、平衡的二叉树的插入四、平衡的二叉树的插入（1）找插入位置；）找插入位置；（2）插入结点；）插入结点；（3）若插入后导致不平衡，则进行调整。）若插入后导致不平衡，则进行调整。145-2120312401523706100451901900
14、100078LL旋转旋转-11203024003705001561078010050例：以例：以30,35,39,15,10,28,16,29,17建立平衡二叉树。建立平衡二叉树。平衡旋转平衡旋转1、LL旋转旋转LL旋转的结果旋转的结果平衡旋转平衡旋转2、RR旋转旋转RR旋转的结果旋转的结果平衡旋转平衡旋转3. LR旋转旋转LR旋转后旋转后平衡旋转平衡旋转4. RL旋转旋转再左旋再左旋五、平衡二叉排序树的查找分析五、平衡二叉排序树的查找分析T1T2T3T4Th : 高度高度 h 结点个数最少的结点个数最少的AVL树树左子树为左子树为 Th1 右子树为右子树为Th2Th-1Th-2五、平衡二叉排
15、序树的查找分析五、平衡二叉排序树的查找分析设以设以Nh表示深度为表示深度为h的二叉平衡树中的最少结点数。的二叉平衡树中的最少结点数。显然，显然，N0=0, N1=1, N2=2Nh=Nh-1+Nh-2+1可以证明，可以证明，n个结点的个结点的AVL树的最大深度为：树的最大深度为：log (5 (n+1) ) - 2。其中，其中，=(1+ 5 )/2每一对每一对(Ki ,Ri)形成一个索引项形成一个索引项8.2.3 B-树树一、一、B-树的定义树的定义m 阶阶 B-树满足或空，或满足树满足或空，或满足（1）树中每个结点最多有）树中每个结点最多有m个子树个子树 ；（2）若根结点不是叶子结点，则至少
16、有）若根结点不是叶子结点，则至少有2个子树；个子树；（3）除根结点外的所有非叶子结点至少有）除根结点外的所有非叶子结点至少有m/2 个子树；个子树；（4）所有的非叶子结点中包含的数据信息为：）所有的非叶子结点中包含的数据信息为：(n,A0,K1,R1,A1,K2,R2,A2, ,Kn,Rn,An）其中，其中，n: 关键字的个数关键字的个数Ki：关键字：关键字Ri：关键字：关键字 = Ki 的数据记录在硬盘中的地址的数据记录在硬盘中的地址Ai： Ki且且 Ki+1 的结点地址的结点地址K1 =K2 = . = Kn, A0：key1.n中进行查找, /直至p-keyi = k keyi+1 止,
17、 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-树上进行查找包含树上进行查找包含两种两种基本操作：基本操作：(1)在在B-树中找树中找结点；结点；(2)在结点中找关键字。在结点中找关键字。因此，第因此，第(1)步查找操作是在
18、磁盘上进行的。第步查找操作是在磁盘上进行的。第(2)是在内存中进行的。是在内存中进行的。即在磁盘上找到指针即在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于利用顺序查找或折半查找查询等于K的关键字。的关键字。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，因此，在磁盘上进行查找的次数、即待因此，在磁盘上进行查找的次数、即待查关键字所在结点在查关键字所在结点在B-树上的层次树上的层次数，是决定数，是决定B-树查找效率的首要因素。树
19、查找效率的首要因素。考虑最坏情况，考虑最坏情况，即待查结点在即待查结点在B-树上的最大层次数，即含树上的最大层次数，即含N个关键字的个关键字的m阶阶B-树的最大深度是多少？树的最大深度是多少？三、三、B-树查找分析树查找分析设关键字的总数为设关键字的总数为 N ，求，求 m阶阶 B-树的最大层次树的最大层次 L。层次层次1234LL+1结点数结点数122（m/2 ）2（m/2 ）22（m/2 ）L-22（m/2 ）L-1 设设 N 1000000 且且 m256 ，则，则 L m叉？叉？例如插入例如插入60。解决方法：分裂！将一个结点分成两个结点。解决方法：分裂！将一个结点分成两个结点。B-树
20、插入举例：树插入举例：2-3树（树（3阶阶B-树）及插入。树）及插入。（1）插入）插入14；B-树插入举例树插入举例：2-3树（树（3阶阶B-树）及插入。树）及插入。（2）插入）插入55；（3）插入）插入19五、五、B-树的删除树的删除例：例：2-3 树的删除操作。树的删除操作。452453 90244561 903375061，701003375370100删删50合并合并452490合并合并再删除再删除534590合并合并45 9033761，701003，2461，701003，2461，70100再删除再删除37+8.2.4 B 树树B+树是树是 B-树的变形树。树的变形树。在实现文件
21、索引结构方法比在实现文件索引结构方法比B-树使树使用得更普遍。用得更普遍。m 阶阶 B+树与树与m阶阶B-树的树的差异差异在于：在于：（1）有）有n个子树的结点中含有个子树的结点中含有n个关键字；个关键字；（2）所有的）所有的叶子结点中包含了全部关键字的信息叶子结点中包含了全部关键字的信息，及指向，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；自小而大顺序链接；（3）所有的非终端结点可以看成是）所有的非终端结点可以看成是索引部分索引部分，结点中仅含，结点中仅含有其子树（根结点）中的最大（或最小）关键字。有其子树（
22、根结点）中的最大（或最小）关键字。索引索引B+树树顺序索引顺序索引集合起点集合起点索引索引集合集合顺序索顺序索引集合引集合数据数据集合集合B+树举例树举例(2-3树树)59 9715 44 59 72 9710 1521 37 4451 59 63 7285 91 97+B 树的查找。树的查找。(1) key=37 ; 59 9715 44 59 72 9710 1521 37 4451 59 63 7285 91 97思考：思考：(2) key=59？(3) key=69？+(1) 快速查找快速查找B 树的两种查找方法：树的两种查找方法：root59 9715 44 59 72 97sqt1
23、0 1521 37 4451 59 63 7285 91 97(2) 顺序查找顺序查找+B 树的插入。树的插入。(1) key=69 ; 59 9715 44 59 72 9710 1521 37 4451 59 63 7269插入插入85 91 97+B 树的插入。树的插入。(2) key=79 ; 59 9715 44 59 72 9710 1521 37 4451 59 63 726985 91 97插入插入+B 树的插入。树的插入。(2) key=79 ; root59 9715 44 59 72 85 9710 1521 37 4451 59 63 7269798591 9791 97分裂！分裂！
