¿Cuáles son todas las estructuras de datos que conoce? ¿Cuál de estos usas con frecuencia? Agrúpelos en “Básico” y “Avanzado”.

Elegí las estructuras de datos en función de lo que más utilicé para mis proyectos en la escuela y en el trabajo. En general, la mayoría de mis proyectos se han realizado utilizando estructuras de datos simples, solo en algunas situaciones he utilizado las complejas.

Lineal simple:
Matrices
Listas vinculadas
Pilas
Colas
Disjoint Set Linked List

Lineal complejo:
Saltar lista
Conjuntos desordenados (basados ​​en hash)

Gráfica simple:
Arboles
Intentos
Árboles B
Montones (Binomial, Fibonacci)
Árbol de búsqueda binaria
Colas de prioridad (implementadas usando montones)
Árbol de búsqueda binaria de equilibrio automático (árbol rojo negro)
Splay Tree
Conjunto / Mapa (ordenado): se puede implementar con árboles

Gráfica compleja:
Treap (BST aleatorizado)
Filtros de floración
Fenwick Tree (árbol de índice binario)
Árbol de segmento
Árbol Kd

Las estructuras de peso equilibrado (árbol binario, lista de salto, treaps, etc.) es una idea muy importante, pero generalmente no se enseña (me consideraría muy afortunado de ser expuesto por mi profesor de algoritmos de posgrado, Dr. Bender 🙂). Los clasificaría en intermedios.

También hay un conjunto completo de estructuras de datos de memoria externa, muchas de las cuales se pueden encontrar bellamente explicadas por el Dr. Bender aquí: http://www.cs.sunysb.edu/~bender …

Las estructuras de datos también se denominan “algoritmos cristalizados”, y puede (a veces) convertir un algoritmo en una estructura de datos, robando ideas de allí. Ejemplos incluyen:
1. búsqueda binaria <-> árbol binario
2. fusionar sort <-> COLA (matriz de búsqueda inconsciente de caché)

También hay otras técnicas, como la indirección, que se pueden aplicar tanto a los algoritmos como a las estructuras de datos para reducir el tiempo de ejecución de ciertas operaciones. La indirecta es una técnica para dividir la entrada en un gran universo y un pequeño universo y manejarlos por separado. Los ejemplos incluyen tiempo lineal LCA, fusión de tiempo de línea en el lugar, etc.

Otras técnicas de uso común utilizadas en conjunto con las estructuras de datos son el análisis amortizado (creación de almacenamiento lineal en el tiempo, unión-búsqueda, montones binomiales, etc.) y la propagación diferida.

La recursión es siempre otra técnica útil para saber. Ejemplos: árboles binarios, montones, árboles vEB.

Todas estas son técnicas útiles para conocer y utilizar.

1) Lista vinculada: la OMI más subestimada y subutilizada. He visto muchas grandes ganancias de rendimiento al refactorizar las estructuras de datos centrales a las listas de enlaces

2) Lista de omisión: algoritmo fácil de implementar, seguro para los hilos, de búsqueda y clasificación que tiene un registro de la complejidad de tiempo esperada

3) quadtrees / octrees: ideal para particiones espaciales en la programación de juegos

Básico: pila, cola, lista vinculada, cola prioritaria, lista circular vinculada, lista doblemente enlazada, árbol, gráfico, conjunto, mapa, matriz, montón, etc.

Avanzado: árbol negro rojo, árbol de índice binario, árbol B / B +, matrices dispersas, hipergrafía, árboles BSP, etc.

1. Pilas
2. Colas
3. Matrices
4. Listas enlazadas
5. Árbol de búsqueda binaria
6. Muchísimo
7. Mapas de hash