The puzzle was to count the number of possible red-black trees on $n$ nodes.
Possible Solution
Red black trees have the following property:
For every node, the (max) height of the subtree at that node is no more than twice the min height. This condition is both necessary and sufficient.
This gives the max height to be at most $2 \lceil \log_2 n\rceil$
Each subtree is also a red-black tree.
This gives us a dynamic programming algorithm.
Let the number of red black trees of min height $h$ and max height $H$, with $n$ nodes be $T(n, h, H)$.
Now we can give a recursive formula by considering the possible number of nodes and the min and max heights of the left and right subtrees (which are red-black trees themselves), then summing the up.
This should give a polynomial time algorithm.
Note: I haven't tried it, but if you choose to, you should be able to verify it by checking with OEIS which has the sequence I believe.
Possible Solution
Red black trees have the following property:
For every node, the (max) height of the subtree at that node is no more than twice the min height. This condition is both necessary and sufficient.
This gives the max height to be at most $2 \lceil \log_2 n\rceil$
Each subtree is also a red-black tree.
This gives us a dynamic programming algorithm.
Let the number of red black trees of min height $h$ and max height $H$, with $n$ nodes be $T(n, h, H)$.
Now we can give a recursive formula by considering the possible number of nodes and the min and max heights of the left and right subtrees (which are red-black trees themselves), then summing the up.
This should give a polynomial time algorithm.
Note: I haven't tried it, but if you choose to, you should be able to verify it by checking with OEIS which has the sequence I believe.
No comments:
Post a Comment