C-有一个千万级节点的树,已知两个节点,如何他们的共同祖先?

C-有一个千万级节点的树,已知两个节点,如何他们的共同祖先?

灵芸 发布于 2017-08-07 字数 22 浏览 1098 回复 3

复杂度小于O(n2)

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

浮生未歇 2017-11-03 3 楼

 //pos = 0 不使用
//pos = 1 为根节点
function getParentPos(a, b) {
while(true) {
if(a == b) break;
if (a > b) {
a = a >> 1;//获取a的父节点
}else {
b = b >> 1;//获取b的父节点
}
}
return a;
}
alert(getParentPos(4, 11));//得到父节点的索引号

想挽留 2017-09-24 2 楼

首先,复杂度为n^2的基本方式,将第一个对比节点的父节点全部入栈,而后将堆栈中的父节点序列跟第二个对比节点进行逐一比较,如果相等说明是最近的共同祖先:

myLCA(node1, node2) {
parentNode := [ ]
while (node1!=NULL) {
parentNode.push(node1)
node1 := node1.parent
}
while (node2!=NULL) {
for i in parentNode.size {
if (parentNode(i) == node2) {
return node2;
}
}
node2 := node2.parent
}

}

在前述方法的基础上优化一下,先后将两个对比节点的父节点序列依次入栈,得到两个可比较的堆栈,然后再循环出栈遍历,这个时候的顺序就是从上到下的遍历了,第一个不相等的节点表明开始分叉了,那么这个节点之前的所有堆栈中的节点都是共同祖先,应该可以达到O(N+M+L).下面算法找出最近的祖先节点:

linearLCA(node1, node2) {
parentNode1 := [ ]
while (node1!=NULL) {
parentNode1.push(node1)
node1 := node1.parent
}
parentNode2 := [ ]
while (node2!=NULL) {
parentNode2.push(node2)
node2 := node2.parent
}
while (node1 == node2) {
oldNode1 := node1
oldNode2 := node2
node1 := parentNode1.pop()
node2 := parentNode2.pop()
}

return oldNode1
}

晚风撩人 2017-08-20 1 楼

树找祖先的问题,往往从叶子节点出发,沿着根的路径往上回溯,效率高效。
最容易想到的方法,分别记录两个节点的回溯路径,然后比较两个记录。对于"千万级节点的树",记录数会非常多,涉及非常多的查找时间。

以下是我根据网上的资料整理的一个思路:
1.建立树时,给每个节点加入层次编号。选取两个节点时,取出层次编号,层次编号大的节点从这个层次的祖先节点,回溯依次入栈祖先节点。
2.这样每个栈的栈顶就是根结点。栈底就是结点本身。
3.每个栈同时出栈,当某一步两个栈顶的元素不等或某一栈为空时,则前一个出栈的元素就是所求的最近公共祖先。