I have a question about the LARD in trees stuff.
For problem a), two nodes, n1 != n2, exactly how many of
the relations L, A, R, D can hold between them?
I said two. But it could be four. The problem I'm having is lets say n1 is a descendent of n2, therefore n2 is a ancestor of n1 (we have two so far), now lets say n1 is off on the left subtree of n2. Is n1Ln2? and n2Rn1?
I'm trying to figure out the description from the top of the page. It reads: Node n1 is left of n2 if there is an ancestor n of both n1 and n2 such that n1 is a descendent of the left child of n and n2 is a descendent of the right child of n.
For this case, n2==n, but I think the last line disqualifies it since it says, n2 must be a descendent of the "right child" of n. If it just said it must be a descendent of n, it would work since, if n2==n it is an ancestor and a descendent, but not of its right child..
At any rate, did anyone else get 2 for this answer?
For b) I got n1An2 && n2Dn1 or n1Ln2 && n2Rn1
For c) I got n1Ln2 && n1Rn2 or n1Dn2 && n2An1
For d) n1An2: pre(n1)post(n2)
n1Rn2: pre(n1)>pre(n2) and post(n1)>post(n2)
n1Dn2: pre(n1)>pre(n2) and post(n1)For e) O(N+M).
Anyone else get similar or different answers?
|