[資料結構] Binary Search Tree

keywords: data structure, recursive function, 遞迴函式, queue, 佇列

此系列筆記主要依照 [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

• Binary Search Tree 有一個很重要的概念是，它是有「階層」的概念在內的，並不是把所有數字放在同一層排序
• 在建立 BST instance 時會把 root 的 value 一併帶入
• 新增值到 BST 時，會判斷這個值比 root 大或小，再以同樣的邏輯分派到 BST 的左下側或右下側
• 檢驗 BST 中包含是否包含某一值時，也是使用同樣的邏輯，先判斷這個值比 root 大還是小，接著依同樣的邏輯往左下側或右下側尋找
• 找出最小值的方式是從 root 開始一路往左下找；找出最大值的方式則是從 root 開始一路往右下找
• 要疊代整個 BST 元素的方式可以分成 Depth First Traversal 和 Breadth First Traversal。
• 其中 Depth First Traversal 又可以分成:
  • 由小到大依序迭代（in-order）
  • 由上往下，由左至右（pre-order）
  • 由下往上，由左至右（post-order）
• Breadth First Traversal 則是以水平的方式由上往下依序疊代所有內容

Depth First Traversal

在撰寫這個方法的時候，需要特別留意 call stack 中執行的順序：

In-Order

從最底部開始，先把左邊的輸出，在輸出右邊的，如此所有的值就會由小到大依序排列。輸出的內容會是：10, 20, 30, 35, 45, 50, 59, 60, 70, 85, 100, 105。

Pre-Order

• 適合使用在想要 Copy Tree 時使用
• 由上往下，由左至右，依序輸出所有內容。以下圖為例，會輸出 50, 30, 20, 10, 45, 35, 70, 60, 59, 100, 85, 105：

Post-Order

• 適合使用在刪除節點時
• 由下往上，由左至右。以下圖為例，會輸出 10, 20, 35, 45, 30, 59, 60, 85, 105, 100, 70, 50：

Breadth First Traversal

適合用在有階層性的資料，例如公司的組織架構，如此可以快速地找出管理職有誰，員工有誰等等：

實作的方式會使用到 queue 作法：

Big O Notation

二元搜尋樹的優點在於：

• 可以快速的找到項目
• 可以快速的新增和移除項目
• 它是屬於 O (log n) 的演算法

但使用它有一個很重要的前提是資料必須盡量平均分散在左右兩邊，讓它長成一個樹狀結構，如果資料都是集中在某一側的話，則不適合使用 Binary Search Tree。這種資料結構常用在「字典」、「電話簿」、「使用者資料」等等。

Sample Code

data-structures-in-javascript @ PJCHENder Github

Started Template

/* eslint-disable */
function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

// 在 BST 中插入值
BST.prototype.insert = function insert(value) {
  /* ... */
};

// 判斷 BST 中是否包含此值，回傳 true/false
BST.prototype.contains = function contains(value) {
  /* ... */
};

// depthFirstTraversal 可以用來疊代 Binary Search Tree 中的所有元素
const ORDER_TYPE = {
  IN_ORDER: 'IN_ORDER', // 將所有元素打平後由左至右排列
  PRE_ORDER: 'PRE_ORDER', // 由上往下，由左至右
  POST_ORDER: 'POST_ORDER', // 由下往上，由左至右
};

BST.prototype.depthFirstTraversal = function depthFirstTraversal(
  iteratorFunc,
  order = ORDER_TYPE.IN_ORDER
) {
  /* ... */
};

// 疊代 BST 中的所有元素
BST.prototype.breadthFirstTraversal = function breadthFirstTraversal(
  iteratorFunc
) {
  /* ... */
};

// 取得 BST 中的最小值
BST.prototype.getMinVal = function getMinVal() {
  /* ... */
};

// 取得 BST 中的最大值
BST.prototype.getMaxVal = function getMaxVal() {
  /* ... */
};

module.exports = {
  BST,
  ORDER_TYPE,
};

參考

• [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub

Read More

[資料結構] Hash Table

keywords: data structure

此系列筆記主要依照 [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

觀念

• Hash Table 本身是一個陣列，裡面的每一個元素都是帶有 key-value 的物件，稱作 Buckets。
• 透過自訂的 hash 函式，可以決定新增的資料要放在 Hash Table 中的哪個位置。
• 當有不同的內容放到相同編號的 Buckets 時，會發生所謂的 collision，這時候相同 Bucket 內的資料，會透過 Linked List 的方式串接在一起。
• 當 insert 了相同 key 的資料時，會有更新的效果。
• 其中會包含的方法有：
  • hash
  • insert
  • get, retrieveAll

Big O Notation

• Hash Table 常用在儲存使用者的 Email、使用者資料。
• 缺點：除非在同一個 bucket 內，否則資料（Node）之間不會彼此參照。

Constant Time - O(1)

• 插入資料
• 搜尋資料

Sample Code

data-structures-in-javascript @ PJCHENder Github

Started Template

// size 會決定在 hashTable 中有多少 buckets
function HashTable(size) {
  this.buckets = Array(size);
  this.numberBuckets = this.buckets.length;
}

// 每一個 key-value pair 稱作 Node
function HashNode({ key, value, next = null }) {
  this.key = key;
  this.value = value;
  this.next = next;
}

// 用來產生一個數值，此數值不能超過 buckets 的 size
HashTable.prototype.hash = function hash(key) {/* ... */};

// 用來新增 Node 到 HashTable 中
// 若該 bucket 已經有資料，則透過 Linked List 的概念，放到 next 中
// 若該 key 已經存在，則進行更新
HashTable.prototype.insert = function insert({ key, value }) {/* ... */};

// 根據 key 取得 value
HashTable.prototype.get = function get(key) {/* ... */};

// 取得所有 Buckets 中的 Node
HashTable.prototype.retrieveAll = function retrieveAll() {/* ... */};

module.exports = HashTable;

參考

• [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub

Read More

[資料結構] Linked List

此系列筆記主要依照 [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

資料結構（Data Structure）是什麼

• 不同的資料結構有不同的強弱項，有的在儲存（storing）和紀錄（recording）資料的速度較快，有的則是在搜尋（searching）和提取（retrieving）上比較快。
• 資料結構的使用會影響到效能表現（performance）和程式運行的效率

Linked List

• Linked List 中，會紀錄該 Linked 的 head 和 tail
• 每一個 Node 則會紀錄它的 value, prev 和 next
• 其中會包含的方法為:
  • addToHead, addToTail
  • removeHead, removeTail
  • search, indexOf

Big O Notation

Constant Time - O (1)

• 新增／移除 Head
• 新增／移除 Tail

Linear Time - O (n)

• 搜尋元素是否存在
• 搜尋元素的 index 位置

Memory Manage Benefits

使用 Linked List 的資料結構可以更有效率的使用記憶體，因為每一個元素都是獨立，彼此之間是透過 next 和 prev 來關聯在一起：

Sample Code

data-structures-in-javascript @ PJCHENder Github

Started Template

/* eslint-disable */
function LinkedList() {
  this.head = null;
  this.tail = null;
}

function Node({ value, next, prev }) {
  this.value = value;
  this.next = next;
  this.prev = prev;
}

// 輸入 value 後，把該值添加到 Linked List 的最前方
LinkedList.prototype.addToHead = function addToHead(value) {
  /* ... */
};

// 輸入 value 後，把該值添加到 Linked List 的最後方
LinkedList.prototype.addToTail = function addToTail(value) {
  /* ... */
};

// 移除 Linked List 的第一個 Node，若 Head 存在則回傳被移除的值，否則回傳 null
LinkedList.prototype.removeHead = function removeHead() {
  /* ... */
};

// 移除 Linked List 的最後一個 Node，若 Head 存在則回傳被移除的值，否則回傳 null
LinkedList.prototype.removeTail = function removeTail() {
  /* ... */
};

// 輸入 value 後，搜尋此 LinkedList 中是否有此值
// 找不到的話回傳 null，否則回傳找的的值
LinkedList.prototype.search = function search(searchValue) {
  /* ... */
};

// 列出所有等同於 searchValue 的 indexes
LinkedList.prototype.indexOf = function indexOf(searchValue) {
  /* ... */
};

module.exports = {
  LinkedList,
  Node,
};

參考

• [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub
• 鏈結串列 Linked List @ iT邦鐵人賽 by hannahpun

Read More

[筆記] 從 JavaScript 學起演算法與資料結構（Learning Algorithm and Data Structure in JavaScript）

記得以前剛轉行從事網頁工程的時候，需要從 database 撈資料到前端呈現，可是當時真的是不清楚要怎麼處理資料，主管便問我說：「你要用什麼演算法」。演・算・法，當時聽到這三個字我真的是滿臉黑人問號？演算法到底是什麼碗糕？

後來想想在學習的路上，總是接觸到很多陌生但卻又耳熟的詞彙，做為新手，常常聽到很多詞就先畏懼了，覺得自己好像很多東西都還不懂的感覺，但其實很多字詞並沒有想得這麼複雜或這麼難。

演算法簡單來說，就是「解決問題的方法」—當碰到一個問題時，要用什麼樣的方式來解決所碰到的這個問題。

這個在 TEDEd 短短 5 分鐘的影片（中文字幕），清楚說明了演算法（Algorithm）的概念：

接下來這一系列的筆記，則是最近剛好有機會在 Udemy 上觀看了由 Eric Traub 的 Learning Algorithm in JavaScript from Scratch 和 Learning Data Structures in JavaScript from Scratch 這兩堂課，讓我真正從 JavaScript 開始學起了演算法和資料結構，筆記當中主要是按照該課程的脈絡加以整理，但是很多程式碼的寫法是消化過後以自己能夠理解的方式撰寫，因此可能和原課程內容有些出入。希望對於沒有接觸過演算法／資料結構的朋友們，也可以一起從 JavaScript 學起演算法／資料結構：

演算法篇（Algorithm）

• Fizz Buzz
• 如何評斷演算法的好壞：Big O Notation 和 Time Complexity
• Harmless Ransom Note：計算陣列中各元素出現的次數
• Is Palindrome：判斷順著寫逆著寫是否相同？
• Caesar Cipher: 往後或往前推移英文字母
• Reverse Words: 把單字反過來寫
• Reverse Array in Place: 暫存變數的使用
• Mean Median Mode
• Two Sum
• 什麼是遞回函式（recursive function, recursion）？
• Binary Search：在陣列中尋找特定元素
• Fibonacci：善用 cache 和 Memoization 提升程式效能
• Sieve of Eratosthenes 質數判斷
• Bubble Sort：學習將陣列對半切分
• 合併排序法（Merge Sort）
• Max Stock Profit

資料結構篇（Data Structure）

• Linked List
• Binary Search Tree
• Hash Table

其他學習資源

這裡一併列出其他和演算法／資料結構有關的學習資源：

• JavaScript Algorithms and Data Structures @ Github
• Data Structure and Algorithms Tutorial @ Tutorial Points
• 演算法筆記
• VisuAlgo

Read More