Author |
Topic: Preprocessing a BST (Read 1001 times) |
|
inexorable
Full Member
Posts: 211
|
 |
Preprocessing a BST
« on: May 17th, 2006, 11:15pm » |
 Quote  Modify
|
Given a binary search tree how can it be preprocessed in O(n) time such that, given a pair a numbers (x,y) it can be determined whether x is parent of y or viceversa, in constant time?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Preprocessing a BST
« Reply #2 on: May 18th, 2006, 3:21pm » |
Quote Modify
|
I think this question asks something slightly different..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Preprocessing a BST
« Reply #3 on: May 18th, 2006, 4:43pm » |
Quote Modify
|
True, it can be reduced.
Preprocess: Tag each node with its preorder and postorder rank.
Test: x is a parent of y iff (x.preorder < y.preorder) && ( y.postorder < x.postorder )
That is, y is a descendant of x if, during a DFS, y is encountered only between the two visits to x.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Preprocessing a BST
« Reply #4 on: May 19th, 2006, 12:50am » |
Quote Modify
|
That works if you get the nodes the numbers are in, but if you get the numbers themselves, it takes O(log(n)) to find the nodes.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Preprocessing a BST
« Reply #5 on: May 19th, 2006, 4:35am » |
Quote Modify
|
towr, that's true, but anyway, KWillets' idea is very elegant! 
|
|
IP Logged |
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Preprocessing a BST
« Reply #6 on: May 19th, 2006, 10:16am » |
Quote Modify
|
Unfortunately, I didn't think of that one myself. It's used quite a bit in relational databases where no one knows what a recursive query is.
As far as the lookup requirement, I guessed that the problem statement was unclear, and that x and y were given as node references in a binary tree or some such. O(1) value lookups would require that it no longer be a BST -- Clarification?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Preprocessing a BST
« Reply #7 on: May 20th, 2006, 2:56am » |
Quote Modify
|
Even so, we need to find whether x,y are parent and child, not ancestor and descendant.
If we're given the nodes, there's a much easier check; we don't even need preprocessing. Unless that's a mistake in the problem statement.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Preprocessing a BST
« Reply #8 on: May 20th, 2006, 3:50am » |
Quote Modify
|
on May 20th, 2006, 2:56am, towr wrote:| Even so, we need to find whether x,y are parent and child, not ancestor and descendant. |
|
What's the difference?
Quote:| If we're given the nodes, there's a much easier check; we don't even need preprocessing. |
|
How?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Preprocessing a BST
« Reply #9 on: May 20th, 2006, 4:17am » |
Quote Modify
|
on May 20th, 2006, 3:50am, Barukh wrote:Well, your father is (one of) your parent(s), but your grandfather is not. They're both ancestors though. And descendant and child works in the other direction.
The same works for trees; except for the root, each node has exactly one parent. There may be multiple ancestors though (If the parents have parents). http://www.cs.wisc.edu/~siff/CS367/Notes/trees.html
Quote:To check whether y is a child of x, check (x.left=y || x.right=y) .
|
| « Last Edit: May 20th, 2006, 4:26am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print