Quiero saber qué es lo mejor: Array O árbol de búsqueda binario en (insertar, eliminar, buscar máximo y mínimo) y ¿cómo puedo mejorar ambos?¿Cuál es la diferencia entre la matriz y el árbol de búsqueda binaria en cuanto a la eficiencia?
Un array permite random access a cada elemento del mismo. para que pueda insertar, eliminar y buscar un elemento específico en O(1), y max/min, eliminar en O(n). [También puede hacer máximo/mínimo O(1) y eliminar O(n) en su lugar]. Si mantiene ordenada su matriz, provocará que insert/delete sea O(n), pero obtendrá O(logn) find y O(1) min/max.
Un BST está ordenada por definición, y por un BST [desequilibrada] regular, se obtiene un comportamiento peor O(n) caso. Para BST balanceada, obtiene O(logn) insertar/eliminar/buscar. Puede obtener O(1) mín/máx de cualquier forma para ambos.
Las matrices también suelen ser más rápidas que iterate [suponiendo que el orden de iteración no es importante] ya que obtiene un mejor rendimiento de cache. Además, a diferencia de BST, que tiene un tamaño ilimitado por naturaleza, una matriz requiere reasignación y copia de los datos cuando la matriz está llena.
Mejorar un BST se puede hacer por lo que es balanced - como AVL o red-black-trees.
¿Cuál es mejor? Depende de la aplicación. Por lo general, cuando planifica insertar datos y mantenerlos ordenados, se preferirá BST. Si el propósito principal es el acceso aleatorio o la iteración: generalmente usa una matriz.
¿Por qué las operaciones constantes 'findMin/findMax'' O (1) 'para una BST equilibrada? – Cratylus
@ user384706: Cada vez que inserta/quita un elemento de una BST balanceada, es 'O (logn)' y 'O (n)' para BST no balanceada. Puede mantener los punteros adicionales 'min' y' max', que solo se modificarán cuando inserte/remueva elementos de BST. Encontrar el nuevo máximo/mínimo es 'O (logn)' para BST balanceado y 'O (n)' para no equilibrado - por lo tanto, no hay pérdida de rendimiento [grandes O términos] en esta operación, y en términos de gran O, usted puede mantener estos indicadores para "libre" – amit
Ah, entonces quiere decir usar punteros adicionales.Pero en este caso, esta es una optimización no relacionada directamente con los algoritmos BST.Así que no es algo inconsistente/engañoso reclamar en una comparación con otra estructura de datos (en este caso una matriz) que el 'max/min' es' O (1) 'ya que no es por defecto? Se debe implementar de tal manera que es – Cratylus
Comparación de rendimiento de matrices y árboles binarios de búsqueda:
Array Binary search tree
Unsorted Sorted Average Worst case
Space O(n) O(n) O(n) O(n)
Search O(n) O(log n) * O(log n) O(n)
Max/Min O(n) O(1) O(1) ** O(1) **
Insert O(1) O(n) O(log n) O(n)
Delete O(1) O(n) O(log n) O(n)
* asumiendo búsqueda binaria
** requiere punteros adicionales para mínimo y máximo, de lo contrario es O (log n)
¿Por qué 'O (1)' encuentra el máximo/mínimo de una BST? – Cratylus
Ahora que lo preguntas, no estoy seguro de si es correcto. Los árboles de búsqueda binaria están ordenados por definición, pero (dependiendo de la implementación?) Puede que no sea posible obtener el mínimo/máximo en O (1). En ese caso, sería O (log n) en su lugar. – Peladao
No es 'O (1)' a menos que su implementación mantenga un puntero a los valores 'min' y' max'. Compruebe también los comentarios en la respuesta de amit – Cratylus
¿Intentaste buscando esta información? Debería ser fácil de encontrar. – Howard
¿Te refieres a las estructuras de datos abstractas [lista vinculada] (http://en.wikipedia.org/wiki/Linked_list) y [árbol de búsqueda binario] (http://en.wikipedia.org/wiki/Binary_search_tree)? – Gumbo
mejorar de qué manera? lo mejor para que? esas son estructuras de datos completamente diferentes, y cada una de ellas podría ser la "mejor" para una determinada aplicación. – amit