# 搜索二叉樹
搜索二叉樹（BST）。
規則：
1. 任意一個節點的左子節點都小于這個節點
2. 任意一個節點的右子節點都大于這個節點
## 應用場景
這種樹的搜索速度：O(logn)，速度非常快。
比如：從10億條記錄中查找任意一條記錄，最多需要比較30多次。
# 代碼實現
~~~
// 定義節點類
class Node {
constructor(data) {
this.data = data // 數據
this.left = null // 左子節點
this.right = null // 右子節點
}
}
// BST樹
class BinarySearchTree {
constructor() {
this.root = null // 根節點
this.length = 0 // 樹中節點的數量
}
// 向樹中插入一條記錄
insert(data) {
// 1. 創建新的節點
let newNode = new Node(data)
// 2.放到樹中
// 如果是空樹
if(this.root === null) {
// 設置這個新節點為樹根
this.root = newNode
} else {
// 從根節點開始比較
this._insert(this.root, newNode)
}
}
_insert(node, newNode) {
// 小于向左走
if(newNode.data < node.data) {
// 判斷是否有左子節點
if(node.left === null) {
// 設置這個新節點為左子節點
node.left = newNode
} else {
// 遞歸，繼承用新節點和左子節點比較
this._insert(node.left, newNode)
}
} else {
// 判斷是否有右子節點
if(node.right === null) {
// 設置這個新節點為右子節點
node.right = newNode
} else {
// 遞歸，繼承用新節點和右子節點比較
this._insert(node.right, newNode)
}
}
}
// 判斷樹中是否包含某一個數
has(data) {
// 從根節點開始查找
return this._has(this.root, data)
}
_has(node, data) {
// 如果節點為空，說明樹中沒有這個數
if(node == null) {
return false
}
// 如果值和前節點值相同，找到了
if(data == node.data) {
return true
} else if(data < node.data) {
// 到左子樹中查找
return this._has(node.left, data)
} else if(data > node.data) {
// 到右子樹中查找
return this._has(node.right, data)
}
}
}
~~~
