Este artículo le presenta 30 estructuras de datos y algoritmos importantes.
¿Para qué se utilizan?
Imagínate una hilera de sillas de teatro. A cada silla se le asigna una posición (de izquierda a derecha), por lo que a cada espectador se le asigna un número de la silla en la que se sentará. Esta es una matriz. Extienda el problema a todo el teatro (filas de sillas) y tendrá una matriz bidimensional (matriz).
Características
Una lista enlazada es una estructura de datos lineal, como una matriz. La principal diferencia entre una lista vinculada y una matriz es que los elementos de una lista vinculada no se almacenan en ubicaciones de memoria contiguas. Consta de nodos: entidades que almacenan el valor del elemento actual y la referencia de dirección del siguiente elemento. De esta forma, los elementos se vinculan mediante punteros.
¿Para qué se utilizan?
Una aplicación relacionada de las listas enlazadas es implementar la página anterior y la página siguiente del navegador. Una lista doblemente enlazada es una estructura de datos perfecta para almacenar páginas mostradas por el usuario.
Características
La pila es un tipo de datos abstracto que formaliza el concepto de conjuntos de acceso restringido. Este límite sigue la regla de último en entrar, primero en salir (LIFO). Entonces, el último elemento agregado a la pila es el primer elemento que elimina de la pila.
Las pilas se pueden implementar mediante matrices o listas enlazadas.
¿Para qué se utilizan?
El ejemplo más común en la vida real es apilar platos unos encima de otros en la cafetería. Comience quitando el panel superior. La placa colocada en la parte inferior es la que permanece más tiempo en la pila.
Una de las situaciones más útiles para las pilas es cuando necesitas obtener el orden inverso de un elemento determinado. Empújelos todos hacia la pila y sáquelos.
Otra aplicación interesante es el problema de los paréntesis válidos. Dada una secuencia de paréntesis, puedes usar la pila para comprobar si coinciden.
Características
La cola es otro tipo de datos en un conjunto de acceso restringido, como la pila comentada anteriormente. La principal diferencia es que la cola está organizada según el modelo FIFO (primero en entrar, primero en salir): el primer elemento insertado en la cola es el primer elemento eliminado. Las colas se pueden implementar utilizando matrices de longitud fija, matrices circulares o listas vinculadas.
¿Para qué se utilizan?
El mejor uso de este tipo de datos abstractos (ADT) es, por supuesto, simular una cola de la vida real. Por ejemplo, en una aplicación de centro de llamadas, las colas se utilizan para mantener a los clientes esperando ayuda de un asesor; se supone que estos clientes deben recibir ayuda en el orden en que llaman.
Un tipo de cola especial y muy importante es la cola prioritaria. Los elementos se ponen en cola según su "prioridad" asociada: los elementos con mayor prioridad se ponen en cola primero. Este ADT es esencial en muchos algoritmos de gráficos (algoritmo de Dijkstra, BFS, algoritmo de Prim, codificación de Huffman). Se implementa mediante montón.
Otro tipo especial de cola es la cola deque (el juego de palabras se pronuncia "deck"). Los elementos se pueden insertar/eliminar desde ambos extremos de la cola.
Características
Map (diccionario) es un tipo de datos abstracto que contiene un conjunto de claves y un conjunto de valores. Cada clave tiene un valor asociado.
Una tabla hash es un tipo especial de mapeo. Utiliza una función hash para generar un código hash y lo coloca en una serie de depósitos o ranuras: la clave se procesa mediante hash y el hash resultante indica dónde se almacena el valor.
La función hash más común (entre muchas funciones hash) es una función de módulo constante. Por ejemplo, si la constante es 6, el valor de la clave x es x6.
Lo ideal es que las funciones hash asignen cada clave a un depósito único, pero sus diseños utilizan en su mayoría funciones imperfectas, lo que puede generar inconsistencias entre claves con el mismo valor generado. Esta colisión siempre se adapta de alguna manera.
¿Para qué se utilizan?
La aplicación de mapas más famosa son los diccionarios de idiomas. Cada palabra en este idioma tiene su propia definición. Se implementa mediante un mapa ordenado (sus claves están en orden alfabético).
La libreta de direcciones también es un mapa. Cada nombre tiene un número de teléfono.
Otra aplicación útil es la estandarización de valores. Supongamos que queremos asignar un índice de 0 a 1439 para cada minuto del día (24 horas = 1440 minutos). La función hash será h(x) = x horas*60 x minutos.
Características
Terminología:
Debido a que los mapas se implementan utilizando árboles rojo-negro autoequilibrados (que se explican más adelante en el artículo), todas las operaciones están en O( log n); todas las operaciones de la tabla hash son constantes.
Un gráfico es una estructura de datos no lineal que representa un par de dos conjuntos: G = {V, E}, donde V es un conjunto de vértices (nodos) y E es un conjunto de aristas (flechas) . Los nodos son valores interconectados por líneas de borde que describen dependencias (a veces relacionadas con el costo/distancia) entre dos nodos.
Existen dos tipos principales de gráficos: gráficos dirigidos y gráficos no dirigidos. En un gráfico no dirigido, la arista (x, y) está disponible en ambas direcciones: (x, y) y (y, x). En un gráfico dirigido, la arista (x, y) se llama flecha, y la dirección viene dada por el orden de los vértices en su nombre: no es lo mismo flecha (x, y) que flecha (y, x).
¿Para qué se utilizan?
Características
La teoría de grafos es un campo amplio, pero nos centraremos en algunos de los conceptos más conocidos:
Un árbol es un grafo no dirigido cuyo La conectividad es mínima (si eliminamos una arista, el gráfico ya no es conexo) y la aciclicidad es máxima (si agregamos una arista, el gráfico ya no es acíclico). Entonces, cualquier gráfico no dirigido conectado acíclico es un árbol, pero por simplicidad lo llamaremos árbol enraizado.
La raíz es un nodo fijo que determina la dirección de los bordes del árbol, por lo que aquí es donde "comienza" todo. Las hojas son los nodos terminales del árbol: es donde todo "termina".
Los vértices secundarios de un vértice son los vértices de los eventos debajo de él. Un vértice puede tener varios nodos secundarios. El padre de un vértice es el vértice del evento que se encuentra encima de él; es único.
¿Para qué se utilizan?
Siempre que necesitamos describir una estructura jerárquica, utilizamos árboles. Nuestro propio árbol genealógico es un ejemplo perfecto. Tus ancestros más antiguos son las raíces de los árboles. La generación más joven representa la colección de hojas.
Un árbol también puede representar la jerarquía de la empresa para la que trabajas. De esta manera podrás descubrir quiénes son tus superiores y a quién deberías dirigir.
Características
Un árbol binario es un tipo especial de árbol: cada vértice puede tener hasta dos nodos secundarios. En un árbol binario estricto, cada nodo, excepto las hojas, tiene dos nodos secundarios. ¿Un árbol binario completo de n niveles tiene los 2? -1 posible nodo.
Un árbol de búsqueda binario es un árbol binario en el que los valores de los nodos pertenecen a un conjunto completamente ordenado: el valor de un nodo elegido arbitrariamente es mayor que todos los valores del subárbol izquierdo y menor que todos los valores en el subárbol derecho todos los valores.
¿Para qué se utilizan?
Una aplicación importante de BT es la representación y evaluación de expresiones lógicas. Cada expresión se puede descomponer en variables/constantes y operadores. Este método de escribir expresiones se llama notación polaca inversa (RPN). De esta manera, pueden formar un árbol binario donde los nodos internos son operadores y las hojas son variables/constantes; se llama árbol de sintaxis abstracta (AST).
Los BST se utilizan a menudo porque permiten búsquedas rápidas de atributos clave. Los árboles AVL, los árboles rojo-negro, los conjuntos ordenados y los mapeos se implementan utilizando BST.
Características
BST tiene tres tipos de recorridos DFS:
Todos estos tipos de árboles son árboles de búsqueda binarios autoequilibrados. La diferencia es que equilibran la altura en tiempo logarítmico.
Los árboles AVL se autoequilibran después de cada inserción/eliminación porque la diferencia máxima de módulo entre las alturas de los subárboles izquierdo y derecho de un nodo es 1. AVL lleva el nombre de sus inventores: Adelson-Wilsky y Landis.
En un árbol rojo-negro, cada nodo almacena un bit adicional que representa el color para garantizar el equilibrio después de cada operación de inserción/eliminación.
En un árbol Splay, los nodos visitados recientemente se pueden volver a visitar rápidamente, por lo que la complejidad del tiempo amortizado de cualquier operación sigue siendo O(log n).
¿Para qué se utilizan?
AVL parece ser la mejor estructura de datos en la teoría de bases de datos.
RBT (Red-Black Tree) se utiliza para organizar segmentos de datos comparables, como segmentos de texto o números. En la versión 8 de Java, HashMap se implementa mediante RBT. Las estructuras de datos en geometría computacional y programación funcional también se construyen con RBT.
En Windows NT (en memoria virtual, red y código de sistema de archivos), el árbol Splay se utiliza para almacenamiento en caché, asignador de memoria, recolector de basura, compresión de datos, cuerda (no para caracteres de texto largos) cadena de instrumentos de cuerda).
Características
El montón mínimo es un árbol binario en el que el valor de cada nodo es mayor o igual que el valor de su nodo padre: val[par[x]]