Étant donné une traversée PreOrder d'un arbre AVL. L'arbre est-il unique?

Question

Je travaille avec des arbres AVL pour une classe. J'ai besoin d'identifier n'importe quel arbre avec un hachage, pour construire ce hachage Je pensais trouver la traversée pré-ordre de tous les éléments dans l'arbre et ensuite construire le hachage en concaténant les hachages de chaque élément.

Premièrement, je voulais m'assurer qu'il n'y a pas de répétition AVLtrees pour la même chaîne de précommande. Même si je n'ai pas trouvé de contre-exemple, je n'en suis pas vraiment sûr.

Toute aide est appréciée!

Answer 1

Un BST (arbre de recherche binaire) sur des éléments distincts est uniquement déterminé par sa liste de traversée de précommande L: ceci peut être montré par induction.

En effet:

1. la r racine doit être le premier élément de L.
2. l'arbre sous gauche de r doit contenir tous les éléments moins r, et son parcours de pré-commande est la sous-liste de L contenant ces éléments: ainsi le sous-arbre de gauche est déterminé de manière unique, par induction.
3. même pour l'arbre droit sous r

Ce résultat est également valable pour un AVL, car il est un type spécial de BST.