Ensemble disjoint avec union par taille et compression des chemins ; l'arbre le plus grand peut-il devenir un sous-arbre de l'arbre le plus court ?

Question

Bonjour, c'est la première fois que je poste ici,

J'ai essayé d'élaborer une question pour étudier mais je n'ai pas réussi à la résoudre :

Nous considérons l'implémentation forestière du type de données abstrait disjoint-set, avec Union pondérée par la taille et Compression de chemin. Initialement, chaque élément se trouve dans un arbre à un nœud.

En partant de l'état initial ci-dessus :

1. donner une (courte) séquence d'opérations UNION et FIND dans laquelle la dernière opération est une UNION qui fait qu'un arbre plus grand A devient le sous-arbre d'un arbre plus petit B (c'est-à-dire que la hauteur de A est strictement plus grande que la hauteur de B).

2. Montrez aux deux arbres A et B que le dernier UNION fusionne

Conseil : vous pouvez partir de n = 9 éléments, chacun dans un arbre à un nœud.

---

Je ne sais pas comment cela pourrait fonctionner puisque l'arbre le plus petit est toujours fusionné avec l'arbre le plus grand en raison de l'union par taille ?

Merci.

Answer 1

Je ne veux pas répondre à vos devoirs, mais cette question est suffisamment ancienne pour que votre semestre soit probablement terminé, et dans tous les cas, un indice devrait suffire.

Il y a une distinction entre l'union par taille et l'union par hauteur principalement en raison de la compression du chemin. Plus précisément, la compression des chemins peut donner lieu à des nœuds de degré très élevé, et donc à des arbres comportant de nombreux nœuds mais une hauteur très courte. Par exemple, voici deux arbres que vous pouvez créer avec union find avec compression de chemin :

|T1:   o    (n=5, h=2)
|    /| |\ 
|   o o o o
|    
|T2:   o    (n=4, h=3)
|     /|
|    o o
|      |
|      o

Si l'opération suivante est une fusion de ces deux arbres, les algorithmes "union par rang" et "union par hauteur" sélectionneraient des parents différents.

En pratique, on utilise généralement "l'union par rang". Le rang est une limite supérieure de la hauteur qui peut être mise à jour en temps constant, et donne le meilleur temps d'exécution asymptotique. Une recherche sur le Web permet d'obtenir de nombreuses et bonnes explications sur cet algorithme.