#93 平衡樹系列 - AVL Tree

在前面的資料庫文章裡曾介紹過 B-tree，一種平衡的搜尋樹，利用樹狀的結構來達成快速尋找的目的，而且因為是平衡的，所以從 root 出發到每一個樹葉的尋找成本是一樣的，這也是必要的，畢竟資料庫引擎用公平的方式來對待所有的資料．然而，B-tree 的結構並非是 binary 的型式，因此這帶給它很大的彈性可以方便地達成一個完全平衡的狀態．在前幾篇的文章也談過了 binary search tree，若你看過的話，你會清楚地知道 binary search tree 和 binary tree 的不同．在 binary search tree 裡，因為在建立樹的過程中有一個很重要的特性，就是右邊子節點的值大於父節點，左邊子節點的值小於父節點，因此在建立樹或是尋找節點時，到達一個節點時，只需要選擇其中一邊，不是左邊就是右邊，所以也達到 "binary search" 的效果．如前面的文章所說，binary search tree 的特性並不保證樹結構本身是平衡的，所謂的平衡就是其結構會和 complete binary tree 很接近．因為 binary search tree 沒有這樣的特性，因此樹的結構很可能是 "歪" 的．

為了要防止這種 "歪" 的情況，在早期的電腦科學研究裡便出現了許多的點子和做法，其中一個稱為 AVL Tree．這是兩位前蘇聯時代的科學家所發明的方法．發明的時間都是在我們出生之前 (我猜想這部落格的讀者群應該沒人超過 60 歲)．首先，先把 AVL tree 的時間複雜度列出來．

Search: O(log n), Insert: O(log n), Delete: O(log n)，不論是 average case 或是 worst case 都是一樣的時間複雜度，超級完美的．這也是為什麼在上一篇章的 APCS 考題會拿像 binary search tree 的實做來用，因為就是這麼快．不論是刪除或插入，甚至尋找都是 O(log n)，為什麼可以這麼快呢? 接下來將來說重點了.

AVL Tree 是一種 binary search tree 的特例，所謂的特例是指 binary search tree 再加上一些其他的特性之後就能變成 AVL tree．而這一個特性稱為 balance factor．每一個節點上都會有一個 balance factor，它代表的是一個值，其值是右邊子樹的高度減掉左邊子樹的高度．例如:

source: Wikipedia

節點 F ，右邊高度為 1，左邊高度為 2，所以 F 節點的 balance factor 為 1 -2 = -1，其他的節點也是用同樣的公式而得．AVL tree 定義了每個節點的 balance factor 必須為 -1 , 0 或 1．透過 balance factor 的限制，我們能知道這一個樹就 "比較" 不會那麼歪掉了，因為右邊子樹和左邊子樹的高度最多只能相差 1 而己．為了確保這個特性能發生，在插入節點或刪除節點的過程裡便需要採取一些動作．而這些動作如下:

1. 往左轉

source: www.tutorialspoint.com

如上圖，節點 A 的 balance factor 是 2，因此必須降低它，由於這是 binary search tree，所以 C 的值大於 B，而 B 的值又大於 A，因此，要把樹技折下來的話，拿中間者來當新的父節點最好，於是以 B 為中心將 A 往左轉，所以就變成了最右邊的圖，這樣就符合了 AVL tree 的特性．

2. 往右轉

source: www.tutorialspoint.com

往右轉的情況剛好是和第一種相似，只是換另一邊而己.

3. 往左再右

source: www.tutorialspoint.com

第三種情況其實是前面兩種情況的綜合體．若你看懂前面兩個為何要那樣轉的話，我相信你也一定看的懂第三種．其主要目的就是要讓 AVL tree 的特性可以滿足．

最後第四種，可想而知就是往右再往左.

4. 往右再往左

source: www.tutorialspoint.com

第四種情況就是第三種的另外一邊．只要你懂第三種情況，那麼第四種情況自然也不會是問題．

你可能會問我，像這種 AVL tree 要應用在什麼地方．老實說，到處都是，許多程式語言在他們的 standard libary/SDK 裡都會提供這種平衡的 binary search tree．我在工作上時常會用到這類型的資料結構以快速建立資料和尋找資料．前一篇 APCS 的解題就是靠類似 AVL tree 這種的平衡樹才能將時間複雜度降到 O(n log n)．別以為 O(n²) 和 O(n log n) 相差不多，一旦輸入的數量到達數以萬計時，你的家用 CPU 就會告訴你他們之間有很大的差距了．

在 Wikipedia 上你也可以找到一個動態的圖來說明 AVL tree 在建立的過程中，這些節點是如何左轉或右轉來達成平衡．AVL tree 將達成平衡這件事分攤在節點插入和刪除的過程中，因為才使得插入節點，刪除節點和尋找節點都有相同的時間複雜度．這的確是很高明的做法，我們大家又再一次站在巨人的肩膀上來看見電腦科學的神奇之處．

