Quais são os papéis das árvores de pesquisa de leitura obrigatória?

9

Eu gostaria de pedir uma ajuda de pesquisadores que realizam uma pesquisa em uma área de árvores de pesquisa. Você poderia escrever a lista dos artigos de leitura obrigatória e os mais recentes que são importantes para ler se eu quiser escrever artigos sobre árvores de busca.

Pessoalmente, tenho a seguinte lista de artigos (é não uniforme, bastante antigo e afeta tópicos diferentes. Há também uma enorme quantidade de artigos sobre a árvore de busca por dedos, mas não escrevi referências a eles). Obrigado pela ajuda.

  • Daniel Dominic Sleator e Robert Endre Tarjan. 1985. Árvores de busca binária auto-ajustáveis. J. ACM 32, 3 (julho de 1985), 652-686. DOI = http://dx.doi.org/10.1145/3828.3835

  • Daniel D. Sleator e Robert Endre Tarjan. 1983. Uma estrutura de dados para árvores dinâmicas. J. Comput. Syst. Sci. 26, 3 (junho de 1983), 362-391. DOI = http://dx.doi.org/10.1016/0022-0000(83)90006-5

  • Scott Huddleston e Kurt Mehlhorn. 1982. Uma nova estrutura de dados para representar listas classificadas. Acta Inf. 17, 2 (junho de 1982), 157-184. DOI = http://dx.doi.org/10.1007/BF00288968

  • Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane e Mihai Pătraşcu. 2009. A geometria das árvores de pesquisa binária. Nos Anais do XX Simpósio Anual ACM-SIAM sobre Algoritmos Discretos (SODA '09). Sociedade de Matemática Industrial e Aplicada, Filadélfia, PA, EUA, 496-505.

  • Samuel W. Bent, Daniel D. Sleator e Robert E. Tarjan. Árvores de pesquisa enviesada. Jornal SIAM sobre Computação 1985 14: 3, 545-568

  • Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak: Árvores de pesquisa binária auto-ajustáveis: o que as faz funcionar? SEC 2015: 300-312

Desde que conduzi pesquisas na área de concatenação rápida de árvores de pesquisa:

  • Haim Kaplan e Robert E. Tarjan. 1996. Representações puramente funcionais de listas ordenadas com possibilidade de catenable. Em Anais do vigésimo oitavo simpósio anual da ACM sobre Teoria da Computação (STOC '96). ACM, Nova Iorque, NY, EUA, 202-211. DOI = http://dx.doi.org/10.1145/237814.237865
  • Pior caso puramente funcional Listas ordenadas por tempo constante. Notas de aula em Ciência da Computação. Gerth Stølting Brodal, Christos Makris e Kostas Tsichlas. Algoritmos - SEC 2006, capítulo 18, 172-183. Berlim, Heidelberg. http://link.springer.com/10.1007/11841036_18
ds.data-structures binary-trees rbtrht
fonte

Respostas:

7

Sleator-Tarjan '85 e Demaine et al '09 definitivamente pertencem a essa lista. Há muitos outros trabalhos recentes relacionados a árvores de espalhamento e otimização dinâmica, por exemplo:

  • Aplicações de matrizes 0-1 proibidas para pesquisar estruturas de dados baseadas em compactação em árvore e caminho, Seth Pettie, SODA 2010
  • Uma árvore de pesquisa binária competitiva com O (log log n) com tempos ideais de acesso para os piores casos, Bose et al, SWAT 2010
  • Limites superiores para árvores de pesquisa binária maximamente gananciosas, Kyle Fox, WADS 2011.
  • Descentralizando árvores de pesquisa binária, Bose et al, ICALP 2012
  • Acesso para evitar padrões em árvores de pesquisa binária, Chalermsook et al, FOCS 2015
  • Dedo dinâmico ponderado em árvores de pesquisa binária, Iacono e Langerman, SODA 2016

Em linhas mais clássicas, acho

  • Árvores de classificação equilibrada, Haeupler, Sen e Tarjan, ACM TALG 2015

vale a pena incluir como uma elegante unificação de árvores AVL e vermelho-preto.

David Eppstein
fonte