Récursive set union: comment cela fonctionne-t-il vraiment?

j'en déduis que incl insère un élément dans un ensemble existant? Si oui, c'est là que le vrai travail se passe.

La définition de l'union est l'ensemble qui inclut tout ce qui en soit d'entrée de jeu. Étant donné deux ensembles stockés sous forme d'arbres binaires, si vous prenez les unions du premier ensemble avec les branches du deuxième, le seul élément dans l'un ou l'autre qui pourrait être absent du résultat est l'élément au noeud racine du deuxième arbre, donc si vous insérez cet élément vous avez le l'union de tous entrée de jeux.

c'est juste une façon très inefficace d'insérer chaque élément des deux ensembles dans un nouvel ensemble qui commence vide. Les doublons sont probablement éliminés par incl, donc le résultat est l'union des deux entrées.

peut-être que cela aiderait à ignorer la structure de l'arbre pour le moment; ce n'est pas vraiment important pour l'algorithme essentiel. Disons que nous avons des ensembles mathématiques abstraits. Étant donné un ensemble d'entrées avec des éléments inconnus, nous pouvons faire deux les choses les choses:

• Ajouter un élément (qui ne fait rien si l'élément est déjà présent)
• vérifiez si l'ensemble n'est pas vide et, si c'est le cas, décomposez-le en un seul élément et deux sous-ensembles disjoints.

pour prendre l'union de deux ensembles {1,2} et {2,3}, nous commençons par décomposer le premier ensemble en l'élément 1 et les sous-ensembles {} et {2}. Nous récursive de l'union, {}, {2}, et {2,3} en utilisant le même processus, puis insérez-1 dans le résultat.

à chaque étape, le problème est réduit d'une opération syndicale à deux opérations syndicales sur des entrées plus petites; un algorithme standard de diviser pour mieux régner. Lorsque l'on atteint l'union d'un ensemble unique et d'un ensemble vide, l'union est triviale, puis remontée dans la chaîne.

la structure de l'arbre est juste utilisée pour permettre l'analyse de cas/décomposition en ensembles plus petits, et pour rendre l'insertion plus efficace. La même chose pourrait être faite en utilisant d'autres données structures, telles que des listes qui sont divisées en deux pour la décomposition et avec l'insertion fait par un contrôle exhaustif pour l'unicité. Prendre le syndicat efficacement nécessite un algorithme qui est un peu plus intelligent, et tire profit de la structure utilisée pour stocker les éléments.

donc basé sur toutes les réponses ci-dessus, je pense que le vrai cheval de travail est incl et la récursivité de l'appel de union est juste pour passer à travers tous les éléments de décors.

j'ai proposé la mise en œuvre suivante de l'union, est-ce mieux?

def union(other:BTSet) :BTSet = right union (left union (other incl element))

  2
 / \  union  4
1   3

((1 union 3) union 4) incl 2
  ^^^^^^^^^......................................assume it works

(((E union E) union 3 incl 1) union 4) incl 2
   ^^^^^^^^^.....................................still E

(E union E) union 3 incl 1 = E union 3 incl 1 = 3 incl 1

le sous-groupe suivant doit être 3 incl1

(  3             ) 
(    \   union D ) incl 2
(      1         )


(((1 union E) union 4) incl 3) incl 2
   ^^^^^^^^^.......................................expand

(((( (E union E) union E) incl 1) union 4) incl 3) incl 2
      ^^^^^^^^^^^^^^^^^^^^^^^^^^..................still 1

((1 union 4) incl 3) incl 2
   ^^^^^^^^......................................continue

((((E union E) union 4) incl 1) incl 3) incl 2
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^..........expand 1 union 4

((4 incl 1) incl 3) incl 2
  ^^^^^^^^^^^^^^^^^^^^^^^^^............Final union result 

Merci @Rex Kerr sort les marches. Je substitue la deuxième étape avec l'étape d'exécution réelle, qui peut donner une description plus claire de La Scala union fonction.

vous ne pouvez pas comprendre les algorithmes récursifs à moins de regarder le cas de base. En fait, souvent, la clé de la compréhension réside dans la compréhension du scénario de base d'abord. Puisque le cas de base n'est pas montré (probablement parce que vous n'avez pas remarqué il y a un en premier lieu) il n'y a aucune compréhension possible.

je fais le même cours, et la mise en œuvre ci-dessus de union a s'avèrent être extrêmement inefficace.

j'ai trouvé la solution non-fonctionnelle suivante pour créer une union d'ensembles d'arbres binaires, qui est beaucoup plus efficace:

def union(that: BTSet): BTSet = {
  var result:BTSet = this
  that.foreach(element => result = result.incl(element))
  result
}