閱讀全文

#92 今年一月份 APCS 程式設計第三題 - 切割費用

前陣子，我的小徒弟去報名他人生第一次的 APCS 考試，可以說是他學習電腦科學以來第一次的正式上機考試．一共有四題的程式設計題目，前面兩題算是簡單的，第三題算中等，第四題比第三題再進階一點點．這篇文章就來談談第三題的解題思考．

完整的題目在 https://zerojudge.tw/ShowProblem?problemid=f607 ，首先，要解題之前，請先確定自已己經百分百了解題目．這一個題目的解決過程可以分成下列 2 個部份,

1. 讀取輸入參數，因為輸入參數並非按照切割次序而輸入的，我們要進行切割時是按照次序來切割的．因此，我們必須對輸入參數做處理，以讓沒有次序的參數集合變成有次序的參數集合．

2. 每一次切割時，都需要知道左右兩端的長度，這樣才能算出該次切割的費用，而知道左右兩端的長度，這需要一個快速的行為才能符合題目的要求．因為題目提到切割次數最多會到二十萬次，並且棍子的長度可以到 10 ⁷ 那麼長.

有關讀取輸入參數的內容，基本上有兩種做法，可以把切割資料全部讀進來之後，再以切割次序做排序．若是這樣做，這個動作將花費 O (n lg n)  ，假設是用 quick sort. 除此以外，我們可以換個角度思考，題目給的切割次序不會出錯，也就是說當切割資料讀進來時，切割次序就是一種 key，不會重覆，因為第 n 次切割只會發生一次．所以可以用 (key, value) 的 hash table 來存放切割資料．由於 hash table 的 set , get 都是 O(1) ，所以這讀取動作將花費 O(n)．

因此，第一個部份的時間複雜度最小可以到 O(n).

接下來，第二部份是計算每一次切割的費用．可以想像正在發生第 k 次的切割，也就是我們要想一個快速的方法讓我們可以查到在第 k 次切割時，當時所在的位置往左邊和往右邊走碰到的第一個切割點. 假設一開始用一個 boolean array 來代表被切割的點，

index :  0    1    2    3    4    5  ......98   99  100    101    102    103  ........ n

value:   f     f     f     f    f     t  .....  t     f       f        f        t         f      .......  f

一開始 array 的都是 false ，被切割過的點就變成 true，假設第 k 次的點要切割在第 100 個位置，而 98 和 102 是 true，所以這一次的切割費用是 102 - 98 = 4．如果以程式的角度來看的話，你得寫一個 for loop 從 100 往右邊走，找到第一個 true ，然後再往左邊走找到第一個 true，然後再做減法．這樣的尋找方式是 O(n)，而這個會發生在切割資料的迴圈裡，假設切割資料是 m 筆，因此這一段的時間複雜度是 O(nm)，一旦 n 和 m 都很大時，這就相當於是 O(n*n)．而 n 最大的值會到 20 萬，因此 O(n*n) 是不能接受的．因此，用 array 做搜尋是不合格的，所以我們必須用其他的資料結構，並且這個資料結構所花費的成本要小於 O(n) (比 array 一個一個找再快).

這時候，答案其實已很明顯了，能夠比 array O(n) 還要快的只有 binary search tree O(lg n) 或是 hash table O(1) ．在這一個動作的過程中，我們需要能 "往左走" 和 "往右走" ，Hash table  顯然不會是個好選擇，因為 hash table 無法儲存元素之間的 "順序"，因此，就剩下 binary search tree 了．binary search tree 在儲存的過程花費 O(lg n) 時間，而尋找的過程也是花費 O(lg n) 時間，而且 binary search tree 的特性讓我們可以 "往左走" "往右走" 來找到最近被切割過的位置．因此，採用 binary search tree 之後，時間複雜度可變成 O (m lg n) ，如果 m 和 n 都很大時，就是 O( n lg n)，這個比剛剛的 O(n*n) 快上很多.

最後，以下的程式碼是我的小學徒提供的，在很大的測試資料下仍花費了 0.25 秒完成，雖然不是最快，但也符合了題目 2 秒內的要求.

閱讀全文

#91 如何寫有影響力的履歷表

根據 Facebook 社團上的成員資料，目前三百多位成員裡有將近 40% 成員的年紀在 34 歲以下，因此，希望這篇文章可以提供年輕人有關撰寫履歷表內容時的參考.

