前陣子和團隊成員討論工作內容時，看到了一位特別的資料結構．老實說，我以前不知道這個結構，因此特別去查了資料，然後將它的內容寫在這裡．
在電腦科學中，組織數據的方式對於快速查找和使用數據至關重要。其中一種特別的數據結構稱為 K-D 樹（K-Dimension tree），主要用於在多維空間中組織點，非常適合應用於機器學習、電腦圖形和資料庫搜索等領域。現在，讓我們來看看 K-D 樹是什麼、為什麼被發明、它可以解決哪些問題，以及如何編寫 K-D 樹的程式碼。
假設你有一組在 2 維空間中的點（例如地圖上的座標），地圖是由 X, Y 軸所組成的．當你希望快速找到某個位置的最近點，K-D 樹就是一個很好的工具．K-D 樹是一種二元搜尋樹，它在具有 k 維空間中將點組織起來的能力。每一層代表一個維度，並且通過交替各個維度的分割，可以使得在空間內找到鄰近點變得更加容易。
所以,...
#97 Segment Tree
在 binary tree 的文章時曾提到從 tree 開始後的資料結構文章將會開啟另一個大門，看來許多問題可以透過 tree 結構來解決．今天要介紹的 segment tree 就是一個例子．
試想一個情況，在現實生活中一定常常會遇到一個工作，一堆資料裡面，在某一個特定範圍依照某一個資料特徵來尋找資料．例如，在公司組織結構裡，找出 A 老闆底下的員工數總和．假設你已經有了員工組織樹狀結構，第一件要做的事情便是尋找 A 老闆節點，找到 A 老闆節點後，再從這裡出發將所有子節點計算個數，便能得到答案．一旦這樣的查詢工作常常發生的話，你會發現前面說的動作並不能馬上回應答案，因為還是要對員工組織樹狀結構進行...
#95 Priority Queue 是不是 Queue ?
在日常生活的情況中，排隊是一件很常見的事．原因是提供資源的人少，而使用資源的人多．例如，一堆人到便利商站買東西，買完後要結帳，而櫃檯人員只有一個，所以結帳得一個一個來，因此買商品的人就得排隊．在此時，如果出現一個文化水準低落的人來插隊，想必你一定會很生氣去跟對方說．在便利商店的排隊結帳來說，插隊通常不是件好事，但日常生活裡，某些特殊情況下，插隊是需要的，比如在醫院的急診室，或是馬路上遇到救護車救火車之類的，這種特殊情況，不緊急的必須先讓給緊急的．當我們撰寫程式碼時，一般情況下我們會使用 Queue 資料結構來達成 "排隊" 的目的，然後，因應需求，如同急診室或救護車的例子，我們必須提供一個方法讓...
#93 平衡樹系列 - AVL Tree
在前面的資料庫文章裡曾介紹過 B-tree，一種平衡的搜尋樹，利用樹狀的結構來達成快速尋找的目的，而且因為是平衡的，所以從 root 出發到每一個樹葉的尋找成本是一樣的，這也是必要的，畢竟資料庫引擎用公平的方式來對待所有的資料．然而，B-tree 的結構並非是 binary 的型式，因此這帶給它很大的彈性可以方便地達成一個完全平衡的狀態．在前幾篇的文章也談過了 binary search tree，若你看過的話，你會清楚地知道 binary search tree 和 binary tree 的不同．在 binary search tree 裡，因為在建立樹的過程中有一個很重要的特性，就是右邊子節點的值大於父節點，左邊子節點的值小於父節點，因此在建立樹或是尋找節點時，到達一個節點時，只需要選擇其中一邊，不是左邊就是右邊，所以也達到...
#87 Binary Search Tree 簡介
在 "資料結構" 系列文章裡寫過了 Binary search ，也寫過了 Tree．Binary search 能幫助我們在一個 "排序" 好的資料序列做快速的資料尋找．Tree 提供我們一個資料儲存 (放置) 的結構，當這兩個碰在一起時，產生了一個相當有用的資料結構.
Binary Search Tree 的發明比起我和絕大部份的讀者的都還要來的老，它出現在 1960 年代，在那個電腦硬體仍不太發達的年代，這個超級有用的資料結構就被發明出來了．誠如之前談的 binary search 內容，當你要進行...
#83 最近搜尋清單資料結構
最近遇到一個特別的需求有關一種像 Queue 但又不是 Queue 的資料結構
需求如下:
1. 可以自訂清單數量大小
2. 內容一筆一筆的存放，但讀取時是後進先出
3. 如果存放時，該資料已存在，則讀取時它會先被讀取.
舉些實例來說明
以下為動作順序
Initialize as size of 5
Set 1
Set 2
Set 3
GetItems() ==> 資料是 3,2,1
Set 4
Set 5
GetItems() ==> 資料是 5,4,3,2,1
Set 6
Set 7
GetItems() ==> 資料是 7,6,5,4,3
Set 5
GetItems() ==> 資料是 5,7,6,4,3
Set 3
GetItems() ==>...
#48 老鼠走迷宮 (mouse maze)
在大學的資料結構的課程裡，大約在教過 Stack, Queue 和 List 這些基本的資料結構之後會有一個老鼠走迷宮的作業．這份作業說難不難，說簡單也沒那麼簡單，對一個正在學習資料結構的學生來說，花個一兩個晚上來寫這份作業是很正常的．如果寫程式正是你的工作，而且你以前沒念過資料結構的話，不妨試著做做看這份作業．
老鼠走迷宮的內容是，要隨機產生一個矩陣，矩陣的大小最好由使用者輸入設定的．然後在矩陣裡的每個位置也會隨機產生三種不同的地形，例如平地，河流與高山．你可以再設計其他不同的地形，老鼠在每一個地形上走動時會花費不同的體力，例如平地是 1 ，河流是 2，而老鼠是無法穿越高山．老鼠的出發點是矩陣的左上角，也就是 (0,0) 的位置, 然後終點在右下角，也就是 (n,m) 的位置，n,m 代表的是矩陣的兩個邊長．
你所要寫的程式是讓使用者輸入矩陣的大小，然後為矩陣的每一個格子隨機產生地形，接著老鼠從出發點開始移動，看看老鼠是否可以走到終點．因為地形中會有高山，所以老鼠不一定都會有一條路可以走到終點．然而，老鼠能走的路也可能不只一條能到終點，你可以試著找出一條就行了．
整個題目的重點在於兩個地方．第一，移動的方向要定出一套規則，第二，要能夠記錄走過的路跡．移動方向的規則可以用最簡單的方式來實行，除了在邊邊與角落以外的格子，每個格子都可以有八種移動方向，上，下，左，右，左上，左下，右上，右下．每到達一個格子時，就可以依照固定的順序來移動到下一個格子，如果在下一個格子都沒有路走或是每個方向都試過了，那就回到上一個格子．因此，路跡的記錄是很重要的，因為需要回到上一個格子．
以下我提供十多年前寫的版本
...
#42 資料庫基礎 - Index 所用的資料結構 B tree
在前面的文裡談了有關資料庫 Index，說明了為什麼 index 能加速尋找資料，也說明了 index 有那些種類．在這篇文中，將來簡單談一下 index 所使用的資料結構．
看了前面的文章後，想必你也可以很容易猜出 index 所使用的是像 tree 那樣的資料結構．在前面的文章中也談到了最基本的 tree 資料結構概念．tree 其實在電腦科學的領域裡應用的相當廣泛，不論是學術上或工業界裡，因為 tree 帶來的好處實在很多，但要把 tree 寫出來其實也不是一件很容易的事．不同的應用會衍生出不同的 tree，而在資料庫的 index 所採用的...
#34 資料結構 - 非電腦科系的工程師們，你們體會多少了呢 ?
我第一次念資料結構時是因為準備台灣的資工研究所考試而念的，當時為了考試再加上時間也不夠多，所以念的很匆忙，沒有太多的時間思考著這門課程的精華．後來，念了研究所之後，研讀了一些學術論文，才慢慢了解到資料結構的精華．在許多學術論文裡都是討論著許多真實世界上的問題，通常這些問題會用一個數學公式或模型來表示，所以接下來的內容討論就可以直接在這數學公式或模型上直接去模擬．而這類的數學公式或模型若要用電腦程式來表達時，通常會發展出適合的演算法與資料結構．所以，這類的論文看多了之後，反而有幫助自己漸漸了解資料結構的精華．
基本上，電腦有二個基本的東西，一個運算器，一個是儲存空間．運算器就是大家所知的 CPU，而儲存空間就是記憶體和硬碟，其中記憶體是速度快但記憶時間較短，而硬碟是速度慢但記憶時間較長．這兩個東西你可以想成他們是長長的紙條，運算器可以在這長長的紙條上寫下資料，也可以讀取資料．
資料結構基本上就包含了兩件內容，一個是你需要用的資料是要寫在紙條上的何處，另一個就是如何在這些資料之間進行讀取或寫入．舉個例子，之前的文章提到...
#15 資料結構 Tree
Tree 應該是我們所需要介紹的最後一個基礎的資料結構了．在資料庫的領域中，你可以看到 Tree 在那裡發揮的淋灕盡致．以我個人來說，我喜歡把 Tree 看成是一種 List 的變形金鋼．前面在談論到 List 時，你可以發現 List 的元素後面只會接著一個元素，就這樣一個一個串接下去，這種情況就可以用在作業系統的檔案儲存．你可以把一個檔案想成是一個 List，而檔案的內容就會依照固定的大小分割成很多個元素，然後依照順序排好串在一起，這些元素就會散落在硬碟空間中，他們不需要排列在一起，所以同一個檔案的內容在放置時，可能是最後的元素放在硬碟空間前面的位置，因為元素之間都有一個...
#14 資料結構 Queue
在基礎的資料結構裡，Stack有一個好兄弟，長的跟它有一點像，但是提供的行為結果卻剛好相反，它的名字叫 Queue．在 Stack 中有一個可以把資料放入的行為叫 push，而把資料讀出來的行為叫 pop，並且最重要的重點是最先放進去的資料將會後最後被讀取的，所以這是一種先進後出或後進先出的情況．
類似於 Stack，Queue 也提供了方法可以將資料寫進去和讀出來，習慣稱為 Enqeueue 和 Dequeue．而跟 Stack 最大的不同就是 Queue 先寫進去的資料將會是先被讀出來，是一種先進先出或後進後出的情況．
你可以在資料結構的課本看到以上的內容，也可以找到 Queue 是如何被實做的，通常來說用 Array 來實做 Queue 會比較單純一點，只要一個 Array...
#13 利用 Hash Table 來增加你的資料處理速度
還記得十多年前參加一個專案時，自己做了一件不好的資料處理方式，當時的我還不知道什麼是 hash function．在那時候專案部份的工作需要快速地處理大量的資料，透過資料庫連線讀取資料，然後再讀取相關的參考資料，再經過運算，最後把結果再寫回資料庫，如果你的方法是讀一筆寫一筆的話，那肯定會造成大量的資料庫 I/O，所以比較適合的方法是做批次的處理，也就是一次讀取某個足夠數量的資料筆數，處理完成之後再一次寫回去，這樣可以減少資料庫的 I/O，也可以讓程式運行起來速度可以快些．
以上的想法是可行的，但當時有一個小小的挑戰是有關參考資料，因為資料在運算的過程中必需依靠其他的數據才能計算，而這些數據多達 8 萬多筆資料，簡單的說，它是三個欄位構成，第一個是分行 ID，第二個是一個會計科目 ID，第三個資料值．
...
#12 利用 Hash Table 來改進 FindSum4()
在 #2 的文章裡曾寫到 FindSum4() 的 Optimization 寫法，其程式碼再重新呈現如下：
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional...
#11 如何快速搜尋資料 - 利用 Hash function/Hash table
前面文章講了 binary search，這篇文章來介紹另一個好用而且非常常見的分類方法，它叫做 Hash．談到 Hash 時，通常包含兩個部份，一個是 Hash function，另一個是 Hash table．在業界的產品上，如 .Net/Java 等，都有提供業界標準的 hash function 以上一些 Hash table 的應用，如 .Net 的 HashSet, Dictionary 等就是 Hash table 的應用．首先，我們先談 Hash function．
Hash function 有一個很重要的特點是運算快速，那要多快呢?...
#10 資料結構 List
List 一般稱為 Linked List，這樣稱呼是因為在 List 裡面的每個元素都是一個連結連到下一個元素，這也稱為單向的 Linked List，如下圖所示：
這種單向的 List 應用在許多的情況下，例如作業系統的檔案寫入到硬碟時所採用的方式就是這樣單向 List 的概念．每個 List 都是由一個或多個元素所組成，而每個元素都有相同的資料結構，以上圖為例，元素裡包含了一個 decimal 和一個 pointer，這個指標所代表的是下一個元素的記憶體位址．所以，如果你要找 List 裡一共有多少元素時，就必須要從第一個元素一直移動到最後一個元素才能得知這個...
#9 Binary search 的 Big O ?
這是一個相當有趣的題目，前面講了 Binary search，因為它利用資料已排序好的特性，所以每次在尋找時可以中候選資料的中間切入來尋找，所以它的 Big O 該如何評估呢 ?
我們之前講到，如果現在找資料的方法是一個一個找，也就是說有十個資料時，最多要找十次，有十萬個資料時，最多要找十萬次，因此我們知道這方法和輸入的資料量成正比，所以是 O(n)．
Binary search 的 Big O 顯然一定比 O(n) 要快，那到底有多快呢 ? 我們可以來觀察一下．每次 binary search 在進行尋找時會從候選資料的中間尋找，然後依照目標值的大小來決定下一次尋找的候選資料是在前面一半還是後面一半，所以每次尋找後都可以將一半的資料給排除，比如說一開始有 100 個資料，經過第一次尋找後，下一回的候選資料就變成...
#8 如何快速搜尋資料 - Binary Search
在以前還沒念電腦科學之前，對於快速搜尋這件事情完全沒什麼概念，唯一知道就是在一堆資料裡面一個一個找了，對於沒念過電腦科學的人來說，一個一個找是最直覺也是最簡單的方法．想像一個情況，一個 Array 裡面有一百個整數，假設每一個整數的值都不一樣，那麼我們想要知道這個 Array 裡面有沒有 77 這個數字，最直接的方法就是從 Array 的第一個元素找到最後一個元素，最好的情況是 77 這數字剛好在 Array 的第一個位置，那麼很快就可以找到了，若最壞的情況是 77 落在 Array 的最後一個位置或是 77 根本不在這裡面，那麼我們就必須從第一個元素找到最後一個元素．從我們之前講的...
#6 資料結構 - Stack - part 2
承接上一篇的內容，我們要用什麼方式來做 Stack 的 "容器" 呢? 我們前面提過 Array 和 List，你覺得那一個用來做為 Stack 的容器比較適當?
我們在前面談過 Array 和 List，兩者最大的差異在於物件位於記憶體上的位置是緊連在一起還是允許分散的．如果緊連在一起，則讀取速度快，如果是分散的，則讀取速度慢．光是這一點，我想 Array 就足夠成為我們做為 Stack 容器的人選了．接下來我們用一個簡單的模型來談如何用 Array 做 Stack 的容器．
上圖是一個 Array，這裡頭一開始宣告了 5 個空間，所以可以放...
#5 資料結構 - Stack - part 1
還記得以前工作時曾有個一個經驗．有一天，我到同事的辦公室閒聊，聊著聊著他就跟我說他正在做一個新功能，當時我們正在做 Windows desktop應用程式，在這個程式裡面有一個編輯功能的頁面，讓使用者可以輸入產品的許多資料，而我同事正在做的就是為每個編輯動作留下記錄，好讓他可以做出 "undo" 的功能，而且要能一直 "undo" 下去．接著，他展現給我看他的成果，一切都運作的蠻好．接著，我就很好奇問他程式碼是怎麼寫的，接著他就展示相關的程式碼給我，他用了一個 .Net 的 DataTable，然後在這個 DataTable 裡建立了相關的欄位，如動作的序號，資料名稱，資料內容．因此，只要使用者一變動了某一個資料後，這個 DataTable 裡就會多了一筆資料，當使用者執行 "undo" 時，就會從這個...
#3 我需要懂資料結構嗎 ?
如果你的工作是系統管理或是網路工程領域，那麼資料結構可能對你不會有太大的影響，如果你的工作是程式設計或資料庫方面的領域，那麼資料結構對你將會是很重要的主題．若你的工作是程式設計類或資料庫類，即便你沒念過書本上的內容，我相信你對資料結構也有基本的認識．資料結構可以說是整個電腦科學裡相當基礎的知識，如果你把電腦科學用國中國小數學來比喻的話，則資料結構就像小學的四則運算一樣的基礎，必須要了解它才能通往更高級的方程式．
以目前的電腦架構來看，你可以把CPU視為一個做運算的單位，比如做加法運算或除法運算等等，而記憶體和硬碟的空間就像是一條有限長度的磁帶，你可以將資料寫在這條磁帶上，而記憶體這條磁帶比較短，但它讀取寫入速度較快，硬碟這條磁帶比較長，它讀取寫入速度較慢，所以當 CPU 運算時所需要的資料都是在記憶體和硬碟這兩條磁碟裡．接下來，當...