題組內容

【題目二】 在 108 課綱的資訊科技領域中，運算思維常透過生活化的情境來引導學生 理解抽象的資料結構。請參考利用「彈珠檯」落下的路徑設計一款名為「二元搜尋彈珠台」的運算思維教具。
規則如下：彈珠台內部的阻擋釘排列成一棵「二元搜尋樹(Binary Search Tree)」， 每個節點都有一個阻擋釘並標示一個整數值。當一顆標示著數字 X 的彈珠從最上方(樹根)落下時，若 X 小於該節點的數值，彈珠會往左邊的通道滾動；若 X 大於該節點的數值，則往右邊的通道滾動。請依據資料結構原理，回答下列問題：

2. 如果我們刻意調整輸入阻擋釘的順序，改為從小到大依序輸入：10, 15, 25, 30,35, 40, 50, 55，請說明這樣建立出來的彈珠台(二元搜尋樹)會呈現何種特殊形狀？在這種最差情況下，搜尋特定數字的時間複雜度為何(請以 Big-O 符號表示)？