Referência para o teorema fundamental das rotações das árvores

13

Diz-se que duas árvores de busca binária são linearmente equivalentes quando concordam em suas travessias em ordem. O seguinte teorema explica por que as rotações das árvores são tão fundamentais:

Sejam A e B árvores de pesquisa binárias. Então A e B são linearmente equivalentes se, e somente se, estiverem conectados por uma sequência de rotações em árvore.

Percebi esse resultado quando aprendi sobre estruturas de dados há muito tempo e queria entender o status especial das rotações de árvores mais profundamente.

A prova é simples e intuitiva: gire o menor elemento até a posição raiz ao longo da coluna esquerda. Pela ordem invariável, essa árvore reorganizada não pode ter uma subárvore esquerda. Agora recursione na subárvore direita. O resultado é uma forma normal para testar a equivalência linear.

Embora seja um teorema básico, nunca o encontrei na literatura. Gostaria muito de receber uma referência para a próxima vez em que precisar usar esse resultado.

(Quebra-cabeças bônus: qual é o melhor algoritmo para encontrar a menor seqüência de rotações de árvores que conecta duas árvores de pesquisa binária linearmente equivalentes?)

reference-request ds.data-structures Per Vognsen
fonte
Outro lugar para procurar pode ser a referência de que o módulo de equivalência de um operador associativo é decidível, pois isso equivale à mesma coisa. No entanto, todas as referências que tenho conhecimento tomam esse fato como garantido.
Rob Simmons

Respostas:

10

Como David Eppstein aponta aqui , nem se sabe que encontrar o caminho mais curto para árvores binárias seja em P. Nos comentários a essa resposta, ele vincula os melhores limites atuais

Suresh Venkat
fonte
Estou aceitando esta resposta desde que aprendi algo com ela. No entanto, eu ainda adoraria encontrar uma referência para o teorema da estrutura, se alguém souber um.
Por Vognsen 26/09/10
11

Um artigo inicial que fez essa observação explicitamente - que as rotações preservam as travessias não solicitadas - é (na Figura 2 de) as árvores de busca binária auto-ajustáveis de Sleator e Tarjan, de 1983 . A heurística de mudança para raiz foi estudada no artigo de 1978, de Allen e Munro, sobre Árvores de pesquisa binária auto-organizada .

Lev Reyzin
fonte
A direção interessante na equivalência de Per não é que as rotações se mantenham em ordem, mas que você pode viajar entre duas árvores que tenham a mesma ordem usando rotações.
Radu GRIGore
Sim - foi por isso que incluí a mudança para a raiz. Também há outro artigo de Sleator, Tarjan e Thurston (Distância de rotação, triangulações e geometria hiperbólica) calculando as distâncias entre duas árvores, que não incluí na minha resposta. Não acho que a observação de Per apareça em nenhum artigo como está, mas adoraria provar que estou errado.
Lev Reyzin
Certo, a direção fácil é uma parte necessária das provas de correção para árvores AVL, 2-3 árvores etc. A direção oposta é mais profunda. Ele diz que você não precisa de nenhuma transformação que preserve a estrutura além das rotações das árvores para garantir a integridade.
Por Vognsen 23/09/10
5

O(1)O(1)

Joan M. Lucas, O gráfico de rotação de árvores binárias é Hamiltoniano, Journal of Algorithms, Volume 8, Edição 4, Dezembro de 1987, Páginas 503-535, ISSN 0196-6774, DOI: 10.1016 / 0196-6774 (87) 90048-4 .

Uma prova mais simples, também construtiva, do fato mais simples de que existe um caminho hamiltoniano no gráfico de rotação pode ser encontrada neste artigo posterior, em co-autoria de Lucas e seus colaboradores.

Lucas JM, Vanbaronaigien DR, Ruskey F., On Rotations and the Generation of Binary Trees, Journal of Algorithms, Volume 15, Edição 3, Novembro 3, novembro de 1993, Páginas 343-366, ISSN 0196-6774, DOI: 10.1006 / jagm.1993.1045 .

Maverick Woo
fonte
-2

Uma prova mais simples, também construtiva, do fato mais simples de que um caminho hamiltoniano sai no gráfico de rotação pode ser encontrada neste último.

007singh
fonte
4
Sua resposta parece incompleta?
Jeremy