二元樹在排序的應用

Posted By Mr. Thursday

在〈由樹的前序、中序、後序走法來談資料結構〉文章裡面提到了演算法就像是做事情的方法,資料結構則是對應演算法可以運作的東西,譬如說刮鬍子有步驟一、步驟二、步驟三,但是要有刮鬍刀、插頭、以及鬍鬚,那些步驟才有運作的東西,甚至不同的刮鬍刀,也會讓同樣的步驟有不同的執行效率,或是連原來的步驟都要改變,譬如說不是電動刮鬍刀,原來步驟裡面插插頭的那一步,也就可以不用作了。演算法資料結構之間的關係也是如此,譬如說排序的演算法,可以用不同的資料結構來實現,好的資料結構,可能某一種排序演算法最適合,對其他種排序演算法,可能反而讓速度變慢。

因此,演算法資料結構,通常會一起考慮,而演算法每一步,也就是電腦可以實現的基本步驟所組成。譬如說兩個數字相加,或是把「樹」這個資料結構裡面的節點根據某種規則移動,都是電腦運算基本步驟所可以達成的。但是如果步驟是「改善排序的品質」的敘述,電腦可能就看不懂了,這時候就是程式設計師,把這些人看的懂的需求,轉換成電腦可以實現的步驟,也就是演算法和對應的資料結構,最後再用程式 (編程) (program),變成電腦真的可以執行的語言,達到最初想要執行的功能。那麼今天想要完成的功能是甚麼呢?「排序」,排序就是把原本雜亂無章的一堆東西,按照某種順序排好,譬如說圖書館裡面的書籍,按照書籍的編號有小到大排好,譬如說醫院的病歷,按照病歷號碼有小到大排好,譬如說一堆檔案,按照字母順序或是檔案時間順序有早到晚排好,這些都是排序的應用。那麼電腦要如何完成「排序」(sort) 這件工作呢?「二元樹」 (binary tree) 怎樣子應用在排序這項工作呢?

在〈由樹的前序、中序、後序走法來談資料結構〉裡面提到了「」的資料結構,也提到了樹的三種走法,並且用「二元樹」 (binary tree) 為例子來講解。二元樹就是一種樹,只是每個節點 (node) 都只有兩個子節點 (child node),看起來就像下面這張圖:

 

就這樣子,一層一層的樹枝分岔下去,只是每次只有兩個分岔,就變成二元樹 (binary tree) 了。假如子節點還有子節點,變成孫節點 (grand children node),那麼子節點和孫節點一起,可以稱做一顆子樹 (sub-tree) ,也就是看成有一顆比較小的樹,接在子節點的位置上面,這就是上圖裡面虛線三角形代表的部分了。

介紹了二元樹以後,我們已經有了資料結構。接下來就是演算法的步驟,要怎樣子透過二元樹,完成「排序」的功能。我們先假定要把一組正整數數字按照大小排好就好,假定我們看到了 1,5,3,2,6,7,4 這七個數字。我們每看到一個數字,就進行以下步驟:

(1) 從樹的樹根 (root) 開始,和每個節點比較

(2) 如果現在這個數字,比現在這個節點的數字小,往左邊的子樹 (sub-tree) 走,否則就往右走

(3) 重覆步驟(2) ,比較新遇到的節點,和現在輸入的數字。如果已經走到樹的結尾,就停止。

根據這三個步驟,假設已經排好了2,4,5,6,7,然後現在輸入一個新的數字 “3″。那麼上面這幾步執行的過程,可以用下面這個動畫表示:

sort1

假設3排好以後,我們又遇到了”1″,那麼接下來執行剛才演算法步驟的過程,會像下面這張動畫一樣:

 sort2

不知道各位讀者看完了這兩張動畫,是否有比較了解,二元樹怎樣子搭配剛才的排序演算法,把數字排好呢?不過怎樣子看的出來,這棵樹把數字排好了呢?我們只要用「中序」(mid-order) 的方式,把這棵樹拜訪一遍,就是由小到大的方式把數字排序好的唸法了。

譬如說第二張動畫,如果用中序拜訪這棵樹,就會得到1,2,3,4,5,6,7的結果,也就是說,雖然輸入資料的順序是4,2,6,7,5,3,1,但是透過二元樹,以及上面很簡單、電腦可以執行的三個步驟,我們就把數字由小到大排好了!

當然,這個演算法只有三步,每次比較數字大小之後,在二元樹上面不是往左就是往右,沒有其他複雜的步驟,但是執行效率就不是最好的了,怎樣子知道一種演算法的效率好不好呢?就等以後介紹其他排序演算法的時候,再一起比較說明吧!另外剛才演算法也省略了,如果兩個數字相等的情況。無論如何,如果只是簡單的排序應用,這個演算法搭配二元樹,應該就足夠了。

其他常見的排序演算法還有哪些呢?包括選擇排序 (selection sort)、插入排序 (insertion sort)、泡泡排序 (bubble sort)、快速排序 (quick sort)、合併排序 (merge sort)、以及正整數才能用的桶子排序 (bucket sort),有興趣的讀者不妨先用這個JAVA Applet動畫模擬器來看看各種排序方法的動畫。最後也找了一段Youtube的排序動畫影片:

最近似乎也是研究所考試的季節,順便祝福各位資訊相關的考生,演算法和資料結構都能越記越熟!

相關連結

演算法相關文章

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!