Referencia para el teorema fundamental sobre las rotaciones de los árboles.

13

Se dice que dos árboles de búsqueda binarios son linealmente equivalentes cuando están de acuerdo en sus recorridos en orden. El siguiente teorema explica por qué las rotaciones de árboles son tan fundamentales:

Deje que A y B sean árboles binarios de búsqueda. Entonces A y B son linealmente equivalentes si y solo si están conectados por una secuencia de rotaciones de árbol.

Noté este resultado cuando aprendí por primera vez acerca de las estructuras de datos hace mucho tiempo y quería comprender más profundamente el estado especial de las rotaciones de árboles.

La prueba es simple e intuitiva: gire el elemento mínimo hasta la posición de la raíz a lo largo de la columna vertebral hacia la izquierda. Por el orden invariante, este árbol reordenado no puede tener un subárbol izquierdo. Ahora recurse en el subárbol derecho. El resultado es una forma normal para probar la equivalencia lineal.

Si bien es un teorema básico, nunca lo he encontrado en la literatura. Agradecería enormemente una referencia para la próxima vez que necesite usar este resultado.

(Bonus brain teaser: ¿Cuál es el mejor algoritmo para encontrar la secuencia más corta de rotaciones de árboles que conectan dos árboles de búsqueda binarios linealmente equivalentes?)

reference-request ds.data-structures Por Vognsen
fuente
Otro lugar para buscar podría ser una referencia de que el módulo de equivalencia de un operador asociativo es decidible, ya que esto equivale a lo mismo. Sin embargo, todas las referencias que conozco dan por hecho este hecho.
Rob Simmons

Respuestas:

10

Como David Eppstein señala aquí , incluso no se sabe que encontrar el camino más corto para árboles binarios se encuentra en P. En los comentarios a esa respuesta, se vincula a los mejores límites actuales

Suresh Venkat
fuente
Estoy aceptando esta respuesta ya que aprendí algo de ella. Sin embargo, todavía me encantaría encontrar una referencia para el teorema de la estructura si alguien conoce uno.
Según Vognsen el
11

Un primer artículo que hizo esta observación explícitamente (que las rotaciones preservan los recorridos internos) es (en la Figura 2 de) los árboles de búsqueda binaria autoajustable de Sleator y Tarjan de 1983 . La heurística de mover a la raíz se estudió en el artículo de 1978 Autoorganizing Binary Search Trees de Allen and Munro .

Lev Reyzin
fuente
La dirección interesante en la equivalencia de Per no es que las rotaciones se mantengan en orden, sino que puede viajar entre dos árboles que tengan el mismo orden usando rotaciones.
Radu GRIGore
Sí, es por eso que incluí el movimiento a la raíz. También hay otro artículo de Sleator, Tarjan y Thurston (Distancia de rotación, triangulaciones y geometría hiperbólica) que calcula las distancias entre dos árboles, que no incluí en mi respuesta. No creo que la observación de Per aparezca en ningún artículo tal como es, pero me encantaría que me demuestren lo contrario.
Lev Reyzin
Correcto, la dirección fácil es una parte necesaria de las pruebas de corrección para árboles AVL, 2-3 árboles, etc. La dirección opuesta es más profunda. Dice que no necesita ninguna transformación para preservar la estructura que no sea la rotación de los árboles para completar.
Por Vognsen
5

Dado que está interesado en la estructura de las rotaciones de árboles, creo que también puede estar interesado en el siguiente documento, que muestra que el gráfico de rotación de árboles binarios de un número fijo de nodos tiene un ciclo hamiltoniano . De hecho, Lucas demostró que el ciclo puede atravesarse con un retraso constante por árbol. (Se puede realizar una rotación enO(1) tiempo, por supuesto, pero no es obvio a priori que podamos decidir qué rotación realizar a lo largo del ciclo hamiltoniano en O(1) tiempo.) Naturalmente, también puede estar interesado en las referencias dentro.

Joan M. Lucas, El gráfico de rotación de árboles binarios es Hamiltoniano, Journal of Algorithms, Volumen 8, Número 4, diciembre de 1987, páginas 503-535, ISSN 0196-6774, DOI: 10.1016 / 0196-6774 (87) 90048-4 .

Una prueba más simple, también constructiva, del hecho más simple de que existe un camino hamiltoniano en el gráfico de rotación se puede encontrar en este artículo posterior en coautoría de Lucas y sus colaboradores.

Lucas JM, Vanbaronaigien DR, Ruskey F., On Rotations and the Generation of Binary Trees, Journal of Algorithms, Volume 15, Issue 3, November 1993, Pages 343-366, ISSN 0196-6774, DOI: 10.1006 / jagm.1993.1045 .

Maverick Woo
fuente
-2

Una prueba más simple, también constructiva, del hecho más simple de que una ruta hamiltoniana sale en el gráfico de rotación se puede encontrar en este último.

007singh
fuente
44
¿Tu respuesta parece incompleta?
Jeremy