FreeOZ论坛

标题: 树的遍历，判断子孙問題，求最有效率算法 [打印本页]

作者: 周星星1832 时间: 4-6-2015 15:19
标题: 树的遍历，判断子孙問題，求最有效率算法
好吧。。。我已经一脑子浆糊。。。。。。。。。。

一颗巨大的树
判断一個Ａ节点是另外一個节点Ｂ的子孙。。。
我想到的两种方法
(1)
递归看Ｂ的childeren有没有Ａ。。有Ａ的返回。。。没有的话要遍历所有子孙
(2)
递归看A的parent有没有B。。有Ｂ的返回没有的话要到ＲＯＯＴ

哪个更有效率哇。。。還是有更有效率的方法
還是根本就没有更有效率的方法。。

我目前用（2）。至少遍历是单线

作者: 周星星1832 时间: 4-6-2015 15:20
@DDD888

作者: 周星星1832 时间: 4-6-2015 15:25
貌似根據ＡＢ节点的位置不同。。最短路径都会不同。。。。

作者: vivicats 时间: 4-6-2015 15:29
毫无疑问2最优

作者: 周星星1832 时间: 4-6-2015 15:31

vivicats 发表于 4-6-2015 14:29
毫无疑问2最优

我也是这种感觉

作者: 浮云云艾米莉 时间: 4-6-2015 15:48
肯定是2啊。。。b如果有x个children, A在第y层，1要走x^y, 2只要走y

作者: 周星星1832 时间: 4-6-2015 15:56

浮云云艾米莉发表于 4-6-2015 14:48
肯定是2啊。。。b如果有x个children, A在第y层，1要走x^y, 2只要走y

也不一定。。
如果Ａ是Ｂ的子孙。。且是很近的子孙。。而且树枝少的话。。。很快就找到了
但是方法二要一直遍历到root。。

作者: ArBen 时间: 4-6-2015 16:09
怎么完全蒙圈了

作者: melody_iic 时间: 4-6-2015 16:13
运算复杂度应该选最坏情况计算

如果A是B的子孙，方法1的运算复杂度是AB层数差是指数关系，方法2是AB层数差的线性关系
如果A不是B的子孙，方法1的运算复杂度是B到最远叶子层数的指数关系，方法2是A层数的线性关系

综上，方法2胜出

作者: 周星星1832 时间: 4-6-2015 16:16

ArBen 发表于 4-6-2015 15:09
怎么完全蒙圈了

你是IT吗

作者: 周星星1832 时间: 4-6-2015 16:23

melody_iic 发表于 4-6-2015 15:13
运算复杂度应该选最坏情况计算

如果A是B的子孙，方法1的运算复杂度是AB层数差是指数关系，方法2是AB层数 ...

是不是还应该结合实际应用情况来看。。。

判断子孙是肯定要的。。。

但是是子孙的情况比较少。。因為是子孙属于用户判断错误。。。多数情况用户判断应该是正确的
也就是说多数情况下应该不是子孙。。是parent。。。。

所以還是2胜出。。。

作者: melody_iic 时间: 4-6-2015 16:27
理论结合实际，正解

作者: ArBen 时间: 4-6-2015 16:28

周星星1832 发表于 4-6-2015 15:16
你是IT吗

不是完全早不到节奏

作者: 周星星1832 时间: 4-6-2015 16:36

melody_iic 发表于 4-6-2015 15:27
理论结合实际，正解

清醒了我

作者: 周星星1832 时间: 4-6-2015 16:36

ArBen 发表于 4-6-2015 15:28
不是完全早不到节奏

那你肯定完全不懂

作者: ArBen 时间: 4-6-2015 17:08

周星星1832 发表于 4-6-2015 15:36
那你肯定完全不懂

你能写不是挨踢男禁入不

作者: 周星星1832 时间: 4-6-2015 17:09

ArBen 发表于 4-6-2015 16:08
你能写不是挨踢男禁入不

脑补一下挨踢知识也是好的

作者: ArBen 时间: 4-6-2015 17:11

周星星1832 发表于 4-6-2015 16:09
脑补一下挨踢知识也是好的

会帮助泡妞嘛

作者: 周星星1832 时间: 4-6-2015 17:12
补一下应用情况
用户需要给子树设置新的parent
所以在设置前系统需要判断是不是能设置
也就是不能让子树节点作为parent

