| Current Forum: 15-211 Main Forum |
| Date: Tue Dec 18 2001 9:54 am |
| Author: Liu, Limin Angela <laliu@andrew.cmu.edu> |
| Subject: Re: Tree Positions question on Fall 00 Test |
|
|
I think O(MN) is correct. Aditya mentioned that unless it specifically says that it's a binary search tree (find in O(lgN) time), assume it's just a linked list. So every find needs O(N) time. Because we don't know where every node is. Unless we use hashtable to match each node to a key value, then the find will be constant time. Since we need to do 2M find, we need O(MN) totally.
e.g. there are many letters stored in the tree, each node is one letter. We want to know the LARD relationship between 'a' and 'b'. We first need to find where 'a' is stored in the tree, then retrieve its pre and post value.
Any comments? |
|