前言
最近复习了一下数据结构，学到二叉搜索树的时候有一些感触，记录下来。
编程语言：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
当然，结果跟搜索的数字有关，但是多试几次平均看来，用二叉搜索树的确能少比较很多次数，耗时也少很多。因为遍历数组是要一项项比较，而二叉搜索树，是从根节点一层一层往下找，每一次比较大小后都过滤掉了另一侧的子树。