作者: MICHELLE07 时间: 4-6-2015 17:30

周星星1832 发表于 4-6-2015 15:36
那你肯定完全不懂

弄点大家都懂的挨踢题目给我们玩玩

作者: 周星星1832 时间: 4-6-2015 17:31

ArBen 发表于 4-6-2015 16:11
会帮助泡妞嘛

你的人生能不能有点更高的追求

作者: 周星星1832 时间: 4-6-2015 17:32

MICHELLE07 发表于 4-6-2015 16:30
弄点大家都懂的挨踢题目给我们玩玩

今天头都大了。。

作者: ArBen 时间: 4-6-2015 17:53

周星星1832 发表于 4-6-2015 16:31
你的人生能不能有点更高的追求

难就介点出息了

作者: 周星星1832 时间: 4-6-2015 19:14

ArBen 发表于 4-6-2015 16:53
难就介点出息了

你就不能投入的爱一次

作者: ArBen 时间: 4-6-2015 19:20

周星星1832 发表于 4-6-2015 18:14
你就不能投入的爱一次

你就不能投入的爱一次

作者: 周星星1832 时间: 4-6-2015 19:31

ArBen 发表于 4-6-2015 18:20
你就不能投入的爱一次

我每次都很投入

作者: ArBen 时间: 4-6-2015 19:43

周星星1832 发表于 4-6-2015 18:31
我每次都很投入

一共几次

作者: ArBen 时间: 4-6-2015 19:44

周星星1832 发表于 4-6-2015 18:31
我每次都很投入

一共几次

作者: 周星星1832 时间: 4-6-2015 19:46

ArBen 发表于 4-6-2015 18:43
一共几次

2次。。。。我只谈过两次恋爱

作者: ArBen 时间: 4-6-2015 21:26

周星星1832 发表于 4-6-2015 18:46
2次。。。。我只谈过两次恋爱

读书少你不要骗俺

作者: DDD888 时间: 4-6-2015 21:44

vivicats 发表于 4-6-2015 14:29
毫无疑问2最优

I agree

May I ask how big is the tree? If space is not an issue and if just want fastest way, maybe just use a hash table to store each node link with all parents as a comma delimited string, just one hash lookup and a text search on the csv will get the answer

作者: cais 时间: 5-6-2015 01:04

浮云云艾米莉发表于 4-6-2015 14:48
肯定是2啊。。。b如果有x个children, A在第y层，1要走x^y, 2只要走y

这律师也来抢我们的饭碗了啊。。。

作者: cais 时间: 5-6-2015 01:07

周星星1832 发表于 4-6-2015 14:56
也不一定。。
如果Ａ是Ｂ的子孙。。且是很近的子孙。。而且树枝少的话。。。很快就找到了
但是方法二要 ...

A是B的子孙的话，方法二不是也能很快的找出来吗？

作者: cais 时间: 5-6-2015 01:10
这个题有没有其它的信息，比如知道每个节点在树里面的深度。知道的话，方法二就可以提前结束了。
或者是树的节点有某种排序。
如果没有其它信息，你这两个方法，怎么样都是二比较有效啊。

作者: superopengl 时间: 5-6-2015 02:06
这还取决于树的数据结构。如果每个node都保存the path from root to self的话，判断A是否是B的子孙，只要判断A.PathToRoot.Contains(B.PathToRoot)即可。是个O(1)的算法。

这种树不适合频繁移动和插入node操作。因为所有被移动subtree上的所有node都需要修改PathToRoot.

作者: 周星星1832 时间: 5-6-2015 06:58

ArBen 发表于 4-6-2015 20:26
读书少你不要骗俺

这是标准答案。。记住了。。。下回别人问你
你也这么说

作者: 周星星1832 时间: 5-6-2015 07:00

DDD888 发表于 4-6-2015 20:44
I agree

May I ask how big is the tree? If space is not an issue and if just want fastest way, m ...

可能很大。。。。。
取决于用户建多大
节点是存储在数据库的
但是树是一次性load的
所以判断的时候是js判断的。没在后台判断

作者: 周星星1832 时间: 5-6-2015 07:02

cais 发表于 5-6-2015 00:07
A是B的子孙的话，方法二不是也能很快的找出来吗？

没有啊。。是子孙的话
也就是说不是parent。所以药一直到遍历到root才知道
假设是直接子孙就一层
这个情况2就不是很有效率了

