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).
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})\) |
You have attempted of activities on this page