数据结构 9查找B

1、1 基本概念基本概念 9.1 9.1 静态查找表静态查找表 9.2 9.2 动态查找表动态查找表 9.3 9.3 哈希查找表哈希查找表 教材第教材第8 8、1111和和1212章省略，因章省略，因操作系统操作系统课程会涉及。课程会涉及。 2 特点：特点： 一、一、二叉排序树的定义二叉排序树的定义 二、二、二叉排序树的插入与删除二叉排序树的插入与删除 三、二叉排序树的查找分析三、二叉排序树的查找分析 四、平衡二叉树四、平衡二叉树 五五、B-B-树和树和B+B+树树 9.2 9.2 动态查找表动态查找表 表结构在查找过程中动态生成。表结构在查找过程中动态生成。 要求：要求： 对于给定值对于给定值k

2、ey,key, 若表中存在其关键字等于若表中存在其关键字等于keykey的记录，则查找成功返回；的记录，则查找成功返回； 典型的动态表典型的动态表二叉排序树二叉排序树 3 平衡二叉树又称平衡二叉树又称AVL树，它是具有如下性质的树，它是具有如下性质的 二叉树：二叉树： 为了方便起见，给每个结点附加一个为了方便起见，给每个结点附加一个数字数字，给，给 出出该结点左子树与右子树的高度差该结点左子树与右子树的高度差。这个数字。这个数字 称为结点的称为结点的平衡因子平衡因子balance。这样，可以得到这样，可以得到 AVL树的其它性质：树的其它性质： 即即| |左子树深度左子树深度- -右子树深度右

3、子树深度| 1| 1 左、右子树是平衡二叉树；左、右子树是平衡二叉树； 所有结点的左、右子树深度之差的绝对值所有结点的左、右子树深度之差的绝对值 1 4 (a) (a) 平衡树平衡树 (b) (b) 不平衡树不平衡树 例：判断下列二叉树是否例：判断下列二叉树是否AVL树？树？ v任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1、0 或或 1；如果；如果 树中任意一个结点的平衡因子的绝对值大于树中任意一个结点的平衡因子的绝对值大于1， 则这棵二叉树就失去平衡，不再是则这棵二叉树就失去平衡，不再是AVL树；树； v对于一棵有对于一棵有n个结点的个结点的AVL树，其树，其高度保持在高度保持在

4、 O(log2n)数量级，数量级，ASL也保持在也保持在O(log2n)量级。量级。 0 0 0 1 1 1 1-1 -1 0 0 0 1 -1 5 如果在一棵如果在一棵AVL树中插入一个新结点，就有可能树中插入一个新结点，就有可能 造成失衡，此时必须造成失衡，此时必须重新调整树的结构重新调整树的结构，使之恢，使之恢 复平衡。我们称调整平衡过程为复平衡。我们称调整平衡过程为平衡处理平衡处理。 现分别介绍这四种平衡处理。现分别介绍这四种平衡处理。 平衡处理可以归纳为四类：平衡处理可以归纳为四类： v LL平衡处理平衡处理 v RR平衡处理平衡处理 v LR平衡处理平衡处理 v RL平衡处理平衡处

