# 搜索二叉树
搜索二叉树（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)
}
}
}
~~~
