一道编程题,不太懂,求教

AVL树是指左右子树的高度差不超过1,现在有一颗n个节点的
AVL树,问这样的树有多少种,比如n=10,有60种。

avl

2个回答

dp[n][h]表示n个节点高度为h的AVL树的个数。
dp[n][h] = dp[m1][h - 1] * dp[m2][h - 1] + 2 * dp[m3][h] * dp[m4][h - 1]
其中 m1 + m2 = n
m3 + m4 = n
其中h是logn级别的,所以总的时间复杂度大概是O(n ^ 2 logn)。

Wintermelob
Wintermelob 能不能再说得清楚点啊,就是知道了dp[n][h]后,怎么做呢? 能给个代码就好了。我再想想这是不是对的。
3 年多之前 回复

递归问题,有一颗n个节点的AVL树有多少种可以转化为问已经有了一个根节点,求n-1个节点的AVL树有多少种
如果只有一个节点,那么只有1种。

Wintermelob
Wintermelob 能写下代码吗?
3 年多之前 回复
Wintermelob
Wintermelob 这样可以吗? 你算算10是不是等于60
3 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问