慢速二进制搜索树插入

Question

我一直在创建一些数据结构来保持我的技能。我创建了一个BST，并一直在对阵列进行压力测试。我注意到BST的插入速度远慢于array.push。我一直在使用Math.random，并在这两个数据结构中添加了数百万个数字。奇怪的是，BST在查找值方面比array.includes/indexOf快得多。有没有更好的方法来编码我的插入函数，或者用BST 只插入一个缓慢的部分

这是我的代码

insert(data) {
if(this.root === null) {
this.root = new Node(data)
return this
} 
let current = this.root
while(current) {
if(current.data === data) {
console.log(data + ' Already exists in tree')
return
}
if(data < current.data) {
if(current.left === null) {
current.left = new Node(data)
this.size++
return this
} 
current = current.left
}
if(data > current.data) {
if(current.right === null) {
current.right = new Node(data)
this.size++
return this
}
current = current.right
}
}
}

Answer 1

您的代码非常好。

TL；DR：您的比较/性能基准不准确

我的答案假设你熟悉算法时间测量的大O符号，如果你不熟悉，请在评论中这样说，我会编辑我的答案。

问题是，array.push是一个简单的操作，因为它总是将元素附加在数组的末尾，这需要O(1)(恒定(时间，而将元素插入BST意味着你正在寻找正确的位置来插入它，因为它必须有序，你不能像处理array,push那样把它扔在树的末尾。这个操作需要更多的时间(确切地说，O(logn)，其中n是树中的节点数(，所以如果比较这两个，array.push当然会更快。

如果您尝试将元素按的顺序插入到数组中，则会比将其插入BST慢得多，因为您必须搜索数组中的每个元素，直到找到正确的位置，然后移动所有元素以适应数组中的新元素，这需要O(n)时间，其中n是数组中的元素数。

总之，BST擅长按顺序查找和插入元素，当顺序无关紧要，你可以把元素放在任何地方时，数组通常会做得更快，这就是为什么在BST中搜索数组比includes或indexOf更快的原因