【数据结构】败者树的建树与比较过程

2023-11-03 00:20

本文主要是介绍【数据结构】败者树的建树与比较过程,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 前置知识
      • 归并段
    • 建树过程
    • 比较过程
    • 疑问
      • 为什么比较次数减少了?
      • 如果某个归并段的元素一直获胜,没有元素了怎么办?
        • 处理方法 1
        • 处理方法 2

前置知识

归并段

  • 外部排序算法通常用于处理大规模数据,其中数据量远超过计算机内存的容量。由于内存无法一次性容纳全部数据,因此需要将数据划分为较小的片段进行排序,在排序过程中将这些片段合并成一个有序的序列
  • 这些归并段内部是有序的,各个归并段之间无序
  • 如图,有 3 个归并段,内部升序
    在这里插入图片描述

建树过程

  • 假设有 5 个节点,给这些节点编号
    在这里插入图片描述

  • 17 是 0 号节点,5 是 1 号节点,…,15 是 4 号节点

  • 为每个节点创建一个根节点,根节点的值是其编号,叶子节点是值
    在这里插入图片描述

  • 从子树中任意挑选两个子树的根节点进行比较,比较对应的值,假设比较规则是:值小的胜出
    本例中,初始有 5 棵子树

  • 比较顺序是任意的,假设根节点为 0 和 1 对应子树进行比较,取出根节点对应的值,5 < 17,5 胜出

    • 除去两棵子树的根节点后,胜者的根节点作为两棵子树的爷节点,败者的根节点作为两棵子树的父节点
    • 即 0 作为父节点,1 作为爷节点

    在这里插入图片描述

  • 比较根节点为 3 和 4 对应子树,取出根节点对应的值,15 < 29,15 胜出
    3 作为父节点,4 作为爷节点
    在这里插入图片描述

  • 比较根节点为 1 和 2 对应的子树,5 < 10,5 胜出
    1 作为爷节点,2 作为父节点
    在这里插入图片描述

  • 比较根节点为 1 和 4 对应的子树,5 < 15,5 胜出
    1 作为爷节点,4 作为 父节点
    在这里插入图片描述

  • 可以看出,根节点是 1,其对应的值是 5,也就是{17, 5, 10, 29, 15} 中的最小值,共比较 4 次
    败者树构建完成

比较过程

  • 将根节点对应的值进行输出,假设编号 1 所在的归并段还有元素需要比较,是 44

  • 败者树需要调整,将根节点重新和编号 1 对应的值进行组合
    在这里插入图片描述

  • 根节点为 0 和 1 的子树进行比较,17 < 44,17 胜出
    0 作为爷节点,1 作为父节点
    在这里插入图片描述

  • 根节点为 0 和 2 的子树进行比较,10 < 17,10 胜出

    2 作为爷节点,0 作为父节点在这里插入图片描述

  • 根节点为 2 和 4 的子树进行比较,10 < 15,10 胜出

    2 作为爷节点,4 作为父节点

    在这里插入图片描述

  • 可以看出,根节点是 2,其对应的值是 10,也就是{17, 44, 10, 29, 15} 中的最小值,共比较 3 次,比建树时找到最小值所需的比较次数(5次)少

疑问

为什么比较次数减少了?

  • 在刚才的例子中,44 没有和 4 的右子树进行比较,这是为什么呢?
    在这里插入图片描述
    • 败者树中,两棵子树的合并规则是:胜者根节点做爷节点,败者做父节点
      因此,编号 3 是败者,编号 4 是胜者

    • 新节点 x 只需要和胜者 y 比较即可

      • 若 x < y,那么 x 可以做根节点,而 y 做父节点
      • 反之 y 做根节点,而 x 做父节点
    • 换句话说,在设定的比较规则中(值小的获胜),我们只关心获胜者(谁是最小的),而不关心节点比哪些节点大

      • 有 2 个集合 A,B,我们想找到两个集合的最小值
        A 集合的最小值是 x
        B 集合的最小值是 y

        显然,要选出最小值,只要比较 x 和 y 即可,若 x < y,那么 x 就是 A 和 B 中最小的,y 比 A 中的哪些元素小,我们并不关心在这里插入图片描述

如果某个归并段的元素一直获胜,没有元素了怎么办?

处理方法 1
  • 记录归并段的元素个数,若某个归并段没有元素,则在输出其根节点对应的值后,移除这课子树

  • 编号 1 对应的归并段没有元素了,那么输出 5,并移除 5 对应的子树,移除后的败者树被破坏了
    在这里插入图片描述

  • 0 和 2 需要重新比较
    在这里插入图片描述

  • 2 和 4 重新比较
    在这里插入图片描述

  • 败者树又构建好了(ヾ(•ω•`)o)
    在这里插入图片描述

处理方法 2
  • 可以填充一个“最大值”,保证所有元素都比最大值小,那么这个最大值就不会在接下来的比较中胜出

  • 1 对应的 5 输出,而 1 合并的是 2 和 4

在这里插入图片描述

  • 假设 999 是最大的值了,类似方法 1,调整一下败者树的结构

在这里插入图片描述
2 对应的 10 是 {17, 999, 10, 29, 15} 中的最小值

这篇关于【数据结构】败者树的建树与比较过程的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/334281

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

JSON Web Token在登陆中的使用过程

《JSONWebToken在登陆中的使用过程》:本文主要介绍JSONWebToken在登陆中的使用过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录JWT 介绍微服务架构中的 JWT 使用结合微服务网关的 JWT 验证1. 用户登录,生成 JWT2. 自定义过滤

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

SpringCloud之LoadBalancer负载均衡服务调用过程

《SpringCloud之LoadBalancer负载均衡服务调用过程》:本文主要介绍SpringCloud之LoadBalancer负载均衡服务调用过程,具有很好的参考价值,希望对大家有所帮助,... 目录前言一、LoadBalancer是什么?二、使用步骤1、启动consul2、客户端加入依赖3、以服务

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

Spring Security注解方式权限控制过程

《SpringSecurity注解方式权限控制过程》:本文主要介绍SpringSecurity注解方式权限控制过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、摘要二、实现步骤2.1 在配置类中添加权限注解的支持2.2 创建Controller类2.3 Us

Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

《SpringAI集成DeepSeek三步搞定Java智能应用的详细过程》本文介绍了如何使用SpringAI集成DeepSeek,一个国内顶尖的多模态大模型,SpringAI提供了一套统一的接口,简... 目录DeepSeek 介绍Spring AI 是什么?Spring AI 的主要功能包括1、环境准备2

SpringBoot集成图片验证码框架easy-captcha的详细过程

《SpringBoot集成图片验证码框架easy-captcha的详细过程》本文介绍了如何将Easy-Captcha框架集成到SpringBoot项目中,实现图片验证码功能,Easy-Captcha是... 目录SpringBoot集成图片验证码框架easy-captcha一、引言二、依赖三、代码1. Ea