作者: 周星星1832 时间: 5-6-2015 07:03

cais 发表于 5-6-2015 00:10
这个题有没有其它的信息，比如知道每个节点在树里面的深度。知道的话，方法二就可以提前结束了。
或者是树 ...

树的深度。节点多少都是随机的。。因为都是用户决定的

作者: 周星星1832 时间: 5-6-2015 07:04

superopengl 发表于 5-6-2015 01:06
这还取决于树的数据结构。如果每个node都保存the path from root to self的话，判断A是否是B的子孙，只要判 ...

这个不太可能。。。没保存过这个路径
确实不适合频繁改动。但是也确实改动的很频繁

作者: ArBen 时间: 5-6-2015 09:12

周星星1832 发表于 5-6-2015 05:58
这是标准答案。。记住了。。。下回别人问你
你也这么说

作者: ArBen 时间: 5-6-2015 09:12

周星星1832 发表于 5-6-2015 05:58
这是标准答案。。记住了。。。下回别人问你
你也这么说

作者: 周星星1832 时间: 5-6-2015 09:14

ArBen 发表于 5-6-2015 08:12

非诚勿扰上这么说的

作者: ArBen 时间: 5-6-2015 09:21

周星星1832 发表于 5-6-2015 08:14
非诚勿扰上这么说的

岛国爱情片？

作者: 周星星1832 时间: 5-6-2015 09:25

ArBen 发表于 5-6-2015 08:21
岛国爱情片？

作者: 浮云云艾米莉 时间: 5-6-2015 10:03

cais 发表于 5-6-2015 00:04
这律师也来抢我们的饭碗了啊。。。

算法，大学不是都学过的嘛！

不许鄙视数学出身的人。。。

作者: vivicats 时间: 5-6-2015 10:24

周星星1832 发表于 5-6-2015 06:02
没有啊。。是子孙的话
也就是说不是parent。所以药一直到遍历到root才知道
假设是直接子孙就一层

不需要遍历到root，如果是子孙的话，一直找parent node，一定可以找到B，然后就结束了。

遍历到root只有最坏情况，也就是A不是B的子孙。我觉得唯一1比2优的情况就是A不是B的子孙，而且B的所有子孙节点个数小于B的深度。

作者: 周星星1832 时间: 5-6-2015 10:39

vivicats 发表于 5-6-2015 09:24
不需要遍历到root，如果是子孙的话，一直找parent node，一定可以找到B，然后就结束了。

遍历到root只 ...

恩。。最坏的情况就是用户犯错。。。Ａ是Ｂ的子孙。。。二就要遍历到root..
不过这种情况应该很少见。。。所以還是2是最优的

只是这总少见情况下。。1才有可能比2路径短

作者: khing 时间: 9-6-2015 17:14
周星星要找工作？

作者: 周星星1832 时间: 9-6-2015 17:15

khing 发表于 9-6-2015 16:14
周星星要找工作？

暂时还不找

作者: wiserfirst 时间: 9-6-2015 23:31
看了讨论，似乎已经有结论了，即方法2在大部分情况下会更高效。
但是我有个问题，为什么方法2要用递归呢，一个循环从A开始一路找自己的Parent，要么找到B，要么找到Root，不就行了吗？不知道 @周星星1832 用什么语言，但是循环的效率至少不会比递归差吧

作者: 周星星1832 时间: 10-6-2015 07:46

wiserfirst 发表于 9-6-2015 22:31
看了讨论，似乎已经有结论了，即方法2在大部分情况下会更高效。
但是我有个问题，为什么方法2要用递归呢， ...

没法循环。。因为不知道多少个parent。也没法一下子获取所有parent节点
只能一层层的递归上去
这个应用是javascript

作者: DDD888 时间: 10-6-2015 10:24

周星星1832 发表于 10-6-2015 06:46
没法循环。。因为不知道多少个parent。也没法一下子获取所有parent节点
只能一层层的递归上去
这个应用 ...

while loop 行吗？

作者: 周星星1832 时间: 10-6-2015 10:53
本帖最后由周星星1832 于 10-6-2015 11:17 编辑

DDD888 发表于 10-6-2015 09:24
while loop 行吗？

