Author |
Topic: Non trivial BST Insertion (Read 1517 times) |
|
howard roark
Full Member
Posts: 241
|
 |
Non trivial BST Insertion
« on: Feb 15th, 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 16th, 2009, 5:55pm by howard roark » |
 IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Non trivial BST Insertion
« Reply #1 on: Feb 16th, 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 17th, 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 17th, 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 17th, 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 17th, 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 17th, 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 17th, 2009, 12:35pm » |
Quote Modify
|
on Feb 17th, 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 17th, 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 Catalan-number (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 17th, 2009, 1:35pm » |
Quote Modify
|
on Feb 17th, 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 17th, 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 17th, 2009, 3:02pm » |
Quote Modify
|
on Feb 17th, 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 17th, 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 1st, 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 2nd, 2009, 1:06am » |
Quote Modify
|
on Mar 1st, 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 2nd, 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 2nd, 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 2nd, 2009, 6:51am » |
Quote Modify
|
on Mar 2nd, 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 2nd, 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 2nd, 2009, 8:12pm » |
Quote Modify
|
on Mar 2nd, 2009, 5:50am, Eigenray wrote:
How is the above result possible?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
F(n) = maxk<n C(n-1,k) F(k) F(n-1-k).
Compared to the other formula it's not surprising. Attached are the plots of { C(n-1,k) F(k) F(n-1-k) : 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 2nd, 2009, 10:25pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print