Author 
Topic: Non trivial BST Insertion (Read 1507 times) 

howard roark
Full Member
Posts: 241


Non trivial BST Insertion
« on: Feb 15^{th}, 2009, 9:25pm » 
Quote Modify

Assume you are building a BST (Binary Search tree) of n nodes using purely by insertions, that all keys are distinct, and that all key orderings for the insertions were equally likely. Write an efficient algorithm which takes as input the root of a tree, and which returns the probability that that particular tree would have been built under these assumptions. Hint 1: If the tree has 3 nodes, root node and children on both sides of root node, probability of that tree is 1/3 PS:I thought this is a better place for this question than cs forums. Please tell me if I should move this to cs forums

« Last Edit: Feb 16^{th}, 2009, 5:55pm by howard roark » 
IP Logged 



mistaken_id
Junior Member
Posts: 132


Re: Non trivial BST Insertion
« Reply #1 on: Feb 16^{th}, 2009, 9:55pm » 
Quote Modify

I doubt if the algorithm even needs n as input..


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Non trivial BST Insertion
« Reply #2 on: Feb 17^{th}, 2009, 2:59am » 
Quote Modify

My first guess is to 1) count the nodes in each subtree 2) multiply for each node (#left+#right)!/left!/#right! (where #left is the number of node in the left subtree, and analogous for #right) 3) divide the whole by #root! That would be O(n) runtime if it checks out.

« Last Edit: Feb 17^{th}, 2009, 3:00am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



howard roark
Full Member
Posts: 241


Re: Non trivial BST Insertion
« Reply #3 on: Feb 17^{th}, 2009, 12:23pm » 
Quote Modify

Cool! so the algo doesnt need n as the input. However, run time does depend on n and it is O(n)....


IP Logged 



howard roark
Full Member
Posts: 241


Re: Non trivial BST Insertion
« Reply #4 on: Feb 17^{th}, 2009, 12:33pm » 
Quote Modify

what does #root mean? #left+#right +1 ??


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Non trivial BST Insertion
« Reply #5 on: Feb 17^{th}, 2009, 12:33pm » 
Quote Modify

You can calculate n by going through the tree (and in fact you have to, #root=n). And to be sure you account for the whole tree you need to visit every node, so you can't do better than O(n).


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Non trivial BST Insertion
« Reply #6 on: Feb 17^{th}, 2009, 12:35pm » 
Quote Modify

on Feb 17^{th}, 2009, 12:33pm, howard roark wrote:what does #root mean? #left+#right +1 ?? 
 For the root node, yes. I strictly use it for the top of the tree here though.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



howard roark
Full Member
Posts: 241


Re: Non trivial BST Insertion
« Reply #7 on: Feb 17^{th}, 2009, 1:00pm » 
Quote Modify

logic behind your algo?? I somehow feel that your algo assumes number of trees with n nodes is n!, which I think is wrong. Number of trees with n nodes is Catalannumber (n). I know I am wrong, Just tell me where I am wrong......


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Non trivial BST Insertion
« Reply #8 on: Feb 17^{th}, 2009, 1:35pm » 
Quote Modify

on Feb 17^{th}, 2009, 1:00pm, howard roark wrote:I somehow feel that your algo assumes number of trees with n nodes is n!, which I think is wrong. 
 Ah yes. What the algorithm returns is the probability of a random sequence of input resulting in that particular tree. And there are n! such random input sequences. But this does seem to be exactly what was asked for. For instance take all inputs of 3 elements 1,2,3 > (1,(2,(3))) 1,3,2 > (1,((2),3)) 2,1,3 > ((1),2,(3)) 2,3,1 > ((1),2,(3)) 3,1,2 > ((1,(2)), 3) 3,2,1 > (((1),2), 3) The middle two result in the same tree, so we have probability 2/6=1/3 of getting that tree, exactly the number you gave.

« Last Edit: Feb 17^{th}, 2009, 1:36pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Non trivial BST Insertion
« Reply #9 on: Feb 17^{th}, 2009, 3:02pm » 
Quote Modify

on Feb 17^{th}, 2009, 1:00pm, howard roark wrote:The possible input sequences are constraint only by the fact that the ancestor of a node has to come earlier in the sequence. So the positions of nodes in different subtrees are independent, as long as they come after their common ancestor. So if we ignore the order the elements of each subtree occurs in for a moment, we're just mixing two groups, which can be done in (n+m)!/(n!m!) ways. And then next we determine the order of those subgroups recursively.

« Last Edit: Feb 17^{th}, 2009, 3:03pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



howard roark
Full Member
Posts: 241


Re: Non trivial BST Insertion
« Reply #10 on: Mar 1^{st}, 2009, 10:11pm » 
Quote Modify

Is the running time of the algorithm O(n).......I think it will be more than that, because as we move up we have to find factorials of larger numbers which are as big as n in the root


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Non trivial BST Insertion
« Reply #11 on: Mar 2^{nd}, 2009, 1:06am » 
Quote Modify

on Mar 1^{st}, 2009, 10:11pm, howard roark wrote:Is the running time of the algorithm O(n).......I think it will be more than that, because as we move up we have to find factorials of larger numbers which are as big as n in the root 
 You can make a table of all factorials you need with O(n) multiplications. Although that's a small comfort when the size of the result grows beyond the machineword. There might be ways to improve it though.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Non trivial BST Insertion
« Reply #12 on: Mar 2^{nd}, 2009, 5:50am » 
Quote Modify

We can also write it as P(T) = 1/T * P(L)*P(R), which looks pretty nice (looks better in my head than on the page though). Let F(n) be the maximum value of P(T) over all trees of size n. Then n!*F(n) is the number of heaps of size n.

« Last Edit: Mar 2^{nd}, 2009, 8:05am by Eigenray » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Non trivial BST Insertion
« Reply #13 on: Mar 2^{nd}, 2009, 6:51am » 
Quote Modify

on Mar 2^{nd}, 2009, 5:50am, Eigenray wrote:We can also write it as P(T) = 1/T * P(L)*P(R), which looks pretty nice. 
 Indeed it does. And the interpretation that goes with it is so much simpler as well. In any subtree every node has an equal chance of being the root. Or to put it another way, you can create the tree by putting all elements in a row, and then recursively pick one from the row uniformly randomly to function as root, and splitting the row in two at its position. Then repeat for both subtrees. [edit]I liked the old version of the formula better [/edit]

« Last Edit: Mar 2^{nd}, 2009, 6:54am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



howard roark
Full Member
Posts: 241


Re: Non trivial BST Insertion
« Reply #14 on: Mar 2^{nd}, 2009, 8:12pm » 
Quote Modify

on Mar 2^{nd}, 2009, 5:50am, Eigenray wrote: How is the above result possible?


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948

F(n) = max_{k<n} C(n1,k) F(k) F(n1k). Compared to the other formula it's not surprising. Attached are the plots of { C(n1,k) F(k) F(n1k) : 0 k < n }, for n =1,...,256. Note the two maxima that look like they are moving back and forth. The index moving to the left is actually standing still at (one less than) a power of 2; the other one grows until it reaches the next (one less than a) power of 2.

« Last Edit: Mar 2^{nd}, 2009, 10:25pm by Eigenray » 
IP Logged 



