《算法導論》ʚ讀書筆記&淺析ɞ 第十五章 - 最優二叉搜尋樹(包含js版代碼實作)

背景簡介

關于二叉搜尋樹

關于最優二叉搜尋樹，算法導論給了一個生動的例子。以下是描述截圖：

從上述的截圖中可以知道搜尋一個單詞是有搜尋成本的，我們将它定義為

dx

代表僞節點(正常節點都未命中時的虛拟節點)

pi

第i個節點命中的機率

qi

第i個僞節點命中的機率

舉個例子：

第2個節點的搜尋代價 = (K2深度+1)*P2 + (D2深度+1)*Q2 =

(0+1)**0.10 + (3+1)**0.02

我們需要找出期望搜尋代價最小的二叉搜尋樹

算法思想

我們假設這棵樹(T)是最優二叉搜尋樹,那麼它的子樹必定也是最優二叉搜尋樹。可以用反證法來了解這個問題，假如它的子樹不是最優二叉搜尋樹(假定為

a

)，我們将其替換成最優二叉搜尋子樹(假定為

b

)。那麼

b

的搜尋代價一定是小于

a

的，那麼原來樹T的其他搜尋代價假設為

t

t+a > t+b 與 假設這棵樹(T)是最優二叉搜尋樹 是相違背的

是以問題就變成了(正向思維):求T的最優二叉搜尋樹 = T的最優二叉左子樹 + T的最優二叉右子樹 + 根節點,遞歸式就有了。

假定求解ki~kj節點的最優二叉搜尋樹,其根節點為kr

假定期望搜尋代價為e[i,j]

假定ki~kj的期望搜尋代價之和為w[i,j]

這裡分為兩種情況

1. j = i - 1 表示子樹沒有節點 隻有僞節點 是以 e[i,i-1] = qi-1
2. j≥ i-1 的情況比較複雜

當原來的樹結構發生變化 在他們上面多了一個r節點的時候 看下圖的變化

子樹所有節點的深度都+1了，會增加搜尋代價

是以可以得到下圖所示的公式

整理一下之後可以得到

最終我們可以得到

算法過程

根據上述的過程 我們需要 e ，w，root 三張表避免重複計算

let e = newTable(n + 1, n + 1)
    let w = newTable(n + 1, n + 1)
    let root = newTable(n, n)
           

處理j=i-1的情況

for (let i = 1; i <= n + 1; i++) {
        e[i][i - 1] = q[i - 1]
        w[i][i - 1] = q[i - 1]
    }
           

需要三層循環(與矩陣鍊乘幾乎一模一樣)

1.周遊1-n各個長度的情況

2.可以了解為同樣的l長度 滑動視窗 例如 12，23， 34， 45，

3.周遊每個r的情況取最小值

代碼實作

//生成二維數組
function newTable(m, n) {
    let arr = [];
    for (let i = 0; i <= m; i++) {
        let arrInside = [];
        for (let j = 0; j <= n; j++) {
            arrInside.push(0);
        }
        arr.push(arrInside);
    }
    return arr;
}

//生成對照表
function createTable(p, q, n) {
    let e = newTable(n + 1, n + 1)
    let w = newTable(n + 1, n + 1)
    let root = newTable(n, n)
    for (let i = 1; i <= n + 1; i++) {
        e[i][i - 1] = q[i - 1]
        w[i][i - 1] = q[i - 1]
    }
    for (let l = 1; l <= n; l++) {
        for (let i = 1; i <= n - l + 1; i++) {
            j = i + l - 1
            e[i][j] = Infinity
            w[i][j] = w[i][j - 1] + p[j] + q[j]
            for (let r = i; r <= j; r++) {
                let t = e[i][r - 1] + e[r + 1][j] + w[i][j]
                if (t < e[i][j]) {
                    e[i][j] = t
                    root[i][j] = r
                }
            }
        }
    }
    return { e, root }
}

function OptimalBst(p, q, n) {
    const { root } = createTable(p, q, n)
    let tree = []
    const find = (root, i, j) => {
        if (i <= j) {
            let r = root[i][j]
            tree.push('k' + r)
            find(root, i, r - 1)
            find(root, r + 1, j)
        }
    }
    find(root, 1, 5)
    return tree
}

module.exports = OptimalBst