一般來說，我會把履歷表的寫法分成兩種，一種是屬於年輕工程師的寫法，另一種是資深工程師的寫法，我將年資不到十年的人定義為年輕工程師，所以可能是在 32 - 36 歲之間，就看你在幾歲從學校畢業．在這年資以下的人，撰寫履歷表時應該要著重在技能的部份．也就是說，你得在履歷表上說明你用過了那些工具與方法來製造軟體系統，以及你運用了那些專業知識 (課本上學的) 在你的工作上．比如，某個年輕工程師從事電商系統前端功能的開發，屣歷表上就需要清楚說明用 Javascript/TypeScript 寫了什麼東西，是否用到其他的 framework，如 Angular 等等，並且做過那些功能，如購物車系統，付款流程，購物體驗等等．把這些東西寫清楚來，讓看履歷表的人明確知道你過去曾用過的工具以及熟悉的產業環境是什麼，這樣能幫助雇主加快認識你的速度．

為什麼年輕工程師要寫這樣的內容呢 ? 因為年輕工程師通常被給予的任務是小而明確的，如解 bug 或做一些小功能．履歷表上寫一些技能類的事情可以幫助未來的雇主知道你過去做過些什麼，也能幫助雇主評估是否要找你來進行面試．

如果 32 - 36 歲以上的工程師 (超過十年的業界經驗)，理論上來說，在業界工作了十年應該要達到資深工程師的水準了．我猜想在台灣的公司對於職稱上的給定標準並沒有一致且較寬鬆，所以中小企業或是非資訊科技領域的公司做了三五年後就能得到資深工程師的職稱．在規模大且制度嚴謹的公司裡，要在三到五年內拼到資深工程師是件不容易的事情，資深工程師的履歷表就應該著重於有關 "影嚮力" 的事情，比如，製造一個付款交易系統，讓整個網站可以在一分鐘之內完成 n 筆交易，使得網站可以承受 m 個使用者的流量．再舉另一個例子，重新製造了購物車系統，讓原本客戶評價極差的用戶體驗變成零負評的新體驗，並且讓網站提升 n % 客戶滿意度．再舉另一個例子，製造了一套基礎建設程式庫用於處理公司內所有系統的溝通機制，將原本平均一分鐘執行時間的動作提升至十秒鐘完成．或是一個更利害的例子，製做了一個很利害的 open source software，放在 Github 上得到了 n 顆星星，造福了世界上許多的軟體工程師．透過這些簡單例子，我相信你一定明白我所謂的 "影響力" 是什麼意思了.

回過頭來，並不是說年輕工程師就不用寫影響力．對於年輕工程師而言，如果你可以寫出令人信服的影響力，一定要寫下來，因為那些都是能讓你換到新公司時談職位與薪水的利器．

不論你寫的是技能比較多或是影響力比較多，千萬要記得別亂寫或是誇大地寫．若有機會面試時，這些技能和影響力是很容易被檢查出來的，一旦面試官發現你在 "唬爛" 時，你有可能永遠不會出現在這公司的面試名單裡．

履歷表內容的基本上包含了你的個人基本資料，工作經歷，學歷，技能以及一些參考資料．以我的經驗來說，我會將影響力放在工作經歷的內容裡，所以每一個工作都會是一段描述，而不是一行文字只包含公司名稱，職位名稱和時間而己．通常來說，一到兩頁的履歷表就應該要把你自己說明清楚，過長的內容，雇主很容易跳過不看，因為有名的公司每天都會收到很多履歷資料，沒有人會把細節看完．同時也要告訴一些年輕的工程師，工作要慎選，常常換工作並不是一件好事情，技能的程度高低也許不會受到換工作的影響，但我相信影響力是需要時間累積的，若常常換工作，則很難說明與說服其他人你在短時間裡能在一家公司做出有影響力的事情! 所以，找新公司時要好好想清楚，工作經歷就像是學歷一樣無法抹去也無法作假的，因此，在換公司時也要好好想想你該如何在新公司做出影響力的事情．同時這個題目也可能當成你和你老闆一對一面談時間裡的內容．

Hope it helps,

閱讀全文

#90 淺談 Dynamic Programming (2)

 前面說過 dynamic programming 的應用很多，這一篇文章來說明其中一種應用，Maximun subarray sum．這個問題是在一個整數的 array 裡找一個連續空間的元素，其元素的總和的值是最大的．如下圖:

source: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

從 index 2 到 index 6 之間的元素總和等於 7，這個區間是這個 array 裡最大的區間總和. 要解決這個問題其實不難，因為用最直接的暴力法就可以解決了，其程式結構如下:

