最低公共祖先的实现 - 有什么区别？ [英] Lowest Common Ancestor implementations - what's the difference?
本文介绍了最低公共祖先的实现 - 有什么区别？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我一直在阅读有关最低顶部codeR 的共同祖先算法，我不明白为什么RMQ算法是参与 - 该解决方案列在那里是出奇的复杂，并具有以下属性：
- 在搜索时的O（开方（N））的时间复杂度，为O（n）precalculation时间复杂度
- O（n）的空间复杂度，用于存储父母每个节点的
- O（n）的空间复杂度再次，用于存储每个节点的precalculations
我的解决办法：给定的两个整数值，发现通过一个简单的preorder遍历的节点。就拿其中一个节点，去了树和路径存储为一组。就拿其他节点上去树和检查每个节点，因为我去了：如果节点的设置，停止和返回的LCA。 全面实施。
- O（n）的时间寻找各2个节点的复杂性，给出的值（因为它是一个普通的树，而不是一个BST -
- O（log n）的空间复杂度存储路径进入设置
- O（log n）的时间复杂度为上升树的第二个节点
所以，有了这两个选项，在顶部codeR算法更好，如果是，为什么？这是我无法理解。我以为O（log n）的比O（开方（N））更好。
公共类LCA {
私有类节点{
int数据;
节点[]孩子=新节点[0];
节点父;
公共节点（）{
}
公共节点（INT V）{
数据= V;
}
@覆盖
公共布尔等于（对象除外）{
如果（this.data ==（（节点）等）.DATA）{
返回true;
}
返回false;
}
}
私人节点根;
公共LCA（）{
根=新节点（3）;
root.children =新节点[4];
root.children [0] =新节点（15）;
root.children [0] .parent =根;
root.children [1] =新节点（40）;
root.children [1] .parent =根;
root.children [2] =新节点（100）;
root.children [2] .parent =根;
root.children [3] =新节点（10）;
root.children [3] .parent =根;
root.children [0]。儿童=新节点[3];
root.children [0]。儿童[0] =新节点（22）;
root.children [0]。儿童[0] .parent = root.children [0];
root.children [0]。儿童[1] =新节点（11）;
root.children [0]。儿童[1] .parent = root.children [0];
root.children [0]。儿童[2] =新节点（99）;
root.children [0]。儿童[2] .parent = root.children [0];
root.children [2]。儿童=新节点[2];
root.children [2]。儿童[0] =新节点（120）;
root.children [2]。儿童[0] .parent = root.children [2];
root.children [2]。儿童[1] =新节点（33）;
root.children [2]。儿童[1] .parent = root.children [2];
root.children [3]。儿童=新节点[4];
root.children [3]。儿童[0] =新节点（51）;
root.children [3]。儿童[0] .parent = root.children [3];
root.children [3]。儿童[1] =新节点（52）;
root.children [3]。儿童[1] .parent = root.children [3];
root.children [3]。儿童[2] =新节点（53）;
root.children [3]。儿童[2] .parent = root.children [3];
root.children [3]。儿童[3] =新节点（54）;
root.children [3]。儿童[3] .parent = root.children [3];
root.children [3]。儿童[0]。儿童=新节点[2];
root.children [3]。儿童[0]。儿童[0] =新节点（25）;
root.children [3]。儿童[0]。儿童[0] .parent = root.children [3]。儿童[0];
root.children [3]。儿童[0]。儿童[1] =新节点（26）;
root.children [3]。儿童[0]。儿童[1] .parent = root.children [3]。儿童[0];
root.children [3]。儿童[3]。儿童=新节点[1];
root.children [3]。儿童[3]。儿童[0] =新节点（27）;
root.children [3]。儿童[3]。儿童[0] .parent = root.children [3]。儿童[3];
}
私人节点findNode（节点根，int值）{
如果（根== NULL）{
返回null;
}
如果（root.data ==值）{
返回根;
}
的for（int i = 0; I＆LT; root.children.length;我++）{
节点发现= findNode（root.children [我]，值）;
如果（发现！= NULL）{
返回发现;
}
}
返回null;
}
公共无效LCA（INT节点1，INT节点2）{
节点N1 = findNode（根，节点1）;
节点N2 = findNode（根，节点2）;
设置＆LT;节点＆GT;祖先=新的HashSet＆LT;节点＆GT;（）;
而（N1！= NULL）{
ancestors.add（n1）的;
N1 = n1.parent;
}
而（N2！= NULL）{
如果（ancestors.contains（N 2））{
的System.out.println（之间找到共同的祖先+节点1 +和+节点2 +：点+ n2.data）;
返回;
}
N2 = n2.parent;
}
}
公共静态无效的主要（字串[] args）{
LCA树=新的LCA（）;
tree.LCA（33，27）;
}
}
解决方案
LCA的算法适用于任何树（不一定是二进制的，不一定平衡）。你简单的算法分析打破了，因为跟踪的路径根节点实际上是O（n）的时间和空间，而不是为O（log N）
I've been reading about the Lowest Common Ancestor algorithm on top coder and I can't understand why the RMQ algorithm is involved - the solution listed there is insanely complicated and has the following properties:
- O(sqrt(n)) time complexity for searches, O(n) precalculation time complexity
- O(n) space complexity for storing parents of each node
- O(n) space complexity again, for storing precalculations of each node
My solution: given 2 integer values, find the nodes through a simple preorder traversal. Take one of the nodes and go up the tree and store the path into a Set. Take the other node and go up the tree and check each node as I go up: if the node is in the Set, stop and return the LCA. Full implementation.
- O(n) time complexity for finding each of the 2 nodes, given the values (because it's a regular tree, not a BST -
- O(log n) space complexity for storing the path into the Set
- O(log n) time complexity for going up the tree with the second node
So given these two choices, is the algorithm on Top Coder better and if yes, why? That's what I can't understand. I thought O(log n) is better than O(sqrt(n)).
public class LCA {
private class Node {
int data;
Node[] children = new Node[0];
Node parent;
public Node() {
}
public Node(int v) {
data = v;
}
@Override
public boolean equals(Object other) {
if (this.data == ((Node) other).data) {
return true;
}
return false;
}
}
private Node root;
public LCA() {
root = new Node(3);
root.children = new Node[4];
root.children[0] = new Node(15);
root.children[0].parent = root;
root.children[1] = new Node(40);
root.children[1].parent = root;
root.children[2] = new Node(100);
root.children[2].parent = root;
root.children[3] = new Node(10);
root.children[3].parent = root;
root.children[0].children = new Node[3];
root.children[0].children[0] = new Node(22);
root.children[0].children[0].parent = root.children[0];
root.children[0].children[1] = new Node(11);
root.children[0].children[1].parent = root.children[0];
root.children[0].children[2] = new Node(99);
root.children[0].children[2].parent = root.children[0];
root.children[2].children = new Node[2];
root.children[2].children[0] = new Node(120);
root.children[2].children[0].parent = root.children[2];
root.children[2].children[1] = new Node(33);
root.children[2].children[1].parent = root.children[2];
root.children[3].children = new Node[4];
root.children[3].children[0] = new Node(51);
root.children[3].children[0].parent = root.children[3];
root.children[3].children[1] = new Node(52);
root.children[3].children[1].parent = root.children[3];
root.children[3].children[2] = new Node(53);
root.children[3].children[2].parent = root.children[3];
root.children[3].children[3] = new Node(54);
root.children[3].children[3].parent = root.children[3];
root.children[3].children[0].children = new Node[2];
root.children[3].children[0].children[0] = new Node(25);
root.children[3].children[0].children[0].parent = root.children[3].children[0];
root.children[3].children[0].children[1] = new Node(26);
root.children[3].children[0].children[1].parent = root.children[3].children[0];
root.children[3].children[3].children = new Node[1];
root.children[3].children[3].children[0] = new Node(27);
root.children[3].children[3].children[0].parent = root.children[3].children[3];
}
private Node findNode(Node root, int value) {
if (root == null) {
return null;
}
if (root.data == value) {
return root;
}
for (int i = 0; i < root.children.length; i++) {
Node found = findNode(root.children[i], value);
if (found != null) {
return found;
}
}
return null;
}
public void LCA(int node1, int node2) {
Node n1 = findNode(root, node1);
Node n2 = findNode(root, node2);
Set<Node> ancestors = new HashSet<Node>();
while (n1 != null) {
ancestors.add(n1);
n1 = n1.parent;
}
while (n2 != null) {
if (ancestors.contains(n2)) {
System.out.println("Found common ancestor between " + node1 + " and " + node2 + ": node " + n2.data);
return;
}
n2 = n2.parent;
}
}
public static void main(String[] args) {
LCA tree = new LCA();
tree.LCA(33, 27);
}
}
解决方案
The LCA algorithm works for any tree (not necessarily binary and not necessarily balanced). Your "simple algorithm" analysis breaks down since tracing a path to a root node is actually O(N) time and space instead of O(log N)
这篇关于最低公共祖先的实现 - 有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
