Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
| insertar | eliminarMínimo | consultarMínimo | eliminarMáximo | consultarMáximo | |
|---|---|---|---|---|---|
| (v) árbol binario de búsqueda | O(n) | O(n) | O(1) | O(n) | O(1) |
| (vi) árbol AVL | O(log n) | O(log n) | O(1) | O(log n) | O(1) |
| (vii) montículo binario | O(log n) | O(log n) | O(1) | O(n) | O(1) |
En esta tabla suponemos que utilizamos un montículo binario con el mínimo en la raíz (un min-heap). De ese modo, sabemos que podemos obtener los costes indicados para las tres primeras operaciones. Eso es compatible con mantener un atributo con el máximo, para consultarlo en tiempo O(1). Pero eliminar el máximo requeriría buscar el nuevo máximo y eso costaría O(n).
Alternativamente, si utilizásemos un montículo binario con el máximo en la raíz (un max-heap) se intercambiarían los costes de las dos operaciones de eliminación.
Por tanto, los árboles AVL son una elección mejor que los montículos binarios para soportar las cinco operaciones.