data structure

這篇文章中,我們將要來說明堆積(heap)這種資料結構,但在說明這個資料結構前,讀者需要先了解二元樹這種資料結構,如果不了解的話,可以看看筆者的這篇文章。 資料結構—樹狀結構與二元樹 不過我們這邊也簡單的複習一下二元樹 ; 二元樹它是一種樹狀結構,但它要符合每個節點最多有兩個子樹這個特性,才能稱為二元樹。 在大概知道了二元樹後,我們就可以開始本篇文章的重點堆積heap。 堆積的原理 二元樹轉成堆積 程式碼實作 堆積 Heap 的原理 堆積這種資料結構,它是一種二元樹,而且要有以下兩種特點的,才能被稱為堆積。 任意節點小於(大於)它的所有子節點,最小(大)的節點一定在根上。 堆積是種完全樹。 完全樹 : 除了最低層外,其它層的節都都被塞滿。 我們畫個圖來看看,就可以很明顯的知道二元樹與堆積的差別,如下圖,左邊的堆積樹很明顯的,子節點值一定小於父節點,而二元樹的就沒這特性。 二元樹轉換成堆積 上面簡單的說明什是堆積,接下來我們這邊要來說明,如何將二元樹轉換成堆積。 傳統上有二種方法,由下而上與由上而下,我們本章節將說明由下而上的方法,不然文章會太長……。 這個方法的基本流程如下,我們以下說明都以max heap為主,也就是根節點為最大值。 計算出此棵樹的節點數量,假設為n。 在從其n/2節點(事實上也就是最後一個父節點)開始進行比較。 若子節點的值大於父節點,則相互對調。 若有交換,還比較在去子節點進行比較。 我們來舉個例子,假設我們有如下圖的二元素。 接下來我們開始說明他的轉換成堆積的流程。 最後下圖就是二元樹轉換成堆積的結果。 程式碼實作 最後我們來將來上述說明進行程式碼的實作,將二元樹轉換成堆積。我們先來簡單的複習實作二元樹。首先是二元樹的基本結構。 function Node(data, index) { this.data = data; this.index = index; this.left = null; this.right = null; } function BinaryTree() { this.root = null; this.count = 0; } 然後我們將要新增個方法,可以新增節點到二元樹中。 BinaryTree.prototype.add = function(node) { node.
圖學理論(graph theory)它源於1736年的數學家 LeonHard Euler ,它為了解決Koenigsberg bridge問題而發展出來的理論,雖然Koenigsberg bridge問題不是我們這篇的重點,但還是簡單介紹一下這個圖論中的著名問題。 在某個國家內,有條河經過兩個市區,並且在這條河中心上還有兩個小島,小島與河的兩岸有七條橋連接這,下圖就是該環境的模擬圖。 那麼這個問題是 ~ 在所有的橋都只能走一次的前題條件下,如何才能把所有的橋都走過一次。 雖然 LeonHard Euler 並沒有解決這個問題,但卻發現了新的研究領域圖論。 圖形結構之原理 圖(graph),是一種用來描述點與點關係的資料結構,也可以說是記錄關聯的結構,它和樹狀結構長的得像,而他們的關係在於 樹是一種圖 那什麼時後,它是圖而不是樹呢? 出現一個環時。 他沒有連通時。 一張圖會由數個節點以及數條邊所構成,節點與節點間使用邊來相接,在數學上通常定義成G = (V,E)來表示,其中V是所有節點所成的集合,而E代表所有的邊所成的集合。圖(graph)畫出來長的如下圖。 接下來我們來認識一些名詞。 頂點(vertex) : 上圖中的A、B、C就為三個項點。 邊(edge) : 上圖中那個每個項點的連線,就稱為邊。 相鄰(adjacent) : 例如上圖中的A與B就為相鄰的,其它的項點也都如此。 附著(incident) : 上圖中,我們可以說明,邊{A,C}與邊{A,B}『附著』在項點 A 。 路徑(path) : 代表某個項點到某個項點的過程。 簡單路徑(simple path) : 在上圖中 A 到 D 的路徑可能有ACBD和ABD,這時我們可以稱ABD為簡單路徑。 長度(length) : 一條路徑上的長度是指該路徑上所有邊的數量。 分支度(degree) : 例如上圖中,我們可以稱項點 B 的分支度為 3 ,但在有向圖中會分成外分支度與內分支度。 子圖(Subgraph) : 請看下圖。 圖的種類 基本上圖又可以分成下述幾重,要選擇那種來使用取決於你的問題。
在筆者的『基礎資料結構 3 — 樹狀結構與二元樹』的這篇文章中,我們介紹了樹的基本概念,也學習了如何遍歷樹的方法,在之前的文章中,我們有說到,如果要遍歷樹大至上有以下三種方法 : 中序追蹤 (in-order) : 先走訪左子樹,然後在根,最後在右子樹。(DBEAFCG) 前序追蹤 (pre-order) : 先走訪根,然後在左子樹,最後在右子樹。(ABDECFG) 後序追蹤 (post-order) : 先走訪左子樹,然後在右子樹,最後是根。(DEBFGCA) level-order : 先走訪第一層節點,再走訪第二層,最後會走到最後一層。(ABCDEFG) 補充: 這裡我們在補充第四種追蹤level-order,事實上它就是BFS,也就是一層一層的掃 那為什麼我們這裡要在拿來說一次呢 ? 因為我們之前實作的方法是用『 Recursion 』來實作。 有寫過程式的人大概會知道,在使用recursion 實作程式碼,常常有可能會發生memory leak事件,所以我們這篇將要來說明,如何不使用它,來實作以上三種 traversal。 中序追蹤 (in-order) 左 => 根 => 右 iteration 直接先深入最深的左子樹,並將行經的節點,存放到 stack 中。 然後深入到最後時,發現是 null ,開始從 stack 中 pop 東西出來。 接下來在從 pop 出的節點的右子樹開始重複第一個步驟。 /** * Tree inordrTraversal (no recursive) * Tip: 左根右 */ BinarySearchTree.
在這篇文章中,我們將要仔細的來說明樹(Tree)這個資料結構,它在計算機科學中非常的重要,有很多演算法都一定會運用到這種資料結構。接下來我們將要好好的研究它,目錄如下。 樹的定義與特性 二元樹 二元樹的實作與方法操作方法實作 樹的定義與特性 在資料結構中,樹這種結構,是用來模擬具有樹狀結構性質的數據集合,它有很明確的層級關係,它長的就像個倒過來的樹,不過你也可以將他想像成祖譜,它真的很像。 在說它的特性前,我們先簡單的知道它的一些素語。我們會搭配著下圖來進行說明。 節點(node) : 下圖的每一個圈圈都存放資料,稱為節點(node)。 根節點(root) : 就是最上面的節點,如下圖的節點 A 。 邊(edge) : 下圖連節每個節點的線,稱為邊(edge)。 分支度(degree) : 一個節點的分支度是它擁有的子節點數量,如下圖看節點 C 它的分支度為 3 。 階度(level) : 樹中節點的層級數量,一代為一個階度,樹根(A)的階度為 1 ,下圖的樹階度為 3 。 高度(Height)、深度(depth) : 樹中某節點的高度代表此節點至最深階度的子節點距離,也就是邊的數量,例如 A 節點的高度為 2 ,而 B 節點的高度為 1 。 接下來我們來說明樹的特性,它具有以下的特點 ; 只要符合下面特點的,我們就可以稱為樹狀結構。 每個節點有零個或多個子節點 沒有父節點的節點稱為根節點 每一個非根節點有且只有一個父節點 除了根節點外,每個子節點可以分為多個不相交的子樹 二元樹 ( Binary tree ) 這邊我們要來說明二元樹,它是樹的一種,我們常聽到的二元啥演算法,有很大一部份都是運用二元樹這種資料結構來處理,它的定義如下。 二元樹是每個節點最多有兩個子樹的樹狀結構 只要符合上述條件的樹,我們都歸類為二元樹。其中二元樹還是有不同的種類。 滿二元樹 ( Full Binary tree ) 如果一棵樹的階度為 k 的樹,它的節點樹量為 2^k - 1 ,則稱為滿二元樹,也就是說全部塞滿的意思,如下圖就是個滿二元樹,它階度為 3 , 所以它的節點樹量應該為 2^3 - 1 = 7 ,下圖的節點數量就為 7 。
前篇文章中,我們說明三種資料結構、陣列、堆疊、佇列,在開始今天的文章前,我們先簡單的複習一下這三個東西是啥。 array : 最常用使用到的資料結構,它是一種相同形態(!)的資料集合,並且會分配『連續』的記憶體空間給予陣列存放資料。 stack : 後進先出法原理的資料結構,後進去的資料會先取出,就像是你有個箱子,你最先放進去的東西,要先將上面的東西取出後,才能取得。 queue : 先進先出法原理的資料結構,先進去的東西先取出,就像是排隊一樣,先排先贏,理論上(和平)。 剛剛在陣列那有說到相同形態,但事實上javascript的陣列,可以存放任何形態的資料,但其它的語言就需要先宣告形態了,某些方面來說它的陣列比較算是list。 複習完了上一篇文章後,咱們可以來學習新的資料結構連結串列(linked list)j。 串列(Linked list)原理 串列與陣列的比較 javascript程式實作 串列 ( Linked List ) 原理 在上一篇中,我們有學習到陣列,它在儲放資料時非常的彈性,但在進行新增或刪除時卻沒著麼方便,主要原因為它的記憶體是連續的。 本篇文章將要說明的連結串列(list),在新增或刪除時就非常的方便,因為它記憶體不是連續的,而是每個結點分配一段記憶體,然後在結點中記錄下個結點的位置。 連結串列有分很多種,我們在這篇文章中將說明比較常用到的『單向連結串列』與『雙向連結串列』。 單向連結串列 單向連結串列,它主要組成的定義如下。 由一組節點(Node)組成的有序串列。 每個節點有『資料欄』與一個『連結欄』組成。 『連結欄』指向其它節點的位置。 根據以上的定義,大至上長的如下圖。 接下來假如我們要新增節點D至A與B之間,過程會和下圖一樣,會將A節點的Link連至D節點,然後它再連到B結點上。而刪除結果過程也差不多,就只是重新指向節點位置。 雙向連結串列 (Double Linked List) 雙向連結串列是另一種常用的串列結構,在單向串列中,它只能順著一個方向尋找資料,而且中間不小心有個節點斷掉,那後面串列的資料就會消失且救不回來,而雙向連結就是可以改善『單向』與『節點斷掉』這兩個缺點。 雙向連結串列,它主要組成的定義如下。 由一組節點(Node)組成的有序串列。 每個節點有『資料欄』與二個『連結欄』組成,一個連結前一個節點,而另一個則連結後一個節點。 『連結欄』指向其它節點的位置。 根據以上的定義,大至上長的如下圖。 然後我們看下圖,來理解如果要插入與刪除節點時,雙向連結串列會如何處理。事際上原理和單向連結串列差不多,都是重新指向位置,只是它要多指向一個。 串列和陣列的比較 由於串列和陣列這兩個使用起來很相似,但原理上,很多地方是不一樣的。以下比較表格來源為此,傳送門。 連結串列 (List) 陣列 (Array) 記憶體 不需要連續的空間 需要連續的空間 節點型態 各node形態不相同 各node形態相同 操作複雜度 插入、刪除都為O(n) (備註) 插入刪除都為O(1)| 空間配置 不需預留空間 須事先宣告連續空間 資料分割、連結 容易 不容易 存取方式 只能循序存取 可支援隨機與循序存又 存取速度 速度慢 速度快 可靠性 差 佳 額外指標空間 需要額外的指標空間 不需要 備註 這裡所為的插入與刪除是指針對某一個 index 的節點進行插入或刪除,在這種情況下,list 需要走到此 index 在進行對應的操作,因此是 O(n)。
接下來的幾篇文章,我們將要簡單的說明幾個基礎的資料結構,那麼資料結構又是什麼呢? 根據 wiki 的解答。 資料結構是電腦中儲存、組織資料的方式。 也就是說你丟了一堆資料進去,你的儲存方式,就是資料結構。 那選擇正確的資料結構可以做啥 ? 答案就是可以提供你的演算法效率。接下來我們將在本篇文章說明三種資料結構陣列(Array)、堆疊(Stack)、佇列(Queue)。 本篇文章目錄如下。 陣列 堆疊 佇列 陣列 ( Array ) 陣列應該算是我們寫程式時,最常使用到的一種資料結構,它就長的下面這樣,上面那行代表我們的資料陣列,下面那行只是表示每個資料對應到的Index,例如array[0]的值為a。 不過有幾點要注意,當初陣列設計之初是在形式上依賴內存分配而成,也就是說必須預先設定陣列的大小。這使得陣列有以下特性。 設定陣列大小後,不能在改變(資料溢位問題)。 在內存中有該陣列專用的連續空間,不會存在其中程式要調用的資料空間。 由於陣列實在太常使用了,這邊就不多說囉。 時間複雜度 indexing : O(1) find : O(n) 堆疊 ( Stack ) 它事實上與陣列很相似,只是它有幾個特殊的方,它只能允許在陣列的一端進行操作,而且按照『後進先出』 LIFO, Last In First Out 的原理運作。如下圖表示。 然後我們簡單的使用javascript來建立stack的資料結構,由於我們是要練習用,所以我們不使用Js的陣列內本來就有提供的stack方法。 首先我們先建立Stack的類別,事實上在js中不該說類別,_size存放該stack的大小,而_container則存放資料。 /** * Stack * this is stack data structure; * @returns {undefined} */ function Stack(){ this._size =0; this._container = {}; } 接下來我們要建立的方法有兩個push與pop,其中push就是將資料丟到stack內,而pop就是取出資料,由於stack遵循『後進先出法』,也就是後丟進去的資料,反而會比較快取得,所以pop,是要取該stack內最後被丟進去的資料。