首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >距离树中另一个节点最远的节点

距离树中另一个节点最远的节点
EN

Stack Overflow用户
提问于 2013-11-10 03:10:36
回答 1查看 1.9K关注 0票数 6

如果输入一棵树,我们需要回答类型的查询,

a)给出了上述树的一个节点,该节点是距离该节点最远的节点。

b)从树中移除一组特定的边缘。

我已经尝试了很长一段时间了,但我能想到的最好的解决办法是,

对于a类型的查询,调用dfs函数将返回O(N)中最远的节点,但我需要做得更好。对于b类型的查询,如果存在,只需更新树删除边缘即可。

因此,我上面的解决方案大致是O(K*N),其中K是查询的数量,N是节点的数量。

EN

回答 1

Stack Overflow用户

发布于 2013-11-10 05:02:02

因为您的树是一棵通用树,也就是说,它没有平衡的概念,甚至没有根,所以一次性查询所能做的最好是O(n)。但是,我认为您可以使用O(n)时间设置一次树,然后让下面的每个查询都保持恒定的时间。

其思想是找出树的“中间”,它将树分成大小大致相等的树,称这些部分是任意的,例如左和右。然后,将它们各自部分中的所有节点标记为它们所在的部分,并存储一个离中间最远的左节点和右节点。当您得到一个节点的查询时,只需查看节点的标签,并在另一侧报告存储的节点。

考虑到这一评论和不必要的否决,看来解决方案需要更多的解释。首先,对于给定节点来说,最遥远的节点通常并不是唯一的。例如,设想一条有三个节点的路径。中间节点有两个距离最远的节点。其中任何一个都是解决之道。基于此,我们的思想是在树中找到一个节点,该节点位于树中两个最相距节点之间的路径中间(这些节点之间的距离是奇数的,可以选择两边的一个节点,使得距离仅相差一个):如果距离最远的节点距离为l个节点,则中间节点有一条长度为l/2到两者的路径,或者1/2到1的路径,另一条路径为l/2+1。

使用这个中间节点将树分成两部分,随机地称为左和右,如果每个节点都知道它是在左边还是右边,那么就可以确定每个节点的最遥远的节点:最长的路径将穿过中间节点进入另一半,从中间到离中间最远的节点。让我们调用左侧第11部分中最长路径的长度和右侧lr部分中最长路径的长度。在不失去通用性的情况下,有lr < ll (只需交换周围的名称)。与中间相距最远的节点称为nl和nr。请注意,如果中间节点中有多个子树,只要其中一个最长路径(或者是唯一的最长路径)位于左侧,则该子树被认为是右侧部分的一部分。

当您想要说明与节点n相距最远的节点时,有三种情况需要考虑。

  1. 节点n是中间节点。在这种情况下,最遥远的节点显然是nl。
  2. 节点n位于树的右侧。您可以构造的最长路径是中间,然后是nl,也就是说,距离最远的节点显然也是nl。
  3. 节点n位于树的左侧。再一次,你能建造的最长的路径是从中间到nr的。

剩下的唯一问题是如何在O(n) time中找到中间节点:

  1. 找到所有的叶节点,并将它们放入队列,用1标记它们,并给它们一个0的距离。这可以在O(n)的时间和空间内完成。
  2. 从队列中读取第一个节点(但不要额外),并找到所有相邻节点。如果有一个节点的标签小于其相邻节点的数目,则增加该标签。如果标签现在匹配相邻节点的数量,那么将节点添加到队列中,并给它一个比队列中的第一个节点更大的距离。
  3. 如果队列中只有一个节点,则此节点为中间节点,此步骤终止。
  4. 否则,提取前端节点并继续处理队列(即步骤2)。

最后一次传递,找到具有最大距离标签的相邻节点,并将该节点上的树挂在左边的树上。在用BFS标记节点为左节点的同时,跟踪队列中的最后一个节点以找到nl。考虑所有其他子树--正确的树--并将它们标记为BFS,作为正确的节点,也可以找到nr。

我想,树的预处理可以做得更优雅,可能也需要很少的传球,但我相信上面的方法确实有效。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/19888999