這一個暴力法的時間複雜度是 O(n*n*n) ，n 是 array 的長度. 如果 n 很小，影嚮不大，但若 n 很大，這一個運算雖然在空間複雜度很表現的很好，但浪費許多 CPU 的運算資源，因為許多加法的計算是重覆了. 將這個問題的時間複雜度降低的方法不只一種，在這篇文章裡，我們用 dynamic programming 的策略來試著降低時間複雜度．如前一篇文章提過的內容，dynamic programming 的策略在於用空間換取時間，所以我們必須找出在什麼地方可以減少重覆的計算．要減少重覆計算之前，我們可以先從暴力法來看到底真正的計算是花在什麼地方了. 從上述的程式碼，你可以看到決定 subarray 的總和值是從最裡面的迴圈來運算的，所以第一圈會計算 start = 0 , end = 0 的總和值，第二圈會計算 start = 0, end = 1 的總和值, 第三圈會計算 start = 0, end = 2 的總和值，以此類推下去．透過觀察，你便能發現第二圈要計算的內容在第一圈已經算過了部份答案，第三圈要計算的內容在第二圈已經算過了部份的答案，因此，最裡面的迴圈其實是重覆了做了許多相加.

Loop 1: -2 

Loop 2: -2 + -3 = -5  (Loop 1 + -3)

Loop 3: -2 + -3 + 4 = -1 (Loop 2 + 4)

Loop 4: -2 + -3 + 4 + -1 = -2 (Loop 3 -1)

因此，透過以上的運算呈現，便能知道最後一個迴圈是可以去除的．我們只要將上一圈計算後的內容先暫存起來，留到下一圈時便能拿出來用，直接做一次加法就可以得到這一圈的答案了．因此，那個查表法的 "表" 也只不是一個臨時的變數，在空間複雜度上並沒有增加，而時間複雜度卻降了一階變成了 O(n*n)，如下列的程式碼.

接著，或許你還會問，空間複雜度還仍再降嗎 ? 剛好這一個題目是可以的，它的名字是 Kadane's algorithm，這個演算法在許多讀者還沒出生之前就已經發明了，這演算法能用 O(n) 的時間複雜度解決這問題，而發明人是一位教授，現在已經非常高齡了. 若你晚些才看到這篇文章, Kadane 教授也許不在人世了，我們大家都是站在巨人的肩膀上.

最後，你可能會問這個演算法我們該用在那裡．這完全取決於你是否會遇到類似的題目．如果你遇到一個問題，而這問題剛好可以 Reduce 成 maximum subarray sum 時，Kadane's algorithm 便能幫助你寫一個超快速的程式來解決問題，例如，你老闆要你找出過去十年裡，那幾個連續的月份其營業額是最好的．

Dynamic programming 的策略確實應用在許多地方，未來介紹更多的主題時，一定都還會碰到 dynamic programming 策略所產生的解法.

閱讀全文

#89 淺談 Dynamic Programing (1)

Dynamic programming 是大學部演算法課程裡相當重要的一個主題，也是典型用空間換取時間的策略．但奇怪的是，這個策略一點也不 dynamic ，一點也不 programming．老實說，我不知道為何這個策略叫 dynamic prograaming，我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.

Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子．Fibonacci number 是以數學多項式來表達的數字集合，以數學式來表達就可以寫成如下:

F(n) = F(n-1) + F(n-2) 

也就是說求第 10 項 (n=10) 的答案時，你必須要先算出來第 9 項和第 8 項. 如果要求第 1 項呢 ? 難道要找出第 0 項和第 -1 項嗎 ? 在 Fibonacci number 上，我們會為這個 number 定義起始點，也就是說第 1 項和第 2 項的值是早被確定的，往後的項次皆由這兩項為基礎而算出來，所以不會有第 -1 項的情況. 假設, F(0) = 0, F(1) = 1 ，那麼數列的答案如下:

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3 

F(5) = F(4) + F(3) = 3 + 2 = 5 

F(6) = F(5) + F(4) = 5 + 3 = 8  以此類推

當你要算第 n 項時，就按以上的方法一直算到第 n 項就能得到答案. 接著，數學公式 F(n) = F(n-1) + F(n-2) 寫出來了，那麼寫程式碼就變得相當簡單.

透過一個 recursive function 就能快速完成  Fibonacci number 第 n 項的計算程式．這一個程式碼沒有使用額外的記憶體空間，所以 space complexity 是 O(1)，但仔細看一下 time complexity，卻發現超乎想像的大，因為有許多重覆的步驟:

            F(5)  
          /     \
       F(4)      F(3)
      /    \    /    \
   F(3)   F(2) F(2)  F(1)
   /  \
 F(2) F(1)

