0
$\begingroup$

Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$. (We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number).

First of all of course we can calculate it via $dp[i][j]$ - number of tree with height $i$ and $j$ vertices, then we divide $dp[h][n]$ by $C_n$ and obtain the result, but it's hard to do using C++ (because $C_{40}$ is very huge and calculation will be incorrect).

Of course we can consider $dp[i][j]$ - is probability that tree has depth $i$ and contains $j$ vertices, but then dynamic step is slightly incorrect ($dp[i][j] = dp[i - k][h - 1] * dp[k][h - 1]$, but it also fail initial values of $dp[i][j]$).

Maybe I should reconsider my dp? Any ideas?

Improve this question
$\endgroup$
4
  • $\begingroup$ As I understand it, your question is: out of the C_n unique trees, what is are the number of trees of each height? (Or equivalently, what is the probability of choosing on of height exactly h, at random). Use a bigint library if you need to work with large numbers--a language that supports it natively like Python is one easy way to do that. What size inputs do you need an answer for? Putting HOW to answer your question aside, this seems like a bad model for what you're doing. "Choose a tree uniformly at random among all shapes" is probably an incorrect model for any real binary search tree. $\endgroup$ – Zachary Vance Nov 1 '20 at 23:20
  • $\begingroup$ Also I don't know an answer if DP is too slow, but I'd recommend checking "The Art of Computer programming vol 4" by Donald Knuth as a likely source of answers. He talks a lot about generating and counting trees in it. $\endgroup$ – Zachary Vance Nov 1 '20 at 23:23
  • $\begingroup$ What is your question? I don't see a question in your post. We are a question-and-answer site, so we require you to articulate a specific question - we shouldn't have to guess what your question is. "How to do something in C++" is off-topic here, but questions are algorithms are on-topic. $\endgroup$ – D.W.♦ Nov 1 '20 at 23:31
  • $\begingroup$ Another possibly useful fact: the average height of a binary tree with n nodes, is 2*sqrt(pi*n) [source: The Average Height of Binary Trees and Other Simple Trees, Phillipe Flajolet] $\endgroup$ – Zachary Vance Nov 1 '20 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.