数据结构第九章查找案例.pptx

1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20;21;22;23;24;25;26;27;28;29;30;31;讨论：当有序表中各记录的查找概率不相等时，该如何查找？;33;34;35;36;37;38;39;40;41;42;43;对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，要求删除后仍需保持二叉排序树的特性。;45;46;47;48;49;50;9.3.4 二叉排序树操作代码;52;53;54;55;56;57;58;59;建立平衡二叉树旋转注意要点;61;62;63;64;65;66;67;68;69;70;71;72;73;74;75;76;77;78;79;80;81;82;83;84;85;86;87;88;89;90;91;92;9.4.5 哈希应用;9.4.5 哈希应用;95;96;97;98;99;9.5 B-树和B+树;9.5.1 B-树 ;4．所有的非终端结点中包含下列信息数据： (n, A0, K1, A1, K2, A2, … , Kn, An) 其中：Ki(i = 1, … , n)为关键字，且Ki Ki+1(i = 1, … , n-1)； Ai(i = 1, … , n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i = 1, … , n)，An所指子树中所有结点的关键字均大于Kn， n 为关键字的个数（或n＋1为子树个数）。;5．所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是 外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。;二、图形表示 ; 从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程交叉进行。;;;四、 B-树的查找;四、 B-树的查找;3．查找分析 ; 根据B-树的定义，第一层至少有1个结点；第二层至少有2个结点；;3．查找分析 ;五、 B-树的插入 ;五、 B-树的插入 ;五、 B-树的插入 ;3．例子 例如，图2所示为3阶B-树（图中略去F结点，即叶子结点），假设需一次插入关键字30，26，85和7。 ;;;;;(f);(g);(h);;(j); 六、 B-树的删除;;;;;;;;;;9.5.2 B＋树;3.所有的非终端结点可以看成是索引部分，结点中仅含其子树 （根结点）中的最大（或最小）关键字。;2 图形表示;3、B＋树的查找 对B＋树可以进行两种查找运算： 1.从最小关键字起顺序查找； 2.从根结点开始，进行随机查找。;4 B＋树的插入 ;5 B＋树的删除;实验;143;144