二元搜尋樹與堆積視覺化工具

將逐一插入值所建立的二元搜尋樹或二元堆積畫成圖。對於二元搜尋樹,會顯示走訪順序(前序、中序、後序)、搜尋某個值時比較的節點路徑,以及刪除節點後的形狀。對於堆積,可以確認陣列的第幾個位置放入哪個值,以及取出根節點後的排列。

值的序列

最多 40 個數字或 6 個字元以內的字串。全部為數字時依數值大小比較,否則依字元順序比較。

樹的形狀

    前序
    –
    中序
    –
    後序
    –
    層序(廣度優先,從上層依序)
    –
    高度(層數)
    –
    節點數
    –
    搜尋時比較的節點
    –

    高度以只有根節點的樹為 1 來計算(也有以根為 0 的算法)。堆積圖中各節點右上方的小數字,是以根為第 0 個的陣列索引:第 i 個的子節點為第 2i+1 與第 2i+2 個,父節點為第 (i−1)÷2 個(無條件捨去)。

    什麼是二元搜尋樹

    二元搜尋樹是一種二元樹,對任何節點而言,左子樹中的值都小於該節點,右子樹中的值都大於該節點。搜尋時從根節點開始,要找的值較小就往左、較大就往右,因此比較次數不超過樹的高度。插入值時也以相同方式往下走,在走到盡頭的位置接上新節點。以範例「50 30 70 20 40 60 80」會建立高度 3 的樹,60 經過與 50、70、60 的 3 次比較即可找到。

    走訪順序(前序、中序、後序)

    走訪樹中所有節點的順序有:先拜訪節點再走訪左右子樹的前序、依左子樹、節點、右子樹順序的中序,以及走訪完左右子樹後才拜訪節點的後序。以中序走訪二元搜尋樹,值會由小到大排列。後序會先處理子樹,因此用於刪除整棵樹或計算運算式樹(逆波蘭表示法);前序則用於複製樹等場合。從上層依序拜訪的是層序(廣度優先)走訪。

    刪除與偏斜

    從二元搜尋樹刪除節點時,若沒有子節點就直接移除,若有 1 個子節點就以該子節點接上原位置。若有 2 個子節點,則將右子樹中最小的值(或左子樹中最大的值)移到該位置,再刪除移出值的原節點。另外,若依序插入已排序的值,樹會只往一側延伸,變得像鏈結串列一樣,搜尋最多需要 n 次比較。為了避免這種情況,會使用每次插入或刪除時調整形狀的 AVL 樹、紅黑樹等平衡二元搜尋樹。

    堆積與陣列表示

    堆積是父節點的值大於等於子節點(最大堆積)或小於等於子節點(最小堆積)的二元樹,其形狀為由上層開始、由左往右填滿節點的完全二元樹。因此,若以根為第 0 個,從上層依序放入陣列,第 i 個節點的子節點就是第 2i+1 與第 2i+2 個,不需要指標即可表示。插入值時放在末端,一邊與父節點比較一邊往上移;取出根節點時,將末端的值移到根,一邊與子節點比較一邊往下移。兩者都只需與樹高成正比的 O(log n) 工作量,因此用於優先佇列與堆積排序。

    練習演算法題目

    將二元堆積以根為 a[0] 的陣列 a[0], a[1], a[2], … 存放,從上層開始每層由左往右依序填入。a[4] 的子節點與父節點為下列何者?

    1. A子節點為 a[9] 與 a[10],父節點為 a[1]
    2. B子節點為 a[8] 與 a[9],父節點為 a[2]
    3. C子節點為 a[9] 與 a[10],父節點為 a[2]
    查看答案與解析

    正確答案:A. 子節點為 a[9] 與 a[10],父節點為 a[1]

    以 a[0] 為根時,a[i] 的子節點為 a[2i+1] 與 a[2i+2],父節點為 a[(i−1) ÷ 2 無條件捨去]。i = 4 時,子節點為 a[9] 與 a[10],父節點為 a[(4−1) ÷ 2] = a[1]。以 a[1] 為根時,子節點為 a[2i] 與 a[2i+1],父節點為 a[i ÷ 2],因此確認採用哪一種規則很重要。由於堆積是完全二元樹,可以不用指標而以陣列表示,只靠索引計算就能找到父子節點。

    以根為 a[0] 的陣列表示父節點值大於或等於子節點值的最大堆積。對堆積 50, 30, 40, 10, 20, 35 加入45:先放在末尾,只要比父節點大就與父節點交換。操作後的陣列為下列何者?

    1. A50, 30, 40, 10, 20, 35, 45
    2. B45, 30, 50, 10, 20, 35, 40
    3. C50, 30, 45, 10, 20, 35, 40
    查看答案與解析

    正確答案:C. 50, 30, 45, 10, 20, 35, 40

    45放在 a[6],其父節點為 a[(6−1) ÷ 2] = a[2] = 40。由於 45 > 40,兩者交換,45移到 a[2]。下一個父節點 a[0] = 50 大於45,因此在此停止,得到 50, 30, 45, 10, 20, 35, 40。交換次數最多只有樹的高度,因此加入為 O(log n),取出最大值也同樣是 O(log n)。由於這個性質,二元堆積常用於實作優先佇列。

    以中序走訪(依左子樹、該節點、右子樹的順序拜訪)走訪二元搜尋樹時,拜訪到的節點值會如何排列?假設所有值都不相同。

    1. A依升冪(由小到大)排列
    2. B依插入樹的順序排列
    3. C依離根部由近到遠(由淺到深)的順序排列
    查看答案與解析

    正確答案:A. 依升冪(由小到大)排列

    在二元搜尋樹中,對任何節點而言,左子樹的值都比該節點小,右子樹的值都比該節點大。因此依左子樹、節點、右子樹的順序走訪,就會由小到大依序拜訪,結果為升冪。依離根部由近到遠排列,是逐層由左往右拜訪的廣度優先(層序)走訪。插入順序雖然會影響樹的形狀,但與走訪的順序並不一致。

    對空的二元搜尋樹依序插入 50, 30, 70, 20, 40, 60, 80。以後序走訪(依左子樹、右子樹、該節點的順序拜訪)走訪此樹時,順序為下列何者?

    1. A50, 30, 20, 40, 70, 60, 80
    2. B20, 40, 30, 60, 80, 70, 50
    3. C20, 30, 40, 50, 60, 70, 80
    查看答案與解析

    正確答案:B. 20, 40, 30, 60, 80, 70, 50

    根為50,左子節點為30(其子節點為20與40),右子節點為70(其子節點為60與80)。後序走訪先拜訪左子樹的 20, 40, 30 與右子樹的 60, 80, 70,最後才拜訪根部的50。50, 30, 20, 40, 70, 60, 80 是先拜訪節點的前序走訪,20, 30, 40, … 則是中序走訪的結果。後序走訪用於必須先處理子節點的情況,例如刪除整棵樹,或由算式樹產生後序式。

    對空的二元搜尋樹依序插入 1, 2, 3, …, 1000(不做平衡的操作)。在這棵樹中尋找1000時,從根部開始比較,到找到為止要比較幾個節點?

    1. A10
    2. B500
    3. C1,000
    查看答案與解析

    正確答案:C. 1,000

    依升冪插入時,新的值每次都成為之前最大值的右子節點,因此樹會變成只往右延伸的一條鏈(高度999)。1000位於最底部,因此要與 1, 2, …, 1000 共1,000個節點比較,與從開頭走訪鏈結串列相同,為 O(n)。若是平衡的樹,層數只有約 log₂ 1000 ≈ 10,因此使用 AVL 樹或紅黑樹這類在每次插入與刪除時調整形狀的平衡二元搜尋樹,最差也能維持 O(log n)。

    常見問題

    二元搜尋樹與堆積有什麼不同?

    二元搜尋樹規定了左右子樹的大小關係,適合搜尋任意值。堆積只規定父節點與子節點的大小關係,適合快速取出最大值(或最小值)。要在堆積中尋找任意值,必須檢查整個堆積。

    為什麼以中序走訪時,值會由小到大排列?

    中序走訪會在某節點之前先拜訪其左子樹(全部小於該節點的值),之後再拜訪右子樹(全部大於該節點的值)。這對所有節點都成立,因此整體會由小到大排列。

    高度要怎麼計算?

    本工具以層數計算,只有根節點的樹高度為 1。若以從根到最深葉節點的邊數計算,只有根節點的樹高度為 0。考試題目會在題目中說明採用哪一種算法。

    考試中會怎麼出題?

    日本基本資訊技術士考試等資訊類證照考試,常考依序插入值所建立的二元搜尋樹的形狀與走訪順序、以陣列表示堆積時的索引關係,以及加入值之後陣列的排列。請選擇範例,將圖與陣列的排列和自己的答案比較看看。

    相關術語

    二元搜尋樹 二元堆積 二分搜尋

    相關計算工具

    半導體、電子電路與資訊計算工具 →