上圖是整個 recursive 的關係. 意思就是，當程式在 F(5) 那一個層次要往下呼叫時，程式會呼叫自己兩次，並傳送 4 和 3 為輸入參數，當第一個 recursive call 再進去時，又會再呼叫自己，並傳入 3 和 2 為輸入參數，以此類推．所以你可以看的出來，有許多重覆的計算在這 recursive 的過程中一直發生．以上圖來說，F(3) 發生了 2 次，F(2) 發生了 3 次．當 n 是一個大的數字時，你就可以發現比 n 越小的數字，重覆計算的次數越多，並且是以指數趨勢來增加．上述的程式碼雖然很簡單，但是 time complexity 卻是很可怕的．上述的程式碼是由上而下計算下來的，假設我們繼續用由上而下的計算方式，改良此程式碼的方法就是將 "重覆" 的計算步驟讓它不要重覆計算．如上圖，如果 F(3) 只真正地被計算了一次，而 F(2) 只真正地被計算了一次，那麼就不會有重覆計算的事情了．為了達成這目標，最簡單的方法便是把計算後的結果儲存下來，等到要計算一樣的內容時，去 "查表" 即可．也就是說第一次 F(3) 計算的結果儲存下來，當程式遇到第二次的 F(3) 時，直接去查詢，若有答案，直接將答案拿來使用，這樣就不用計算了．同時，為了確保不會造成過多的 time complexity，我們也需要確認答案的儲存和查詢所花費的 time complexity 要非常小，如 O(1)．這種 "查表" 的精神也是 dynamic programming 所代表的策略．

若將上述的程式碼加入 "查表" 的功能，它將看起來如下:

或是直接改成由下往上計算

以上兩個程式碼雖然結構有點不太一樣，但都是用了一個 array 來記錄每一個項次計算的答案，因此 time complexity 省下來了，而且 space complexity 也增加了，但這樣的空間增加似乎是值得的．當然也可以再把上述的程式碼繼續改下去讓 space complexity 變的更小，不過這並不是這篇文章的重點．透過以上的簡單例子讓大家方便了解 dynamic programming 的 "查表" 意義是什麼．許多世界上有名的演算法都是基於 dynamic programming 的精神所發展出來的，例如你幾乎每天都在用的字串比對演算法就是基於 dynamic programming 所發明出來．

這篇文章用 Fibonacci number 的例子來說明 dynamic programming 的精神，這是相當簡單的例子，下篇文章我們用較難的例子來說明 dynamic programming 的用法.

閱讀全文

#88 資訊工程系的大學先修考試 APCS

在美國加拿大的大學入學測試中心成立了一種測驗，名為 Advanced Placement，裡面分成多個不同的專業考試，主要用來測驗高中生在該專業領域的 "程度" 如何．這些專業領域如生物，歷史，物理，語言，統計等等，其中電腦科學也是其中一個專業領域．簡單地說，就是要測驗那些資優班的高中學生，當他們申請大學時，可以附上 Advanced Placement 的成績用來代表他們有多少的能力在這些專業領域裡．詳情可參考 https://en.wikipedia.org/wiki/Advanced_Placement

在數年前，台灣教育部也發動了一樣的計畫，其中電腦科學的專業是由台師大資工系來執行，詳情可參考 https://apcs.csie.ntnu.edu.tw/

到今年 2020 為止，大部份在台灣有比較好的資工系學校都會參考這個成績，並且設下了門檻，例如台大資工要求觀念題和實作題都要達到 4 級分以上．這個考試結果一共分為五級，依照學生答案的內容來分級．若要達成 4 級分的話，基本上要熟練一個程式語言，如 C++，並且會用基本的資料結構，如 Array, List 等，除此之外，還要知道如何寫 recursive code 來解決問題，例如 binary search 等．對於正在讀文章的你，可能已經工作多年，這些並不是什麼難事，但對一個高中生，除了要面對高中的課程，還要花時間學習這些 "課外讀物"，這的確不是件容易的事. 在師大的 APCS 網站裡，提供了歷史考題．我會在這網站裡貼出參考答案. 如果你是打算以後念資工系的高中生，或是你們家有這樣的高中生，歡迎你分享給他們.

程式實作題: 三角形辦別

日期: 2016/10/29

參考答案

程式實作題: 矩陣轉換

日期: 2016/3/5

參考答案

以上的答案是 C++ 搭配 STL，答案並不是我寫的，是我一位小徒弟寫的答案，他在二個月前剛升上高一，以他目前的能力要應付台灣 APCS 題目算輕鬆．我這位小徒弟是個小學霸，以後再來介紹我是如何訓練他電腦科學的知識.

以上兩題對於已經在工作的你來說應該都是很簡單的題目，只是一些基本的數學應用題．台灣 APCS 的歷史題目還有好多題，未來文章會介紹.

閱讀全文

#87 Binary Search Tree 簡介

在 "資料結構" 系列文章裡寫過了 Binary search ，也寫過了 Tree．Binary search 能幫助我們在一個 "排序" 好的資料序列做快速的資料尋找．Tree 提供我們一個資料儲存 (放置) 的結構，當這兩個碰在一起時，產生了一個相當有用的資料結構.

