Landy Blog
0%

資料結構-Binary Search Tree - Wrap Up

發表於 更新於 分類於 ，
做 Binary Search Tree 的總結

Binary Search Tree 具有哪幾種方法?

insert,
contains,
depthFirstTraversal (with pre-order, in-order, post-order),
breathFirstTraversal,
getMaxVal,
getMinVal

Binary Search Tree 完整的 Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

BST.prototype.insert = function (value) {
  if (value <= this.value) {
    if (!this.left) this.left = new BST(value);
    else this.left.insert(value);
  } else {
    if (!this.right) this.right = new BST(value);
    else this.right.insert(value);
  }
};

BST.prototype.contains = function (searchVal) {
  if (this.value === searchVal) return true;
  if (searchVal < this.value) {
    if (!this.left) return false;
    else this.left.contains(searchVal);
  } else {
    if (!this.right) return false;
    else this.right.contains(searchVal);
  }
};

BST.prototype.depthFirstTraversal = function (iteratorFnc, order) {
  if (order === 'pre-order') iteratorFnc(this);
  if (this.left) this.left.depthFirstTraversal(iteratorFnc, order);
  if (order === 'in-order') iteratorFnc(this);
  if (this.right) this.right.depthFirstTraversal(iteratorFnc, order);
  if (order === 'post-order') iteratorFnc(this);
};

BST.prototype.breathFirstTraversal = function (iteratorFnc) {
  const queue = [this];
  while (queue.length) {
    const currentNode = queue.shift();
    iteratorFnc(currentNode);
    if (currentNode.left) queue.push(currentNode.left);
    if (currentNode.right) queue.push(currentNode.right);
  }
};

BST.prototype.getMinVal = function () {
  if (!this.left) return this.value;
  else return this.left.getMinVal();
};

BST.prototype.getMaxVal = function () {
  if (!this.right) return this.value;
  else return this.right.getMaxVal();
};

const bst = new BST(50);
bst.insert(30);
bst.insert(100);
bst.insert(-1);
bst.insert(40);
bst.insert(70);
bst.insert(60);

bst.depthFirstTraversal(getVal, 'in-order'); // -1 30 40 50 60 70 100
console.log('--------------------');
bst.breathFirstTraversal(getVal); // 50 30 100 -1 40 70 60

console.log(`Min, ${bst.getMinVal()}`); // Min, -1
console.log(`Max, ${bst.getMaxVal()}`); // Max, 100

function getVal(node) {
  console.log(node.value);
}

time complexity - O(log2n)

以上這些方法像是 insert, contains, getMaxVal, getMinVal 這幾種，都有做判斷是否有左, 右 node 的判斷，
然後，依據判斷的結果來決定要往 left-side 或 right-side 繼續遍尋。
這樣子二分法的處理方式，可以讓處理時間為 O(log2n) ，比起 Linked List 的 O(n) 所需耗費的時間還要少。

Conclusion

  • 但在享有 O(log2n) 的前提是，你要先把資料以 Binary Search Tree 的方式來建構你的資料，接著，才能使用跟 Binary Search Tree 相關的方法。
  • 另外， Binary Search Tree 如果所有 node 都只有 right-side child node 或者只有 left-side child node 的話，這樣子的話這是一顆不平衡的 tree，而這一棵 tree 的使用效率會很低，基本上就跟 Linked List 一樣。