#15 資料結構 Tree

Tree 應該是我們所需要介紹的最後一個基礎的資料結構了.在資料庫的領域中,你可以看到 Tree 在那裡發揮的淋灕盡致.以我個人來說,我喜歡把 Tree 看成是一種 List 的變形金鋼.前面在談論到 List 時,你可以發現 List 的元素後面只會接著一個元素,就這樣一個一個串接下去,這種情況就可以用在作業系統的檔案儲存.你可以把一個檔案想成是一個 List,而檔案的內容就會依照固定的大小分割成很多個元素,然後依照順序排好串在一起,這些元素就會散落在硬碟空間中,他們不需要排列在一起,所以同一個檔案的內容在放置時,可能是最後的元素放在硬碟空間前面的位置,因為元素之間都有一個 link 記錄下一個元素的位置在那裡.

對 List 來說,如果一個元素有一個 link 的空間來記錄下一個元素在什麼地方,這稱為 Single link list,也就是說元素往下走了之後就回不來了,除非從頭開始.如果一個元素有兩個 link 空間,一個用來記錄下一個元素在那裡,另一個用來記錄上一個元素在那裡,這稱為 Double link list,可能在一個元素上往前走或是往後走,但這種的實務上的應用比較少些.對於 Tree 來說,它有多個 link 可以記錄下一階層的元素在那裡,所以用畫圖來表示的話,看起來就像下圖.


以上圖來說,Tree 的資料結構是:

Class TreeNode {
    public TreeNode left;
    public TreeNode middle;
    public TreeNode right;
    public string Data;
}

一個元素可以連結到三個元素,這個跟 List 的元素只有連結到一個元素是不太一樣的.也許你會提出問題,連結到一個元素和連結到三個元素或是更多的元素有什麼差別呢 ? 差別當然很多項,以我目前來看,我覺得最大的差別在於找到元素的速度.舉個例子,如果你用一個 List 來儲存一系列的數字,即便是這些數字已經依照某一個規則排列好,你在找時還是要從 List 裡的第一個元素開始,然後一個一個往下找.所以,如果都沒找到的話,你所花費的時間複雜度就是 O(n).現在,相同的數字依照某個特定的規則製做成 Tree 的結構,而當你找某個數字時,只要從 TreeNode 某一個節點繼續往下找即可,所以每當經過一個節點往下一階層時,你就已經捨棄了 2/3 的內容,只剩下 1/3 的內容要找.所以找起來的時間複雜度是 O(logN),這裡的 log 是以 3 為底,因為 TreeNode 可分為三個節點.

這時你可能會認為如果 Tree 在搜尋資料上是這麼好用的話,那我們是不是可以多用 Tree 少用 List ? 這就很難有一個正確答案了.雖然 List 的搜尋時間複雜度是 O(n),不過建立 List 是相當簡單的,但要建立一個 Tree 就不像 List 那麼單純了.如果你建了一個 Tree 而只拿它來用一兩次的話,這實在是不太符合效益原則.而且,Tree 的結構是適合用來做資料尋找的速度加快用的,而不太適合用來儲存資料,你想想如果今天有一堆數字要存在電腦裡,你把它儲存成 Tree 的結構,而接下來要把所有的內容讀出來,你覺得 Tree 結構所採用的方法會比 List 或 Array 來的更方便和簡單嗎 ? 答案顯然是不會的.再說,你把資料弄成 Tree 結構來儲存,在空間使用上並沒有佔到任何便宜.

所以,通常你看到一些資料索引的技術背後的基礎資料結構一定會採用 Tree 結構,原因就是加速資料尋找速度,但真正的資料並不會用 Tree 結構來儲存,只是索引所使用的資料是以 Tree 結構來儲存.許多資料庫的產品為了加速資料尋找的速度,便採用了許多 Tree 結構.我們這邊講的是一個較廣泛的 Tree 結構,在不同的應用情況下,會有特製的 Tree 做為在那些特定情況下的解決方案.以後的文章內容會再談到那些細節.

Share:

0 意見:

張貼留言