He estado creando algunas estructuras de datos para mantener mis habilidades en forma. Creé un BST y he estado probando su velocidad contra una matriz. Noté que la velocidad de inserción del BST es mucho más lenta que la de array.push. He estado usando Math.random y he agregado millones de números a ambas estructuras de datos. Curiosamente, el BST es mucho más rápido para encontrar un valor que array.includes/indexOf. ¿Hay una mejor manera de codificar mi función de inserción o está insertando solo una parte lenta con BST?
Aquí está mi código
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 } } }Tu código está perfectamente bien.
TL;DR: Su punto de referencia de comparación/rendimiento es inexacto
Mi respuesta asume que está familiarizado con la notación Big O para la medición del tiempo de los algoritmos, si no lo está, dígalo en un comentario y editaré mi respuesta.
La cuestión es que array.push es una operación simple, ya que siempre agrega el elemento al final de la matriz, lo que lleva un O(1) (constante), mientras que insertar un elemento en un BST significa que está buscando el lugar correcto para insertarlo, porque tiene que estar en orden, no lo tiras al final del árbol como lo haces con array,push . Esta operación lleva más tiempo ( O(logn) donde n es el número de nodos en el árbol, para ser precisos), por lo que si compara estos dos, por supuesto que array.push será más rápido.
Si intentó insertar un elemento en orden en la matriz, habría sido mucho más lento que insertarlo en un BST, porque tendría que buscar todos y cada uno de los elementos de la matriz hasta llegar al lugar correcto, luego mover todo para encajar su nuevo elemento en la matriz, lo que toma O(n) tiempo, donde n es el número de elementos en la matriz.
Entonces, en conclusión, BST se destaca en encontrar e insertar elementos en orden , y cuando el orden no importa y puede colocar el elemento donde sea, la matriz generalmente lo hará más rápido, por eso buscar en su BST es más rápido que includes o indexOf para una matriz