The problem was to compute the number of AVL tree of $n$ nodes.
Solution
The solution is very similar to that of the corresponding problem for red-black trees.
Using dynamic programming, try to compute $T[n, h]$ the number of AVL trees on $n$ nodes with height $h$.
Now write a recursive formula based on the AVL tree properties, and you have an algorithm.
I will leave the details to you.
Solution
The solution is very similar to that of the corresponding problem for red-black trees.
Using dynamic programming, try to compute $T[n, h]$ the number of AVL trees on $n$ nodes with height $h$.
Now write a recursive formula based on the AVL tree properties, and you have an algorithm.
I will leave the details to you.
No comments:
Post a Comment