Skip to main content

[資料結構] Binary Search Tree(BST)

TL;DR#

  • 每個 Node 會包含 value, leftright
  • Binary Search Tree 會實作 lookup, insert, 和 remove 的方法

Brinary Search Tree 的特性#

Imgur

  • Perfect Binary Tree 有幾個重要的特性:
    • 每下一層的 Node 數量都是上一層 Node 數的兩倍
    • 最下層 Node 的數量會等於其上層所有 Node 數量加總後 + 1。例如,三層的 Perfect Tree,則三層 Node 的數量,會等同於前兩層的數量加總後再加 1,也就是 4 = 3 + 1
    • Node 的總數量會同於 2 的(Node 層數)次方 -1,也就是 2^h - 1
  • Binary Search Tree 有一個很重要的概念是,它是有「階層(關係)」的概念在內的,並不是把所有數字放在同一層排序。
  • 在建立 BST instance 時會把 root 的 value 一併帶入
  • 新增值到 BST 時,會判斷這個值比 root 大或小,再以同樣的邏輯分派到 BST 的左下側或右下側
  • 檢驗 BST 中包含是否包含某一值時,也是使用同樣的邏輯,先判斷這個值比 root 大還是小,接著依同樣的邏輯往左下側或右下側尋找
  • 找出最小值的方式是從 root 開始一路往左下找;找出最大值的方式則是從 root 開始一路往右下找
  • 要疊代整個 BST 元素的方式可以分成 Depth First TraversalBreadth First Traversal
  • 其中 Depth First Traversal 又可以分成:
    • 由小到大依序迭代(in-order)
    • 由上往下,由左至右(pre-order)
    • 由下往上,由左至右(post-order)
  • Breadth First Traversal 則是以水平的方式由上往下依序疊代所有內容

Big O Notation#

二元搜尋樹的優點在於:

  • Lookup: O(log N)
  • Insert: O(log N)
  • Delete: O(log N)

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

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

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

其他 Tree#

一般來說,當我們需要使用 Tree 這類的資料結構時,會有現成的 Library 可以使用,而不需要自己去建立它。

除了 Binary Search Tree 之外,還有很多不同的 Tree。為了解決 Binary Search Tree 不平衡的問題,最常見的還包括 AVL Tree 和 Red/Black Tree。

參考#

Last updated on