Saltar al contenido ForoHackers

Estructuras de datos: por dónde empezar

Estructuras de datos
#892 · Ophuscado · · Denunciar

Una estructura de datos es una forma de organizar los datos en memoria para que las operaciones que necesitas sean baratas. Arreglos, listas, tablas hash y árboles guardan los mismos elementos; se distinguen en lo rápido que los encuentran, insertan, borran u ordenan. Elegir bien suele importar más que cualquier microoptimización.

Conceptos clave

  • Tipo abstracto de datos e implementación: una pila o un mapa es una interfaz; los arreglos o los nodos enlazados son maneras de construirla.
  • Memoria contigua o enlazada: los arreglos aprovechan la caché y se indexan en tiempo constante; los nodos enlazados insertan barato pero obligan a seguir punteros.
  • Hashing: una función hash lleva una clave a una posición; las colisiones se resuelven con encadenamiento o sondeo.
  • Árboles balanceados: mantener un árbol de búsqueda poco profundo da búsqueda, inserción y borrado logarítmicos.
  • Montículos y colas de prioridad: acceso rápido al elemento menor o mayor.

Vocabulario

  • Coste amortizado: el coste medio por operación en una secuencia larga, como cuando un arreglo dinámico se duplica.
  • Factor de carga: la razón entre los elementos guardados y las posiciones de una tabla hash.
  • Invariante: una propiedad que la estructura mantiene tras cada operación, como el orden del montículo.
  • Estructura persistente: la que conserva disponibles las versiones antiguas tras una actualización.

Qué estudiar, en orden

  1. Construye un arreglo dinámico y una lista enlazada simple; mide el tiempo de insertar al principio y al final.
  2. Implementa una tabla hash con encadenamiento, luego redimensiónala y observa el factor de carga.
  3. Implementa un árbol binario de búsqueda y después una variante balanceada, como un AVL o un rojo-negro.
  4. Construye un montículo binario y úsalo para una cola de prioridad y para heapsort.
  5. Mira los conjuntos disjuntos, los tries y los árboles B, y pregúntate qué hace rápido cada uno.

Etiquetas relacionadas

#algorithms #memory-management #databases #complexity

Inicia sesión o únete para responder.