wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Preprocessing a BST
        
(Message started by: inexorable on May 17^th, 2006, 11:15pm)

Title: Preprocessing a BST
Post by inexorable on May 17^th, 2006, 11:15pm

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?

Title: Re: Preprocessing a BST
Post by KWillets on May 18^th, 2006, 10:30am

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1139985558

Title: Re: Preprocessing a BST
Post by towr on May 18^th, 2006, 3:21pm

I think this question asks something slightly different..

Title: Re: Preprocessing a BST
Post by KWillets on May 18^th, 2006, 4:43pm

True, it can be reduced.
[hide]
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.
[/hide]

Title: Re: Preprocessing a BST
Post by towr on May 19^th, 2006, 12:50am

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.

Title: Re: Preprocessing a BST
Post by Barukh on May 19^th, 2006, 4:35am

towr, that's true, but anyway, KWillets' idea is very elegant! :D

Title: Re: Preprocessing a BST
Post by KWillets on May 19^th, 2006, 10:16am

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?

Title: Re: Preprocessing a BST
Post by towr on May 20^th, 2006, 2:56am

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.

Title: Re: Preprocessing a BST
Post by Barukh on May 20^th, 2006, 3:50am

on 05/20/06 at 02:56:17, 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?

Title: Re: Preprocessing a BST
Post by towr on May 20^th, 2006, 4:17am

on 05/20/06 at 03:50:17, Barukh wrote:

What's the difference?

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:

How?

To check whether y is a child of x, check (x.left=y || x.right=y) .