复制
相关文章
shell 开始日期 结束日期循环
shell 日期循环 #!/bin/sh if [ $# == 2 ]; then datebeg=$1 dateend=$2 else echo "请输入开始时间和结束日期,格式为2017-04-04" exit 1 fi beg_s=`date -d "$datebeg" +%s` end_s=`date -d "$dateend" +%s` echo "处理时间范围:$beg_s 至 $end_s" while [ "$beg_s" -le "$end_s"
大数据工程师-公子
2019/03/14
2.8K0
当前日期得到本周的开始和结束日期
本文由来源 21aspnet,由 javajgs_com 整理编辑,其版权均为 21aspnet 所有,文章内容系作者个人观点,不代表 Java架构师必看 对观点赞同或支持。如需转载,请注明文章来源。
Java架构师必看
2021/03/22
2.8K0
js根据年月获取这月或者年的开始日期和结束日期
获取月的: //获取这个月的月初和月末 function getMonthStartEnd(vars){ var str = ''; if(vars!=null&&vars!=''){ var nyYear=vars.slice(0,4); var nyMonth=vars.slice(4,vars.length); var firstDay = new Date(nyYear,nyMonth-1); var lastDay =
tongyao
2022/06/09
5.5K0
bootstrap 日期控件起始日期&结束日期相互约束
使用bootstrap的日期控件需要单独引入bootstrap-datetimepicker.min.css和bootstrap-datetimepicker.min.js 详情及文件可以通过下面地址下载:http://www.bootcss.com/p/bootstrap-datetimepicker/index.htm
程序新视界
2022/05/06
3K0
bootstrap 日期控件起始日期&结束日期相互约束
Power Pivot智能日期运用——当前初始日期/当前结束日期
(六) 当前初始日期 1. OPENINGBALANCEMONTH/ OPENINGBALANCEQUARTER/ OPENINGBALANCEYEAR A) 语法 OpeningBalanceMonth (<expression>, <dates> [, <filter>]) OpeningBalanceQuarter (<expression>, <dates> [, <filter>]) OpeningBalanceYear (<expression>, <dates> [, <filter>] [,
逍遥之
2020/03/24
2.7K0
Power Pivot智能日期运用——当前初始日期/当前结束日期
VBA: DTPicker日期控件的使用
文章背景:最近在查看同事写的VBA代码时,发现了DTPicker日期控件。DTPicker是日期选择控件,自Win7开始,它就不是Windows系统自带的,需要下载MSCOMCT2.OCX,并在电脑上注册后才能使用。
Exploring
2022/09/20
9.5K0
VBA: DTPicker日期控件的使用
js获取上周、本周、上月、本月、上季度、本季度的开始日期、结束日期(无bug)
/** * 获取上周、本周、上月、本月、上季度、本季度的开始日期、结束日期 start * 亲测无bug。获取上月开始结束日期考虑了年份的变化 */ var now = new Date(); //当前日期 var nowDayOfWeek = now.getDay()-1; //今天本周的第几天 var nowDay = now.getDate(); //当前日 var nowMonth = now.getMonth(); //当前月 var nowYear = now.getYear(); //当
用户1065635
2019/11/27
7.1K0
shell日期循环[通俗易懂]
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/163978.html原文链接:https://javaforall.cn
全栈程序员站长
2022/09/15
5620
VBA代码库12:处理日期和时间
本文中的代码来自于www.cpearson.com,特辑录于此,方便在需要时参考。
fanjy
2021/07/12
1.8K0
时间序列 | 从开始到结束日期自增扩充数据
糖尿病是全球最常见的慢性非传染性疾病之一。流行病学调查显示,我国约11%的成年人患有糖尿病,而在住院患者中这一比例更高。
数据STUDIO
2021/06/24
3K0
pands中的日期和时间操作
其中,Date Time用于表示某个具体的时间点,Time spans用于生成时间间隔相同的时间序列;Time deltas表示时间间隔,Date offsets则表示日期间隔,这二者的作用都是用于时间运算,通过时间点+时间间隔的方式,得到新的时间点。
生信修炼手册
2020/07/16
2.1K0
SQL 中的日期和时间类型
在我们SQL中一般支持三种数据类型。 date:日历日期,包括年(四位),月和日。 time: 一天中的时间,包括小时,分和秒。可以用变量time(p)来表示秒的小数点后的数字位数(默认是0)。 通过制定 time with timezone,还可以把时区信息连同时间一起存储。 timestamp: date 和 time的组合。 可以用变量timestamp(p)来表示秒的小数点后的数字位数(这里默认值为6)。如果指定with timezone,则时区信息也会被存储 日期和时间类型的值可按如下方式说明:
Dato
2018/04/17
3.2K0
Java中的时间和日期处理
本文主要讲解Java 8的时间处理方式和Java8之前版本的时间处理方式的区别。笔者将Java8之前的jdk版本统称为旧版本。
栋先生
2018/09/29
2.7K0
Java中的时间和日期处理
js根据起始日期加间隔天数计算出结束日期
getNewDay(dateTemp, days) { dateTemp = dateTemp.split("-"); //转换为MM-DD-YYYY格式 var nDate = new Date(dateTemp[1] + "-" + dateTemp[2] + "-" + dateTemp[0]); var millSeconds = Math.abs(nDate) + days * 24 * 60 * 60 * 1000; var rDa
Wyc
2023/03/23
6.2K0
js根据起始日期加间隔天数计算出结束日期
Flutter中的日期、格式化日期、日期选择器组件在
所谓时间戳,是指自格林威治时间1970年01月01日00时00分00秒(北京时间1970年01月01日08时00分00秒)起至现在的总秒数。
拉维
2019/08/29
26.1K0
Flutter中的日期、格式化日期、日期选择器组件在
ElasticSearch里面关于日期的存储方式
在ElasticSearch里面最常用的就是时间字段了,经常会在群里看到一些小伙伴提出有关时间的问题,为什么es查询的时间跟我实际看到的时间差8个小时呢。如果我们了解了ElasticSearch底层的时间存储方式就会比较容易的理解这个问题。 下面散仙先普及下时区的知识,想必大家也不陌生学过地理的同学都知道全球有24个时区每个时区的跨度是经度15度, 相较于两地时间表,可以显示世界各时区时间和地名的世界时区表(World Time),就显得精密与复杂多了,通常世界时区表的表盘上会标示着全球2
我是攻城师
2018/05/14
2.4K0
Java 指定日期和日期间隔,返回间隔 之前 | 之后 的日期
public class DateUtil { /** * 指定日期和日期间隔,返回间隔之前的日期 * @param specifiedDay * @param interval * @return */ public static String getSpecifiedDayAgo(String specifiedDay, int interval){ return getSpecifiedDay(specifiedDay
大数据工程师-公子
2019/03/14
2.6K0
java中的日期类
在程序的开发中我们经常会遇到日期类型的操作,Java对日期类型的操作提供了很好的支持。在最初的版本下,java.lang包中的System.currentTimeMillis();可以获取当前时间与协调时间(UTC)1970年1月1日午夜之间的时间差(以毫秒为单位测量)。我们往往通过调用该方法计算某段代码的耗时。
别团等shy哥发育
2023/02/25
3.6K0
java中的日期类
mysql—mysql中如何存储日期数据
1,特点 1)以YYYY-MM-DD HH:MM:SS[.fraction]格式存储日期时间,在mysql5.6前可以只能存储到秒,在5.6后能存储到微秒 2)datetime类型与时区无关,占用8个字节的存储空间 3)时间范围公元1000-01-01 00:00:00到9999-12-31 23:59:59,存储的时间范围非常广
全栈程序员站长
2021/04/07
5K0
Java中的时间和日期(二):java时间存储的基本原理
在java中,java.util.Date对象用于表示时间。这个对象既能表示日期,也能表示时间。原因在于这个对象内部实际上是一个long字符来存储的毫秒数。我们都知道时间通过System.currentTimeMillis()方法获取当前的系统时间戳,就能转换为我们所需要的时间:
冬天里的懒猫
2020/08/11
1.9K0

相似问题

循环生成基于开始日期和结束日期的日期列表。

11

开始日期和结束日期的Sas循环

124

基于“开始日期”和输入日期显示“结束日期”

26

基于开始日期和结束日期的JSON过滤

22

基于开始日期和结束日期的拆分记录

10
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文