¿Por qué los árboles de búsqueda binaria?

Question

Estaba leyendo el árbol de búsqueda binaria y estaba pensando que ¿por qué necesitamos BST en absoluto? Todas las cosas, hasta donde yo sé, también se pueden lograr usando arreglos ordenados simples. Por ej. - Para construir un BST que tenga n elementos, se requiere n*O(log n), es decir, O(nlog n) y el tiempo de búsqueda es O(log n). Pero esto también se puede lograr usando una matriz. Podemos tener una matriz ordenada (requiere O(nlog n) vez), y el tiempo de búsqueda también es O(log n), es decir, algo de búsqueda binaria. Entonces, ¿por qué necesitamos otra estructura de datos? ¿Hay algún otro uso/aplicación de BST que los haga tan especiales?

--Ravi

Answer 1

Las matrices son geniales si se trata de escribir una sola vez, leer muchas veces el tipo de interacciones. Es cuando se llega a insertar, intercambiar y eliminar, en el que BST realmente comienza a brillar en comparación con una matriz. Dado que se basan en nodos, en lugar de basarse en un fragmento contiguo de memoria, el costo de mover un elemento a la colección o fuera de la colección es rápido, manteniendo la naturaleza ordenada de la colección.

Piense en ello como lo haría con la diferencia entre las listas vinculadas y las matrices. Esta es una simplificación excesiva, pero resalta un aspecto de la ventaja que he señalado anteriormente.

Answer 2

¿Qué hay de tiempo de inserción ordenada?

Answer 3

En la programación de gráficos si tiene objetos extendidos (es decir, que representan un intervalo en cada dimensión y no solo un punto) puede agregarlos al nivel más pequeño de un árbol binario (normalmente un octárbol) donde encajen por completo.

Y si no calcula previamente el árbol/la lista ordenada, el tiempo de inserción aleatorio O (n) en una lista puede ser prohibitivo. Por otro lado, el tiempo de inserción en un árbol es solo O (log (n)).

Answer 4

Imagine que tiene una matriz con un millón de elementos.

desea insertar un elemento en la posición 5.

Así se inserta al final de la matriz y luego especie.

Digamos que la matriz está llena; eso es O (nlog n), que es 1,000,000 * 6 = 6,000,000 operaciones.

Imagine que tiene un árbol equilibrado.

Eso es O (log n), más un bit para equilibrar = 6 + un poco, llámelo 10 operaciones.

Así que, acaba de gastar 6,000,000 ops en ordenar su matriz. Luego desea encontrar ese elemento. ¿Qué haces? búsqueda binaria - O (log n) - que es exactamente ¡lo mismo que lo que vas a hacer cuando buscas en el árbol!

Ahora imagine que desea asignar otro elemento.

¡Su matriz está llena! ¿qué haces? reasignar la matriz con n elementos adicionales y memcpy el lote? ¿De verdad quieres memcpy 4mbytes?

En un árbol, solo agrega otro elemento ...