1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| OPTIMAL-BST(p, q, n) let e[1 : n + 1, 0 : n], w[1 : n + 1, 0 : n], and root[1 : n, 1 : n] be new tables for i = 1 to n + 1 // base cases e[i, i − 1] = qi−1 // equation (14.14) w[i, i − 1] = qi−1 // 为了避免出错,只有一个非根节点时同样单独处理。 for i = 1 to n e[i, i] = qi-1 + pi + qi w[i, i] = e[i, i] + qi-1 + qi root[i, i] = i for l = 2 to n for i = 1 to n − l + 1 j = i + l − 1 e[i, j] = ∞ w[i, j] = w[i, j − 1] + pj + qj // equation (14.15) // 修改之处。 for r = root[i, j - 1] to root[i + 1, j] // try all possible roots r t = e[i, r − 1] + e[r + 1, j] + w[i, j] // equation (14.14) if t < e[i, j] // new minimum? e[i, j] = t root[i, j] = r return e and root
|