第8章查找技术.ppt

数据结构与算法 作 者：胡明 王红梅 出版社：电子工业出版社 邮 箱：wanghm@mail.ccut.edu.cn 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 B 树——查找操作 21 182133 2123 比较次数不超过树的深度。 8.3 树表的查找技术 B 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 叶子结点只包含1个记录 插入新记录 14 8.3 树表的查找技术 B 树——插入操作 新记录将插入到相应的叶子结点中。 叶子结点只包含1个记录 插入新记录 18 33 12 23 30 48 15 20 21 24 31 45 47 50 52 10 14 8.3 树表的查找技术 B 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 叶子结点只包含2个记录 插入新记录，分裂－提升 55 8.3 树表的查找技术 B 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 55 叶子结点只包含2个记录 插入新记录，分裂－提升 插入 8.3 树表的查找技术 B 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 叶子结点只包含2个记录 插入新记录，分裂－提升 分裂 50 55 52 8.3 树表的查找技术 B 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 10 15 20 21 24 31 45 47 叶子结点只包含2个记录 插入新记录，分裂－提升 提升 50 55 48 52 8.3 树表的查找技术 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 B 树——删除操作 情况1：从包含2个记录的叶子结点删除1个记录。 解决方法：直接删除这个记录。 8.3 树表的查找技术 18 33 12 23 30 48 10 15 24 31 45 47 50 52 B 树——删除操作 情况1：从包含2个记录的叶子结点删除1个记录。 解决方法：直接删除这个记录。 21 8.3 树表的查找技术 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 B 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。 8.3 树表的查找技术 18 33 12 21 30 48 10 15 20 23 31 45 47 50 52 B 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。 8.3 树表的查找技术 18 33 12 21 30 48 10 15 20 23 31 45 47 50 52 B 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 8.3 树表的查找技术 18 33 12 20 21 48 10 15 30 31 45 47 50 52 B 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 8.3 树表的查找技术 18 33 12 20 21 48 10 15 30 31 45 47 50 52 B 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 8.3 树表的查找技术 20 21 48 33 31 45 47 50 52 B 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 10 12 18 30 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 8.3 树表的查找技术 48 33 30 45 47 50 52