¿Cuáles son los papeles de los árboles de búsqueda de lectura obligatoria?

9

Me gustaría pedir ayuda a los investigadores que realizan una investigación en un área de árboles de búsqueda. ¿Podría por favor escribir la lista de los documentos que debe leer y los documentos más recientes que es importante leer si quiero escribir documentos sobre árboles de búsqueda?

Personalmente, tengo la siguiente lista de documentos (no es uniforme, es bastante antigua y afecta a diferentes temas. También hay una gran cantidad de documentos sobre el árbol de búsqueda de dedos, pero no escribí referencias a ellos). Gracias por ayudar.

  • Daniel Dominic Sleator y Robert Endre Tarjan. 1985. Árboles de búsqueda binarios autoajustables. J. ACM 32, 3 (julio de 1985), 652-686. DOI = http://dx.doi.org/10.1145/3828.3835

  • Daniel D. Sleator y Robert Endre Tarjan. 1983. Una estructura de datos para árboles dinámicos. J. Comput. Syst. Sci. 26, 3 (junio de 1983), 362-391. DOI = http://dx.doi.org/10.1016/0022-0000(83)90006-5

  • Scott Huddleston y Kurt Mehlhorn. 1982. Una nueva estructura de datos para representar listas ordenadas. Acta Inf. 17, 2 (junio de 1982), 157-184. DOI = http://dx.doi.org/10.1007/BF00288968

  • Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane y Mihai Pătraşcu. 2009. La geometría de los árboles de búsqueda binarios. En Actas del vigésimo Simposio anual ACM-SIAM sobre Algoritmos discretos (SODA '09). Society for Industrial and Applied Mathematics, Filadelfia, PA, EE. UU., 496-505.

  • Samuel W. Bent, Daniel D. Sleator y Robert E. Tarjan. Árboles de búsqueda sesgados. SIAM Journal on Computing 1985 14: 3, 545-568

  • Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak: Árboles de búsqueda binaria autoajustables: ¿qué los hace funcionar? ESA 2015: 300-312

Desde que realicé una investigación en el área de concatenación rápida de árboles de búsqueda:

  • Haim Kaplan y Robert E. Tarjan. 1996. Representaciones puramente funcionales de listas ordenadas ordenables. En Actas del vigésimo octavo simposio anual de ACM sobre Teoría de la informática (STOC '96). ACM, Nueva York, NY, EE. UU., 202-211. DOI = http://dx.doi.org/10.1145/237814.237865
  • El peor de los casos, puramente funcional, listas ordenadas catenables en tiempo constante. Lecture Notes in Computer Science. Gerth Stølting Brodal, Christos Makris y Kostas Tsichlas. Algoritmos - ESA 2006, Capítulo 18, 172-183. Berlín, Heidelberg. http://link.springer.com/10.1007/11841036_18
ds.data-structures binary-trees rbtrht
fuente

Respuestas:

7

Sleator-Tarjan '85 y Demaine et al '09 definitivamente pertenecen a dicha lista. Hay muchos otros trabajos recientes relacionados con árboles de despliegue y optimización dinámica, por ejemplo:

  • Aplicaciones de matrices 0-1 prohibidas para buscar estructuras de datos basadas en compresión de árbol y ruta, Seth Pettie, SODA 2010
  • Un árbol de búsqueda binaria competitivo O (log log n) con tiempos de acceso óptimos en el peor de los casos, Bose et al, SWAT 2010
  • Límites superiores para árboles de búsqueda binaria codiciosos, Kyle Fox, WADS 2011.
  • Des amortización de árboles de búsqueda binarios, Bose et al, ICALP 2012
  • Acceso para evitar patrones en árboles de búsqueda binarios, Chalermsook et al, FOCS 2015
  • Dedo dinámico ponderado en árboles de búsqueda binaria, Iacono y Langerman, SODA 2016

En líneas más clásicas, creo

  • Árboles de rango equilibrado, Haeupler, Sen y Tarjan, ACM TALG 2015

Vale la pena incluirlo como una elegante unificación de AVL y árboles rojo-negros.

David Eppstein
fuente