AVL 樹計數問題：n 節點 AVL 樹的形態數動態規劃解法

問題重述

AVL 樹定義：任意節點左右子樹高度差 ≤ 1。給定 n 個節點，求不同形態的 AVL 樹數量。例：n=10 時答案為 60。要求高時間效率。

動態規劃狀態定義

設 `dp[n][h]` 為節點數為 n、高度為 h 的 AVL 樹數量。

轉移方程

考慮根節點左右子樹高度組合：

• 情況一：左子樹高 h-1，右子樹高 h-1 → 節點數分配 `m1 + m2 = n-1`
• 情況二：左子樹高 h-1，右子樹高 h-2 → `m3 + m4 = n-1`
• 情況三：左子樹高 h-2，右子樹高 h-1 → 對稱，乘 2

合併：

dp[n][h] = Σ dp[m1][h-1] * dp[m2][h-1]   // 兩邊高度相同
         + 2 * Σ dp[m3][h-1] * dp[m4][h-2] // 高度差 1

其中 `m1+m2 = n-1`，`m3+m4 = n-1`，且所有 `m ≥ 0`。

複雜度分析

• h 最大約 `log_φ(n)` (φ≈1.618)，即 O(log n) 層。
• 每層 n 狀態，轉移枚舉 m 需 O(n)。
• 總複雜度 O(n² log n)，對 n ≤ 幾千完全足夠。

初始條件與邊界

• `dp[0][0] = 1` (空樹高度 0)
• `dp[1][1] = 1` (單節點高度 1)
• 其餘 `dp[0][h>0] = 0`，`dp[n>0][0] = 0`

最終答案

對給定 n，答案為 `Σ_h dp[n][h]`（所有可能高度之和）。

結語

AVL 樹計數是經典的「樹形 DP + 高度狀態」問題。掌握「以高度為維度」的 DP 設計思路，可解決多類平衡樹計數變體。