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})\)