Skip to the content ForoHackers
Log inJoin

Estructuras de datos: por dónde empezar

Data structures
#3398 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply