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

距离树中另一个节点最远的节点
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

复制
相关文章
如何在 Git 上更改分支名称?
在 Git 版本控制系统中,分支是非常重要的概念。分支允许你在项目中进行并行开发和实验,同时保持主分支的稳定性。有时候,你可能需要更改已存在的分支名称,例如纠正拼写错误或者为了更好地描述分支的内容。本文将详细介绍如何在 Git 上更改分支名称。
网络技术联盟站
2023/06/19
1.9K0
如何在 Git 上更改分支名称?
更改Linux网卡名称
转载自:https://blog.csdn.net/yeziand01/article/details/88424624
zy010101
2019/07/02
5.1K0
更改Linux网卡名称
Oracle 更改表名称的几种方式
ALTER TABLE old_table_name RENAME TO new_table_name;(大写为系统命令)
全栈程序员站长
2022/08/29
4.7K0
更改WordPress插件的菜单名称
如果您想在不直接编辑插件的情况下更改WordPress内部管理菜单的名称,您可以使用$menuWordPress管理员中存在的全局变量。操作此数据结构将允许您更改由任何插件添加的管理菜单的文本或名称。这在您希望提供项目内容的清晰度或为客户端提供更好的管理UX的情况下非常有用。
许都博客
2021/06/15
4K0
Github更改账户名称/仓库地址/个人链接后缀
注意:在public profile中修改的name,是主页个人名字,不是仓库地址后缀!!!
浩Coding
2019/07/03
11.4K0
如何在NLP中有效利用Deep Transformer?
2017年,谷歌在“Attention is all you need”一文中首次提出了完全基于self-attention(自注意力)机制的transformer模型,用于处理序列模型的相关问题,如机器翻译等。传统的神经机器翻译模型大都是采用RNN或者CNN作为encoder-decoder模型的基础,而Transformer模型则摒弃了固有的模式,采用完全并行化的结构,在提升了模型的性能的同时提高了训练的速度,目前已经被推广到多项自然语言处理的相关任务当中。
AI科技评论
2020/02/14
9570
如何在NLP中有效利用Deep Transformer?
如何在Linux中更改SSH端口?
SSH(Secure Shell)是一种安全的远程登录协议,它允许您通过网络远程连接到Linux系统并进行管理操作。默认情况下,SSH使用22端口进行通信。然而,为了增强系统的安全性,有时候我们需要更改SSH端口,以减少潜在的攻击。
网络技术联盟站
2023/05/25
9.4K0
如何在Linux中更改SSH端口?
如何在 Linux 中更改主机名?
在 Linux 系统中,主机名是用于标识和区分网络上的不同计算机的名称。默认情况下,Linux 发行版会分配一个主机名给您的计算机,但是有时候您可能需要根据自己的需求更改主机名。在本文中,我们将详细介绍如何在 Linux 中更改主机名,以及更改主机名后可能涉及到的其他配置。
网络技术联盟站
2023/06/09
8.8K0
如何在 Linux 中更改主机名?
linux中有选择的删除目录中的文件
某些场景下我们需要删除目录下指定类型,后缀的文件。这时候就需要一些小技巧。 首先我们先要了解一下模式匹配。在Linux中,shell模式是由以下特殊字符组成的字符串,称为wildcards或者meta
入门笔记
2022/06/02
3K0
如何在 Linux 中更改 Nginx 80 端口?
Nginx 是一个开源的轻量级 Web 服务器替代 apache 来处理高流量的网站。
网络技术联盟站
2022/06/21
5.4K0
如何在 Linux 中更改 Nginx 80 端口?
如何在Ubuntu 14.04上更改PHP设置
PHP是一种服务器端脚本语言,被许多流行的CMS和博客平台使用,如WordPress和Drupal。它也是流行的LAMP和LEMP堆栈的一部分。在设置基于PHP的网站时,更新PHP配置设置是一项常见任务。找到确切的PHP配置文件可能并不容易。有多个PHP安装在服务器上正常运行,每个安装都有自己的配置文件。知道要编辑哪个文件以及当前设置是什么可能有点神秘。
彼岸轮回
2018/09/25
1.7K0
如何在 Linux 中更改 Apache HTTP 端口?
Apache Web Server 是一个免费的开源跨平台 Web 服务器应用程序,用于通过 Internet 提供内容。
网络技术联盟站
2022/06/21
6.3K0
如何在 Linux 中更改 Apache HTTP 端口?
如何在Linux中更改用户ID?
在Linux系统中,每个用户都有一个唯一的用户ID(User ID),用于标识和管理用户的权限和资源访问。有时候,我们需要更改用户ID,可能是为了解决冲突、重组用户组或其他管理需求。本文将详细介绍如何在Linux中更改用户ID的几种方法。
网络技术联盟站
2023/06/08
8.4K0
如何在Linux中更改用户ID?
使用Python实现批量更改文件夹下图片的名称
前几天在Python白银交流群有个叫【belongs】的粉丝问了一个使用Python实现批量更改文件夹下图片的名称的问题,如下图所示。
前端皮皮
2022/08/17
2.6K0
使用Python实现批量更改文件夹下图片的名称
点击加载更多

相似问题

在CKEditor中有选择地触发更改事件

12

如何在Coq中有选择地重写?

15

选择名称匹配,如80%

35

如何在FosUserbundle中有选择地禁用注册?

22

如何在python中有选择地深拷贝?

11
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

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

洞察 腾讯核心技术

剖析业界实践案例

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