6.19. Resumen de implementaciones del TAD Vector Asociativo

En los últimos dos capítulos hemos examinado varias estructuras de datos que se pueden utilizar para implementar el tipo abstracto de datos Vector Asociativo. Una búsqueda binaria en una lista, una tabla hash, un árbol binario de búsqueda y un árbol binario de búsqueda equilibrado. Para concluir esta sección, vamos a resumir el desempeño de cada estructura de datos para las operaciones clave definidas por el TAD Vector Asociativo (ver la Tabla 1).

Tabla 1: Comparación del desempeño de diferentes implementaciones del TAD Vector Asociativo
Operación Lista ordenada Tabla hash Árbol binario de búsqueda Árbol AVL
agregar \(O(n)\) \(O(1)\) \(O(n)\) \(O(\log_2{n})\)
obtener \(O(\log_2{n})\) \(O(1)\) \(O(n)\) \(O(\log_2{n})\)
in \(O(\log_2{n})\) \(O(1)\) \(O(n)\) \(O(\log_2{n})\)
eliminar \(O(n)\) \(O(1)\) \(O(n)\) \(O(\log_2{n})\)
Next Section - 6.20. Resumen