Binary Search Tree 的發明比起我和絕大部份的讀者的都還要來的老，它出現在 1960 年代，在那個電腦硬體仍不太發達的年代，這個超級有用的資料結構就被發明出來了．誠如之前談的 binary search 內容，當你要進行 binary search 時，有一個很重要的前提就是被尋找的資料需要以某種排序好的順序存在，不論是從小排到大，從大排到小，或是從中排到小，再排中排到大，只要是資料依照某種屬性而排序好，就可以進行 binary search. 它的尋找資料的時間複雜度也在前面文章提過了，是 O (log N) 的複雜度，因為每一次尋找都可以捨棄掉一半非尋找目標的資料，這對尋找是個很大的幫助．然後，別忘了剛剛說的前題，資料必需是以某種方式排序好的．若你要在一堆沒有排序好的資料，把它排序，再執行 binary search 來找資料的話，這顯然有點過頭了，因為光是較快的排序都要花費 O(nlogn) 時間．因此在使用 binary search 之前，資料已是排序好的方式存在則能馬上使用 binary search，

當要讓資料以某種排序的方式建立起來時，可想而知，在建立的過程中可能要花費較多的時間，畢竟這不是隨便把資料加上去就好，而是要找到一個適當的位置才能加上去，以維持排序的狀態．你可以想像一個 integer single link list ，當你要加資料進去時，你得找到適當的位置並執行 insert 的動作，如下圖所示:

因此，只要我們能找一個適合的資料結構將資料依排序的目標建立起來，binary search 就可以派上用場. 在 Tree 的應用裡面，有個基本的結構叫 binary tree，也就是每個樹節點除了資料本身的空間外，還有另外兩個空間，一個是指向左邊節點的空間，另一個是指向右邊節點的空間. Binary tree 本身並不涉及任何資料排序的概念，但若我們為它加上一個限制，資料大的往右邊節點方向去建立，而資料小的往左邊節點方向建立，那麼這個 binary tree 便存在了排序的特性，如下圖所示，在任一個樹節點上，若左邊存在一個節點，則左邊節點的值將比較小，同理，右邊節點的值將比較大.

當 binary tree 加上了 "順序" 的特性時，這時就稱它為 binary search tree. 當尋找資料的動作發生時，從 root 開始出發，假設我們在上圖的 binary tree 上找 44，我們會在 root node 往右邊走，因為 44 > 11．以此類推，只要經過兩個樹楖點，我們便能找到 44. 如前面所說，這個動作的時間複雜度是 O(logn). 在大部份的應用裡，這個速度已經夠快了．

此時，你可能會發現在 binary search tree 要找資料時, root 的值是很重要的，因為你可能會看到如下圖的情況,

如上圖，倘若我們選到了一個不適合的值來當 root 時，此時 binary search tree 就長 "歪" 了．所謂的歪並不是壞掉的意思，而是大量傾向某一邊造成不平衡的情況．所謂的不平衡的意思就是某一樹節點左邊的 subtree 和右邊的 subtree 在高度上有大的落差．這會造成搜尋成本的不平均．比如，若你要找 44，它剛好是 root，所以一下子就找到了，若你要找 7，中間要經過 44 -> 33 -> 11 -> 6 ，最後到 7，若是你要找 11，中間經過 44 -> 33 就到 11. 所以，每個節點被找到的成本存在的大差異，因為我們稱之為不平衡的樹．這是我們希望能避免的情況，畢竟你希望的是每一個資料在被尋找時，每個資料被找到的時間成本和平均成本是很接近的，這樣才是公平．倘若資料本身需要不公平的情況，那就另當別論了.

Binary search tree 幫助我們將資料能用某一種順序的方式儲存起來，並且在尋找時也能達成 binary search 的效果．有些程式語言的程式庫裡都會提到這一個好用的資料結構，例如 C++ 的 map 就是典型的 binary search tree 實作. 如果你常用的程式語言裡沒有提供 binary search tree 的實作，我強烈建議你應該要在網路上找找是否有其他人做好成熟度夠高的實作，因為 binary search tree 的應用實在很多而且很好用. 當然 binary search tree 並無法為你自動達成 "平衡"，所以才會有其他的資料結構產生用來解決這個平衡的事情，如 AVL tree, red back tree, B tree 等等. AVL tree, red black tree, B tree 也算是蠻有用的資料結構，不光是學術價值，其工業應用價值也是頗高，以後會寫文章來介紹它們.

閱讀全文

#86 貪心方法是最佳解 ?

最佳解? 這種解答是許多問題所追尋的目標．例如，在一個城市裡找到出發點和目的地的最短距離．直覺來看，若你沒有把所有可能的路徑列出來，你怎麼知道那一個才是最短的．再舉例一個例子，在一個 int array 裡面，找出最大值的元素位置．若你沒把所有的元素都拜訪一遍，你怎知道那一個才是最大的．這兩個例子雖然都是在找 "最佳解"，但是解法的思考卻不太一樣．第二個例子的思考是 "一條路"，而第一個例子是 "多條絡"．在 "一條路" 的情況下，對下一個步驟來說沒什麼好選擇的，只能一直往前走．然而，"多條路"的情況下，在什麼路口選擇什麼路，這對答案或執行過程會有很大的影響． 