function is_child(setNewParentId, thisId) {
var isChild = false;
var parentConns = instance.getConnections({
target:[thisId],
scope:["cause", "combo"]
},true);
if (parentConns.length) {
var parentId = parentConns[0].sourceId;
if (parentId ==setNewParentId) {
return true;
} else {
isChild = is_child(setNewParentId, parentId);
}
}
return isChild;
}

复制代码

貌似可以

作者: 周星星1832 时间: 10-6-2015 12:19
其实感觉還是递归比while 更简洁

作者: vivicats 时间: 10-6-2015 12:35
一个while loop就解决了，递归有点多此一举了，要考虑到递归不管从效率还是内存空间使用上，都差于loop，递归要保存当前的所有状态，在这个例子是完全是没用的

作者: 周星星1832 时间: 10-6-2015 12:55

vivicats 发表于 10-6-2015 11:35
一个while loop就解决了，递归有点多此一举了，要考虑到递归不管从效率还是内存空间使用上，都差于loop，递 ...

function is_child(setNewParentId, thisId) {
var parentConns = instance.getConnections({
target:[thisId],
scope:["cause", "combo"]
},true);
while (parentConns = instance.getConnections({ target:[thisId], scope:["cause", "combo"] },true)) {
var parentId = parentConns[0].sourceId;
if (parentId ==setNewParentId) {
return true;
} else {
thisId = parentId;
}
}
return false;
}

复制代码

作者: vivicats 时间: 10-6-2015 13:05
本帖最后由 vivicats 于 10-6-2015 12:07 编辑

周星星1832 发表于 10-6-2015 11:55

这样写短一点

function is_child(setNewParentId, thisId) {
var parentConns, parentId;
        while (thisId != setNewParentId && thisId != 0) {
parentConns = instance.getConnections({ target:[thisId],  scope:["cause", "combo"] },true);
        parentId = parentConns[0].sourceId;
        }
        return (thisId == setNewParentId);
}

ps: 不太会写javascript，见笑了，另外不知道怎么编辑格式，凑合着看吧

作者: 周星星1832 时间: 10-6-2015 13:19

vivicats 发表于 10-6-2015 12:05
这样写短一点

function is_child(setNewParentId, thisId) {

nice

作者: khing 时间: 10-6-2015 23:44

周星星1832 发表于 9-6-2015 16:15
暂时还不找

那是工作中遇到的问题啊？好高大上

如果有指向parent的指针，直接循环往回找就是了；
如果没有，那就递归：

bool isParent(node *a, node *b) {
if (!a) return false;
if (a->l == b || a->r == b)
return true;
return isParent(a->l, b) || isParent(a->r, b);
}

复制代码

不好意思，俺只会C++

作者: 周星星1832 时间: 11-6-2015 07:59

khing 发表于 10-6-2015 22:44
那是工作中遇到的问题啊？好高大上

如果有指向parent的指针，直接循环往回找就是了；

目前的项目确实比较难搞
涉及很多基础的涉及
其实发现知识真的是用的时候才是觉得有用的。。

作者: wiserfirst 时间: 11-6-2015 18:41

周星星1832 发表于 10-6-2015 11:55

我建议把查找parentId的逻辑提取出来，会更清晰一点

function get_parent_id(thisId) {
var parentId = undefined;
if (parentConns = instance.getConnections({ target:[thisId], scope:["cause", "combo"] }, true)) {
parentId = parentConns[0].sourceId;
}
return parentId;
}
function is_child(setNewParentId, thisId) {
var parentId;
while (parentId = get_parent_id(thisId)) {
if (parentId === setNewParentId) {
return true;
} else {
thisId = parentId;
}
}
return false;
}

复制代码

作者: 周星星1832 时间: 11-6-2015 19:52

wiserfirst 发表于 11-6-2015 17:41
我建议把查找parentId的逻辑提取出来，会更清晰一点

好主意。。。。等我休假回来改代码
昨天早上系统已经go live了。。。

作者: clarkli 时间: 14-6-2015 15:02
2的前提是child node要有指向parent的指针

1的话，如果是二叉搜索树可以做到O(log(N))，否则只能linear了

作者: 周星星1832 时间: 14-6-2015 15:36

clarkli 发表于 14-6-2015 14:02
2的前提是child node要有指向parent的指针

1的话，如果是二叉搜索树可以做到O(log(N))，否则只能linear ...

指针算是有
不是二叉树

欢迎光临 FreeOZ论坛 (https://www.freeoz.org/ibbs/)