2020年5月26日

[資料結構] Binary Search Tree

      ,  
keywords: data structure, recursive function, 遞迴函式, queue, 佇列
此系列筆記主要依照 [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。
Imgur
  • 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 中執行的順序：
Imgur

In-Order

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

Pre-Order

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

Post-Order

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

Breadth First Traversal

適合用在有階層性的資料，例如公司的組織架構，如此可以快速地找出管理職有誰，員工有誰等等：
Imgur
實作的方式會使用到 queue 作法：
Imgur

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,
};

參考

0 意見:

張貼留言