5、理 6 0 0 1 13 3 0 0 3737 0 0 2424 例：例：请将下面序列构成一棵请将下面序列构成一棵平衡二叉排序树平衡二叉排序树： （ 13，24，37，90，53） 0 0 1313 0 0 3737 -1-1 1313 0 0 2424 -1-1 2424 1313 需要需要RR平衡处理平衡处理 (绕绕B左旋左旋,B为根）为根） 0 0 9090 -1-1 2424 -1-1 3737 0 0 5353 1 1 9090 3737 需要需要RL平衡旋转平衡旋转 (绕绕B先右旋后左旋）先右旋后左旋） 0 0 3737 0 0 9090 0 0 5353 0 0 3737 0 0

6、 9 90 0 0 0 5353 7 若在若在A的的左子树的左子树上插入左子树的左子树上插入 结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至 2，需要进行一次，需要进行一次顺时针旋转顺时针旋转。 (以以B为旋转轴）为旋转轴） 若在若在A的的右子树的右子树上插入右子树的右子树上插入 结点，使结点，使A的平衡因子从的平衡因子从-1增加增加 至至-2，需要进行一次，需要进行一次逆时针旋转逆时针旋转。 (以以B为旋转轴）为旋转轴） 8 若在若在A的的右右子树的子树的左左子树上插入子树上插入结结 点，使点，使A的平衡因子从的平衡因子从-1增加至增加至-2， 需要需要先进行先进行顺顺时针旋转，再

7、时针旋转，再逆逆时时 针旋转针旋转。 (以插入的结点以插入的结点C为旋转轴）为旋转轴） 若在若在A的的左左子树的子树的右右子树上插入子树上插入 结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至 2，需要，需要先进行先进行逆逆时针旋转，再时针旋转，再 顺顺时针旋转。时针旋转。 (以插入的结点以插入的结点C为旋转轴）为旋转轴） 这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变 9 1 Status InsertAVL(Tbf=EH; t=1; /当前树空 9 else /当前树根就是要找的 if (e.key = Tdata.key) t=0; return

8、 0; 12 if (e.key = Tdata.key) /进入左子树 13 if (!InsertAVL(Tlchild, e, t) return 0; 14 if (t) 16 LH: LeftBalance(T); t=0; else /进入右子树 25 if (!InsertAVL(Trchild, e, t) return 0; 26 if (t) 28 LH: Tbf=EH; t=0; 30 EH: Tbf=RH; t=1; 32 RH: RightBalance(T); t=0; 37 return 1; 0 0 1313 0 0 3737 -1-1 13131313 0 0

9、 2424 -1-1 2424 In(13, 37, 0) 25 In(24, 37, 0); 26/32 RightBalance(13); t=1; 37 return 1; In(24, 37, 0) 25 In(Null, 37, 0); 26/30 T=24;RH; t=1; 37 return 1; 10 五、五、B-树树 1定义定义 2查找过程查找过程 3插入操作插入操作 4删除操作删除操作 5查找性能的分析查找性能的分析 11 1B-树的定义树的定义 B-树是一种 平衡平衡 的 多路多路 查找查找 树： 12 平衡树(BF=0) 根结点或为叶子结点，或至少含有两棵 子树； 其余

10、所有非叶结点均至少含有m/2棵子 树，至多含有 m 棵子树； 树中所有叶子结点均不带信息，且在树 中的同一层次上； 13 非终端结点包含(n,A0, K1, A1, K2, A2, Kn, An ) 多个关键字多个关键字均自小至大自小至大有序排列，即：K1 K2 keynum; i=Search(p, K); / 在p-key1.keynum中查找 i ， p-keyi=Kkeyi+1 if (i0 else q=p; p=p-ptri; / q 指示 p 的双亲 if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功 19

11、 在查找不成功之后，需进行插入。 显然，关键字插入插入的位置位置必定在最下最下 层的非叶结点层的非叶结点，有下列几种情况： 3插入插入 1）插入后，该结点的关键字个数nm， 不修改指针; 例如 20 2）插入后，该结点的关键字个数 n=m， 则需进行“结点分裂”，令 s = m/2， 在原结点中保留 （A0，K1， ， Ks-1，As-1）； 建新结点 （As，Ks+1， ，Kn，An）； 将（Ks，p）插入双亲结点；例如 3）若双亲为空，则建新的根结点。 例如 21 例如:下列为 3 阶B-树(子树个数为2或3， 故又称2-3树) 50 20 40 80 插入关键字 = 60, 60 80

12、90, 60 80 90 90 50 80 60 30, 40 20 30 50 80 80 30 50 22 被删结点不是最下层结点，借被删关键字的右子树中的 最小关键字； 被删结点为最下层结点，（1）它的关键字个数不少， 删除该关键字即可；（2）它的关键字个数不能减少： 要从其左(或右)兄弟结点“借”关键字，无关键字可借 时就进行结点“合并”： （2.1）“有的借”左（右）兄弟结点中最大（最小） 的关键字上移至双亲，双亲结点中大于（小于）上 移关键字的关键字下移至被删结点； （2.2）“没的借合并”把被删结点与其左（右）兄弟 结点以及双亲结点中分割二者的关键字合并在一起。 4删除删除保证关

13、键字的个数不能小于m/2-1 23 在B-树中进行查找时，其查找时间 主要花费在搜索结点（访问外存）上， 即主要取决于B-树的深度树的深度。 5查找性能的分析查找性能的分析 问：含 N 个关键字的 m 阶 B-树可 能达到的最大深度 H 为多少？ 24 第第 2 层层 2 个个 先推导每一层所含最少结点数： 第第 1 层层 1 个个 第第 H+1 层层 2 ( m/2 ) H-1 个个 第第 4 层层 2 ( m/2 )2 个个 第第 3 层层 2m/2 个个 反过来问： 深度为H的B-树中， 至少含有多少个结点？ 25 假设 m 阶 B-树的深度为 H+1，由于 第 H+1 层为叶子叶子结点

14、，而当前树中含有 N 个关键字，则叶子结点必为 N+1 个， N+12( m/2 )H-1 H-1log m/2 (N+1)/2) Hlog m/2 (N+1)/2)+1 由此可推得下列结果： 26 在含在含 N 个关键字的个关键字的 B-树上树上 进行一次查找，需访问的结点进行一次查找，需访问的结点 个数不超过个数不超过 log m/2 (N+1)/2)+1 结论：结论： 27 是是B-树的一种变型树的一种变型 四、四、B+树树 28 1B+树的结构特点：树的结构特点： 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子叶子 结点彼此相链接链接构成一个有序链表，其 头指针指向含最小关键字的结点； 29 50 96 15 50 62 78 96 71 788 4 8 9 96 56 6220 26 43 50 3 8 15 sq root 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子 树中关键字的最大值； 所有叶子结点都处在同一层次 上，