Binary search tree

This is the 16th day of my participation in Gwen Challenge

Before going to the interview, in the interview, the interviewer asked to write a method, from ten thousand random numbers to find the given number, return the existence or non-existence. If arr[I] is equal to the given number, return true. If arr[I] is equal to the given number, return false. Then he confidently gave the answer

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));
Copy the code

The interviewer took a look at it and said it was right, but could the performance be better? There was no answer. When I went back and thought about it, if I want to improve performance, there are two aspects. One is the data structure, one is the algorithm. Then the algorithm is to compare, compare to the number to return true, compare less than there is no number, the algorithm seems to have no problem. So it’s a data structure problem. Baidu, and then found a binary search tree, so what is a binary search tree? Binary search tree (BST) is also called binary search tree or binary sort tree. It has both the characteristics of quick insertion and deletion of linked list and the advantages of quick search of array, so it is widely used. First, a binary search tree is organized as a binary tree. Secondly, it has sorting effect. If the left subtree of any node is not empty, the value of all nodes in the left subtree is not greater than the value of its root node. If the right subtree of any node is not empty, the value of all nodes in the right subtree is not less than the value of its root node. The left and right subtrees of any node are binary search trees respectively. So how do we build and use binary search trees? How much more efficient is a binary search tree than an array? Without further ado, let’s do a code comparison.

Code to build and use binary search trees

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) {// The target value is larger than the current node
        if (root.right == null) root.right = new Node(num);// If the right side is empty, the node is created
        else addNode(root.right, num);// If the right side is not empty, recurse to the right
    } else {// The target is smaller than the current node
        if (root.left == null) root.left = new Node(num);
        elseaddNode(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);
Copy the code

We build and use binary search tree compared with the previous method, found that binary search tree performance is indeed strong. GET!