Référence pour le théorème fondamental sur les rotations des arbres

13

On dit que deux arbres de recherche binaires sont linéairement équivalents lorsqu'ils s'accordent dans leurs traversées dans l'ordre. Le théorème suivant explique pourquoi les rotations d'arbres sont si fondamentales:

Soit A et B des arbres de recherche binaires. Alors A et B sont linéairement équivalents si et seulement s'ils sont reliés par une séquence de rotations d'arbres.

J'ai remarqué ce résultat lorsque j'ai découvert pour la première fois les structures de données il y a longtemps et je voulais comprendre plus profondément le statut spécial des rotations d'arbres.

La preuve est simple et intuitive: faites pivoter le moindre élément jusqu'à la position racine le long de la colonne vertébrale gauche. Par l'ordre invariant, cet arbre réarrangé ne peut pas avoir de sous-arbre gauche. Maintenant récursif sur le sous-arbre droit. Le résultat est une forme normale pour tester l'équivalence linéaire.

Bien qu'il s'agisse d'un théorème de base, je ne l'ai jamais rencontré dans la littérature. J'apprécierais grandement une référence pour la prochaine fois que j'aurai besoin d'utiliser ce résultat.

(Bonus cerveau teaser: Quel est le meilleur algorithme pour trouver la séquence la plus courte de rotations d'arbres qui connectent deux arbres de recherche binaire linéairement équivalents?)

reference-request ds.data-structures Per Vognsen
la source
Un autre endroit à rechercher pourrait être une référence que l'équivalence modulo d'un opérateur associatif est décidable, car cela revient à la même chose. Cependant, toutes les références que je connais tiennent ce fait pour acquis.
Rob Simmons

Réponses:

10

Comme David Eppstein le souligne ici , même le fait de trouver le chemin le plus court pour les arbres binaires n'est pas connu en P. Dans les commentaires de cette réponse, il établit un lien vers les meilleures limites actuelles.

Suresh Venkat
la source
J'accepte cette réponse depuis que j'en ai appris quelque chose. Cependant, j'aimerais toujours trouver une référence pour le théorème de la structure si quelqu'un en connaît un.
Per Vognsen
11

Un des premiers articles qui a fait cette observation explicitement - que les rotations préservent les traversées dans l'ordre - est (dans la figure 2 de) les arbres de recherche binaires auto-ajustables de 1983 de Sleator et Tarjan . L'heuristique de déplacement vers la racine a été étudiée dans l'article d'Allen and Munro de 1978 sur les arbres de recherche binaires auto-organisés .

Lev Reyzin
la source
La direction intéressante de l'équivalence de Per n'est pas que les rotations se conservent dans l'ordre, mais que vous pouvez vous déplacer entre deux arbres qui ont le même ordre dans les rotations.
Radu GRIGore
Oui - c'est pourquoi j'ai inclus la racine de déplacement. Il y a aussi un autre article de Sleator, Tarjan et Thurston (Rotation Distance, Triangulations, and Hyperbolic Geometry) calculant les distances entre deux arbres, que je n'ai pas inclus dans ma réponse. Je ne pense pas que l'observation de Per apparaisse dans un seul article tel quel, mais j'aimerais avoir tort.
Lev Reyzin
À droite, la direction facile est une partie nécessaire des preuves de correction pour les arbres AVL, 2-3 arbres, etc. La direction opposée est plus profonde. Il indique que vous n'avez besoin d'aucune transformation préservant la structure autre que la rotation des arbres pour être complet.
Per Vognsen
5

O(1)O(1)

Joan M. Lucas, The graph of rotation of binary trees is Hamiltonian, Journal of Algorithms, Volume 8, Issue 4, décembre 1987, Pages 503-535, ISSN 0196-6774, DOI: 10.1016 / 0196-6774 (87) 90048-4 .

Une preuve plus simple, également constructive, du fait plus simple qu'il existe un chemin hamiltonien dans le graphique de rotation peut être trouvée dans cet article ultérieur co-écrit par Lucas et ses collaborateurs.

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
la source
-2

Une preuve plus simple, également constructive, du fait plus simple qu'un chemin hamiltonien sort dans le graphique de rotation peut être trouvée dans ce dernier.

007singh
la source
4
Votre réponse semble incomplète?
Jeremy