二叉搜索树

这是我参与更文挑战的第16天，活动详情查看：更文挑战

之前去面试，面试中，面试官让写一个方法，从一万个随机数中进行查找给定的数字，返回存在还是不存在。当时心想幸好我会，直接定义一个空数组，然后把一万个随机数赋值进数组，然后从头到尾遍历，如果arr[i]等于给定数字，直接返回true，如果最后还是没有，就返回false。然后自信满满的给了答案

var arr = [];

for (var i = 0 ; i < 10000 ; i ++) {
    arr[i] = Math.floor(Math.random() * 10000);
}

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

var num = 0;
function search(arr, target) {
    for (var i = 0 ; i < arr.length ; i ++) {
        num += 1;
        if (arr[i] == target) return true;
    }
    return false;
}
console.log(search(arr, 1000));
复制代码

面试官看了一眼，然后说写是写对了，但是性能能不能再优化一下？当时没回答出来。
回去之后，仔细想了想，如果要提升性能的话，两个方面。一个是数据结构，一个是算法。然后算法就是比较，比较到给定数就返回true，比较不到就没有这个数了，算法好像没毛病。那么就是数据结构的问题了。百度了一下，然后就找到了二叉搜索树，那么什么是二叉搜索树呢？
二叉搜索树（BST）又称二叉查找树或二叉排序树，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势，所以应用十分广泛。首先一棵二叉搜索树是以二叉树来组织的。其次有排序的效果，任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。任意结点的左、右子树也分别为二叉搜索树。
那么我们如何构建和使用二叉搜索树呢？二叉搜索树搜索效率比之前用数组又强多少呢？不多逼逼，直接用代码来对比一下。

代码构建和使用二叉搜索树

var arr = [];

for (var i = 0 ; i < 10000 ; i ++) {
    arr[i] = Math.floor(Math.random() * 10000);
}

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

var num = 0;
function search(arr, target) {
    for (var i = 0 ; i < arr.length ; i ++) {
        num += 1;
        if (arr[i] == target) return true;
    }
    return false;
}

function addNode(root, num) {
    if (root == null) return;
    if (root.value == num) return;
    if (root.value < num) {//目标值比当前节点大
        if (root.right == null) root.right = new Node(num);//如果右侧为空，则创建节点
        else addNode(root.right, num);//如果右侧不为空，则向右侧进行递归
    } else {//目标值比当前节点小
        if (root.left == null) root.left = new Node(num);
        else addNode(root.left, num);
    }
}

function buildSearchTree(arr) {
    if (arr == null || arr.length == 0) return null;
    var root = new Node(arr[0]);
    for (var i = 1 ; i < arr.length ; i ++) {
        addNode(root, arr[i]);
    }
    return root;
}

var num2 = 0;
function searchByTree(root, target) {
    if (root == null) return false;
    num2 += 1;
    if (root.value == target) return true;
    if (root.value > target) return searchByTree(root.left, target);
    else return searchByTree(root.right, target);
}

console.log(search(arr, 1000));
console.log(num);

var root = buildSearchTree(arr);

console.log(searchByTree(root, 1000));
console.log(num2);
复制代码