前面已有兩篇文章簡單地介紹了貪心方法．這篇文章要討論的是利用貪心方法得到的解答會是最佳解嗎 ? 用一個簡單的問題來測試．假設郵局提供的郵票面值如下:

$10, $5, $2, $1, $0.5, $0.2, $0.1 

現在你要寄一封信，它所需的郵資是16.1 元，請問最少要用幾張郵票 ? 這是一個最佳解的問題，目的是要找最少的郵票數量. 使用貪心方法來解這問題，它所需的程式碼如下:

以上的程式範例就是一個貪心方法．從最大的面值一直嘗試到最小的面值，一直湊到超過所需要賺買的郵票面值. 得到的答案是 $10, $5, $1, $0.1，需要四張郵票，面值是 10, 5, 1, 0.1 剛好能湊到 16.1，並且也這麼湊巧，四張郵票剛好是最佳解.

如果把郵票的面值改變，新的郵票面值有 

$5, $3.7, $3.1, $2.9, $2.3, $2, $1.7, $1.3, $1, $0.5, $0.2, $0.1

當我們再用同樣的程式去執行時，得到的答案會是 $5, $5, $5, $1, $0.1 ，需要 5 張郵票．但你認真排列之後，你會發現有一個更好的答案，那就是 $5, $3.7, $.3.7, $3.7，只需要 4 張郵票即可．此時便可發現貪心方法並無法保證我們一定能夠得到最佳解．如果得到最佳解，只能說題目本身的特性剛好能讓貪心方法得到最佳解而己．

從第一個問題來看，最佳解的答案有幾個特性

1. 答案最多一個 $0.1，因為若有兩個以上的 $0.1，便可以用 $0.2 來替代．

2. 答案最多兩個 $0.2，因為若有三個以上的 $0.2，便可以用一個 $0.5 和一個 $0.1 來替代.

3. 答案不會存在兩個 $0.2 和一個 $0.1，因為可以用一個 $0.5 替代.

還有一些其他的特性可以類推而得．同時，第二個問題可以用同樣的方式來找出最佳解的特性．第二個問題的其中一個特性就是，不該出現兩個 $5, 一個 $1 和一個 $0.1，因為可以用三個 $3.7 來替代，所以我們用貪心方法所得到的答案便不會是最佳解．

閱讀全文

#85 如何聘用適合的軟體工程師

如果你是一個團隊的領導者，尋找適合的軟體工程師一定是你份內工作裡不會缺少的一項任務．我這邊採用 "適合的軟體工程師" 而不是用 "優秀的軟體工程師"，其主要原因在於每個團隊的任務與能力不同，所以無所謂的優不優秀，只要是適合的人，對你團隊來說都是優秀的．

人們常說 "物以類聚"，這句話適用在許多人類的活動裡，對於建構一個軟體開發團隊而言，其實也是適用的．真正優秀的工程師對於技術含量低的工作通常不見得感興趣，相同地，能力不好的工程師也無法在技術含量高的團隊裡存活下來．這些原因可能來是一個現實的條件 - 薪資．

一般而言，薪資高的工作對於工程師的品質也會要求較高，相同地公司付出的薪水也會比較多．這是一個很簡單的經濟學原理 Supply-Demand 的觀念．一個健全的社會裡都是有這樣的現象．因此，身為團隊領導者的你首先必須思考一件事情，你需要什麼程度的軟體工程師．在你設定下了一個範圍之後，接下來的問題便是該如何衡量一個軟體工程師是否適合．

以下是我的做法，已經行之有年了，這些做法並不是我發明的，只能說是被 "同化" 後的結果.

1. 設定基本功夫的內容

既然是從事軟體開發的工作，你得先確保來面試的人具備基礎的資料結構與演算法的頭腦. 若是你資工相關科系畢業的，你應該能明確深刻的體驗到軟體工程師的工作就是將專案中的問題轉換成程式可以操作的模型，然後在電腦的架構下，不斷地在這些可操作的模型上做 "資料處理" 的動作，最後將結果產生出來．在這過程中，了解資料結構是一件非常重要的基礎．你可以從前面的文章裡了解到一個軟體工程師對資料結構的熟悉度將決定了程式的好壞 (Time complexity and Space complexity)，最終將會影響到整個專案的品質．

如果你團隊的工作是一般簡單的資料處理網站，使用者在表單上輸入資料，然後在其他表單上輸出資料．類似這樣的工作，你至少得確認你的軟體工程師懂得 Array, List, Stack, Queue, Hash table 這些基本的資料結構以及相關的應用．如果你團隊是製造一個資料庫引擎，那麼 Tree/Graph 的操作與相關應用將會是你團隊裡所需要的最基本的功夫．

