前言

最近复习了一下数据结构，学到二叉搜索树的时候有一些感触，记录下来。

编程语言：JavaScript
内容：二叉搜索树的构建和搜索

情景

在有一万个数的数组中，查找是否有一个值

// 一个随机数数组
const arr = [];
for (let i = 0 ; i < 10000 ; i++) {
    arr[i] = Math.floor(Math.random() * 10000);
}

数组遍历查找

let count = 0; //查找次数
// 数组遍历搜索
function search(arr,target) {
    for (let i = 0; i < arr.length; i++) {
        count++;
        if (arr[i] == target) {
            return true;
        }
    }
    return false;
}
//打印效率
console.time('searchArr')
console.log(search(arr,1000), count)
console.timeEnd('searchArr')

一般的思路都是这样，直接遍历数组，但是要找很多次。要优化性能的话，要么优化数据结构、要么优化算法。算法就是比较大小，没什么问题，所以可以优化数据结构，将 数组 换成 二叉排序树

二叉搜索树中查找

构建二叉搜索树

// 二叉搜索树 节点
class Node{
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 构建二叉搜索树
function buildSortTree(arr) {
    if(arr == null || arr.length == 0) return null;
    const root = new Node(arr[0]);
    for (let i = 1; i < arr.length; i++) {
        addNode(root, arr[i]);
    }
    return root;
}
// 比较大小并添加节点
function addNode(root,value) {
    if (root == null) return;
    // 等于节点的value
    if (value == root.value) return;
    // 小于节点的value
    if (value < root.value){
        if (root.left == null) //节点为空直接添加节点
            root.left = new Node(value);
        else    // 否则递归创建添加节点
            addNode(root.left, value)
    }
    // 大于节点的value
    else{
        if (root.right == null) 
            root.right = new Node(value);
        else
            addNode(root.right, value)
    }
}
const root = buildSortTree(arr);

搜索

// 遍历二叉搜索树
let count2 = 0; // 遍历次数
function searchTree(root, value) {
    count2++;
    if(root == null) return false;
    if(root.value == value) return true;
    if (value < root.value)
        return searchTree(root.left, value);
    else
        return searchTree(root.right, value);
}
// 打印效率
console.time('searchTree')
console.log(searchTree(root,1000), count2)
console.timeEnd('searchTree')

结果

result.png

当然，结果跟搜索的数字有关，但是多试几次平均看来，用二叉搜索树的确能少比较很多次数，耗时也少很多。因为遍历数组是要一项项比较，而二叉搜索树，是从根节点一层一层往下找，每一次比较大小后都过滤掉了另一侧的子树。