| Current Forum: 15-211 Main Forum |
| Date: Mon Dec 17 2001 6:13 pm |
| Author: Shi, Ying <shy@cmu.edu> |
| Subject: Re: Tree Positions question on Fall 00 Test |
|
|
my answer:
a) two, same reasoning as you gave in your post(strictly follow the description--"child's")
b) c) same
d) your answer in the post seem to be imcomplete, might be due to formatting problem, here is mine:
n1 A n2 : pre(n1) < pre(n2) AND post(n1) > post(n2)
n1 R n2 : pre(n1) > pre(n2) AND post(n1) > post(n2)
n1 D n2 : pre(n1) > pre(n2) AND post(n1) < post(n2)
e) O(MN)
the cost includes:
-set-up preorder numbers O(N)
-set-up postorder numbers O(N)
-each query involves: <1. find n1 in the tree-gets its pre&post numbers : O(N) 2. find n2 and get its numbers O(N)> times M
so cost = O(N) + O(N) + M * O(N) = O(MN)
Any comments ?
Thanks
|
|