式尋找可能的AVL樹數與n個節點

Question

讓節點的數量爲3。
如果A，B，C ...都在順序C> A> B，則可能AVL樹是： n=1 gives 1,n=2 gives 2..(look image)

正如我們所知道的BST，它是2n C n /（n + 1）。
有沒有人試圖推導出一個公式，可以找到在給定節點數時avl樹的數量。
示例問題：有11個節點的可能樹的數量是多少？

Answer 1

我懷疑這個簡單的公式存在。但你可以找到與動態規劃可能AVL株數，灌裝二維表，其中n爲節點的數量，h是樹高，再總結所有非零正節點條目：

F(n, h) = Sum[by all possible i]{F(i,h-1)*F(n-1-i,h-1)} + 
      Sum[by all possible j]{F(j,h-1)*F(n-1-j,h-2)} + 
      Sum[by all possible k]{F(k,h-2)*F(n-1-k,h-1)} 

說明：我們（h-1），或者與（h-1）和（h-2）樹，或者與（h-2）和（h-1）樹相連接，可以製作n個節點h高AVL樹， （h-1）棵樹。