透過考試來了解面試者的情況是最快速的方法之一．但我通常不建議拿一般市面上的考題．我建議的方式是準備一個在你過去的專案經驗裡值得拿出來當考試的題目．這是一個真實世界的問題，所以題目內容是容易能面試者明白為什麼是這種考題，同時也能讓面試者體會到未來有機會進來工作時，面對的情況這類似是這樣．通常準備一個簡單的和一個難的題目．

2. 設定操作工具的熟練度內容

世界上有許多程式語言以及相關許多不同的產品與工具．如果你需要的是一個可以盡快上戰場協助團隊的軟體工程師，那麼你便需要確保來面試的人員具備相關工具的知識與熟練度．例如，團隊的工作裡需要大量用到 Visual Studio/Microsoft SQL server 來進行專案開發，則你必須確認面試的人們對這些工具是熟悉的．最簡單的方法就是上機考．透過上機考的過程，你便可以清楚知道面試者對一個工具操作的熟悉度是在什麼程度．

3. 設定其他所需知識的領域

若專案是用關聯式資料庫做為 repository 時，你必須確定面試者具備 ER Model 的知識以及相關的知識，如 Index 的設計等. 若專案是用物件導向的方法來開發時，你必須確定面試者明白什麼是 class, object, 以及其他物件導向的原則與應用．同樣地，透過考試是最能直接明白面試者的情況．我在這邊也是給相同的建議，那就是考試的內容最好是團隊過去所面臨過的情況，分別找出簡單與難的問題來做為面試題目．

4. 設定人格特質

每個團隊都有一種 "文化"，這種文化的事情實在困難說清楚，而這種文化確會大大地影響整個團隊的產出和品質．身為團隊領導者的你必須了解到團隊的文化是什麼，然後將這些文化融入在團隊的運作過程中．比如，沒有經過 review 的 code 不能 check-in source control, 沒有加上 unit test 的 function 不能 check-in source control．類似這樣的事情讓面試者了解到團隊運作是有規則地運行．因此，態度散漫或不夠嚴謹的人自然無法能適應這種文化．

分享一個以前的經驗，我多年前參加一個公司內部的面試，面試的過程中，那位老闆不斷地提出許多問題來轟炸我的思緒，除了看我的反應以外，也看我能不能耐住性子來穩健地解決問題．他們團隊的工作是一個線上問題支援的網站服務，所以工程師們必須 on-call 並且有抗壓的能力.

一個適合的軟體工程師除了要寫出符合團隊期待的程式碼品質以外，還要執行團隊所規定用來幫助便於軟體管理的事情．要盡量讓一切的團隊活動都是在可受控的範圍內，這是團隊領導者非常需要的．

最後，找工作是緣份，找到適合的軟體工程師也是一種緣份．千萬別為了補滿工程師的人數而濫芋充數，因為最後倒霉的將是整個團隊，這是團隊領導者最需要注意的事情之一.

閱讀全文

#84 程式設計的簡約格式 - 減少程式碼縮排

最近在 code review 的過程中，總是常常會看到一些令人驚喜的事情，其中一件事情和程式的寫法有關．有時候是邏輯可以在簡化，有時候是 coding style 上可以在簡化以便閱讀．首先來看 coding style 可以簡化的部份．在寫程式的過程中，有時會因為業務邏輯面的複雜而造成會寫出多個 nested if statements 的情況，如下面的例子



上面的程式碼其實沒錯，也算方便閱讀．也許是我個人的因素，遇到 nested if 的時候，我會儘量地朝向少點縮排的方式前進. 除此之外，第 7 行和第 13 行是回傳一樣的答案．在程式寫法上可以將他們結合在一起，因為那是一個 "業務邏輯"，一般來說，我們希望同一件事情只要發生在一個地方．因此，可以將上述的程式碼改成如下:



一個 if 配合上多個檢查條件，我自己覺得這樣閱讀起來比上述的語法好些.

再來看另外一個例子.

原本的程式碼如下:



同樣的，這程式也沒錯．不過，閱讀起來有點 "階梯"．因為當我們閱讀時，大腦會產生那種 "階梯"，如果 if true part/false part 的內容物很多程式碼，我們還得仔細看縮排才知道下一行要跑到那繼續看．

其實，只要動一點腦筋想一下就可以把它寫的更簡單，如下



這樣的寫法是一樣的邏輯，而且是不是覺得更方便閱讀呢 ?

在寫程式的過程式，會常用到 if..else.. 是很正常的事情，然後這也代表你的業務邏輯將分成兩塊，而這兩塊的內容是獨立而不會互相干擾的，所以這兩塊的內容基本上不會重覆．若有重覆，那就是一般所謂的 duplicated code bad smell．另外，利用減少 "縮排" (indentation) 的技巧也能讓程式碼達到更方便閱讀的地步．

閱讀全文