Un artículo le presentará 30 estructuras de datos y algoritmos importantes

Los arrays son la estructura de datos más simple y común. Se caracterizan por un fácil acceso a los elementos por índice (posición).

¿Para qué se utilizan?

Imagina que hay una fila 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 y columnas de sillas) y tendrá una matriz 2D (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 manera, los elementos están vinculados mediante punteros.

¿Para qué se utilizan?

Una aplicación relacionada de las listas enlazadas es la implementación de la página anterior y la página siguiente del navegador. Una lista doblemente enlazada es la estructura de datos perfecta para almacenar las páginas mostradas por la búsqueda de un usuario.

Propiedades

Una pila es un tipo de datos abstracto que formaliza el concepto de colección de acceso restringido. Este límite sigue la regla LIFO (último en entrar, primero en salir). Entonces, el último elemento agregado a la pila es el primer elemento que elimina.

Las pilas se pueden implementar mediante matrices o listas enlazadas.

¿Para qué se utilizan?

El ejemplo más común de la vida real es el de apilar platos unos encima de otros en una cafetería. Primero se retira la placa superior. El plato colocado en la parte inferior es el que lleva más tiempo en la pila.

Una de las situaciones en las que las pilas son más útiles es cuando necesitas obtener el orden inverso de elementos dados. Simplemente empújelos todos hacia la pila y explótelos.

Otra aplicación interesante es el problema de los paréntesis válidos. Dada una cadena de paréntesis, puedes usar la pila para comprobar si coinciden.

Propiedades

Una cola es otro tipo de datos dentro de una colección 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, se utiliza una cola para mantener a los clientes esperando recibir 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 (nunca mejor dicho, se pronuncia "deck"). Los elementos se pueden insertar/eliminar desde ambos extremos de la cola.

Propiedades

Los mapas (diccionarios) son tipos de datos abstractos que contienen colecciones de claves y colecciones 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 en una matriz 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 la función de módulo constante. Por ejemplo, si la constante es 6, el valor de la clave x es x%6.

Lo ideal es que una función hash asigne cada clave a un depósito único, pero la mayoría de sus diseños emplean funciones imperfectas, lo que puede provocar que claves con el mismo valor generado entren en conflicto. Esta colisión siempre se adapta de alguna manera.

¿Para qué se utilizan?

La aplicación más famosa de Maps es el diccionario de idiomas. Cada palabra del idioma tiene una definición asignada. 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 asignado.

Otra aplicación útil es la estandarización de valores. Supongamos que queremos asignar un índice de 0 a 1439 a cada minuto del día (24 horas = 1440 minutos). La función hash será h(x) = x.hora*6x.minuto.

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 se realizan en O( log n) Completado dentro; 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 el conjunto de vértices (nodos) y E es el conjunto de aristas (flechas) . Los nodos son valores interconectados por bordes: líneas que describen la dependencia (a veces asociada con el costo/distancia) entre dos nodos.

Hay 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: flecha (x, y) no es lo mismo que flecha (y, x).

¿Para qué se utilizan?

Propiedades

La teoría de grafos es un campo muy amplio, pero nos centraremos en algunos de los conceptos más conocidos:

Un árbol es un grafo no dirigido, es más pequeño en términos de conectividad (si eliminamos una arista, el gráfico ya no es conexo) y más grande en términos de aciclicidad (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 llamaremos árbol a un á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, ahí es donde todo "termina".

Los hijos de un vértice son los vértices de 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?

Utilizamos árboles siempre que necesitamos representar una estructura jerárquica. Nuestro propio árbol genealógico es un ejemplo perfecto. Tus ancestros más antiguos son las raíces del árbol. La generación más joven representa la colección de hojas.

El árbol también puede representar la relación superior-subordinado en la empresa donde se trabaja. De esta manera, podrá saber quién le reporta y a quién debe administrar.

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 hijos. Un árbol binario completo con n niveles tiene los 2?-1 nodos posibles.

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 cualquier nodo elegido arbitrariamente es mayor que todos los valores del subárbol izquierdo y menor que el subárbol derecho todos los valores en el árbol.

¿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. Esta forma de escribir expresiones se llama notación polaca inversa (RPN). De esta manera, forman 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 una búsqueda rápida de atributos clave. Los árboles AVL, los árboles rojo-negro, los conjuntos ordenados y los mapas 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 la forma en que equilibran la altitud en tiempo logarítmico.

Los árboles AVL se autoequilibran después de cada inserción/eliminación porque la diferencia modular entre las alturas de los subárboles izquierdo y derecho de un nodo es como máximo 1. AVL lleva el nombre de sus inventores: Adelson-Velsky y Landis.

En un árbol rojo-negro, cada nodo almacena un bit adicional que representa el color, que se utiliza 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 datos comparables, como textos o números. En la versión Java 8, 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 y cuerdas (reemplazo de cadenas de texto largas).

Características

Un min-heap 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]]