二叉搜索树

作者: 太妃榛果拿铁 | 来源:发表于2020-03-09 13:38 被阅读0次

前言

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

编程语言: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

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

相关文章

  • 数据结构与算法之二叉搜索树(八)

    目录 二叉搜索树概念二叉搜索树的接口设计,包括增,删,改,查平衡二叉搜索树 一 二叉搜索树 二叉搜索树是二叉树的一...

  • Algorithm小白入门 -- 二叉搜索树

    二叉搜索树二叉搜索树 BSTBST 的基本操作计算合法的 BST 1. 二叉搜索树 BST 二叉搜索树(Binar...

  • 二叉搜索树

    二叉搜索树 图解二叉树搜索算法图解:二叉搜索树算法二叉查找树(Binary Search Tree),(又:二叉搜...

  • 23-红黑树

    1.二叉搜索树(BST)继承二叉树(BinaryTree) 2.平衡二叉搜索树(BBST)继承二叉搜索树(BST)...

  • 二叉搜索树(Binary Search Tree)

    1. 定义 二叉搜索树(BST)又叫二叉查找树,二叉排序树。二叉搜索树就是一棵二叉树,但是它又具有搜索树的特征: ...

  • 二叉树基础

    二叉树的分类 完全二叉树与满二叉树 二叉搜索树BST 平衡二叉搜索树BBST因为二叉搜索树有可能退化为链表,降低查...

  • 数据结构 经典算法复习

    二叉搜索树, 平衡二叉树(AVL) 红黑树 B树(平衡多路搜索树) B+树(在B树上改造) 二叉搜索树...

  • Swift 验证二叉搜索树- LeetCode

    题目: 验证二叉搜索树 验证二叉搜索树给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有...

  • 树,二叉树,搜索树

    树,二叉树,搜索树 资料 二叉搜索树 Demo 树的遍历 Demo 题目 ◎ 二叉树的中序遍历 ◎ 二叉树...

  • 【数据结构】红黑树

    1、什么是红黑树? 红黑树是一个要求不那么严格的平衡二叉树搜索树(平衡二叉搜索树/AVL树=平衡二叉树+二叉搜索树...

网友评论

    本文标题:二叉搜索树

    本文链接:https://www.haomeiwen.com/subject/ojfpdhtx.html