¿Cuáles son algunas estructuras de datos y algoritmos menos conocidos que uno debería saber?

Question

Recientemente me encontré con la estructura de datos SkipList. Realmente me ayudó a resolver un problema que de otra manera sería difícil de resolver. Estaba luchando para resolverlo usando el árbol binario equilibrado, pero se volvió muy complejo ya que el árbol debe estar siempre equilibrado y quería saber la existencia no solo de un valor particular sino de valores en un cierto rango. SkipList me ayudó a resolver ese problema de manera efectiva.

Me pregunto qué otras estructuras de datos necesito saber? Sé sobre Array, List, Stack, Queue, Linked List, hashtable, tree y sus diferentes formas como B-tree, Trie etc. Me gustaría saber si encuentras alguna otra estructura de datos/concepto interesante y útil en un ciclo de desarrollo regular.

Answer 1

No mencionaste gráficos que son muy potentes y si no los conoces definitivamente deberías leerlos. Busque el algoritmo de Dijkstra y el algoritmo de búsqueda A *, así como la búsqueda general de profundidad general y la búsqueda inicial de amplitud.

También dejó montones, que a menudo se utilizan como la estructura subyacente para una cola de prioridad. Los montones binarios son los más simples, pero también podrías buscar montones min-max-medianos, montones binomiales (fusiones rápidas) y montones de Fibonacci (tecla de disminución rápida, útil para algunos algoritmos de gráficos).

Otras estructuras de datos interesantes incluyen intentos de Patricia que son intentos eficientes en el uso del espacio (codificados en subcadenas en lugar de caracteres), árboles de ajuste, que son balanceados y pueden programarse para que sean persistentes. También revise los filtros Bloom, que es una estructura de datos probabilísticos que le permite determinar si un elemento es miembro de un conjunto. Puede tener falsos positivos pero no falsos negativos y es eficiente en espacio/tiempo.

Finalmente, puede ir por la ruta funcional y buscar estructuras de datos inmutables y persistentes. Muchas de esas son solo versiones funcionales de estructuras de datos que usted ya conoce. Si está interesado en eso, le recomiendo que consulte las estructuras de datos puramente funcionales de Okasaki.

Answer 2

Tiene "Lista" y "Lista vinculada", y no está del todo claro qué diferencia (si hay alguna) tiene entre las dos. De todos modos, una estructura obvia que te salteaste es el montón (que podrías estar clasificando como un tipo de árbol, pero eso es bastante incierto en el mejor de los casos). En última instancia, los árboles son un subconjunto de gráficos, por lo que si no has estudiado los gráficos (en general), ese es probablemente un área para explorar.

Me gustaría señalar que ninguno de estos es particularmente "reciente", ya que todos se conocen desde hace décadas. La mayoría de estas estructuras realmente generales se conocen desde hace bastante tiempo. Los más recientemente descubiertos tienden a relacionarse con áreas temáticas más específicas.