Salut,
 
Voila j'ai un souci de realisation d'un algo abstrait qui est sensé fusionner deux tas (representé par des arbres binaires) le tout en O(log n)
 
Les étapes pourrait être :
 
1) On séléctione la racine de l'arbre a et on l'inserer dans l'arbre b
 
2) on avance recursivement dans l'arbre a ...
 
Sachant que l'insertion se fait en O(log n) j'ai du mal. Plz help    
 
Sinon passer d'un TAS a un ABR en O(n) ?  

Ton bonheur :
http://www.brpreiss.com/books/opus5/html/page364.html

Excellent merci !
 

C'est sympa, je ne connaissais même pas l'existence des leftist trees !  
 
Mais dans ce genre je préfére les AVLs  
 
Il y aurait il un autre moyen de le faire ? rien qu'avec des arbres binaires tout cons ?

J'ai peut être pas compris ton problème, mais tu parle bien de fusionner deux tas ?
 
Parce que fusionner deux arbres binaires tout cons, c'est une opération en temps constant O(1). Il suffit de rattacher la racine d'un arbre à une feuille de l'autre arbre. Il n'est certes pas équilibré mais sans précision supplémentaire c'est l'algo optimal .
 
De plus, si tu veux fusionner deux tas, non gauchers (ou droitier), alors je crois que la complexité de l'opération est supérieure à O(log n1 + log n2).
 
En fait, je pense bien qu'il y a ce qu'il te faut dans le lien que je t'ai indiqué

Ceci peut être plus parlant pour fusionner deux tas "gauchers" :
 

 
Complexité : O(log n1 + log n2)

Si j'ai bien compris le "leftist" est une sorte d'AVL, chaque noeud de l'arbre comporte un champs supplementaire "nullPathLength" qui donne la longueur du plus court chemin entre le dit noeud et un noeud externe (donc vide), l'AVL a des noeuds avec un champs "déséquilibre" (au maximum 1). Donc ce champs "d" est rempli a chaque création d'un noeud dont on  
pourras supposer la complexité en O(1). C'est sympas ça quand même.
 
Mon probleme est bien de fusionner 2 tas (stockés sous forme d'arbres binaires donc pas de champs suppl), exemple (cas utopique ) :
 
     T1            T2     (Fusion T1 T2)=>    T3
 
      1             6                          1    
   2     3       7                        2       3
 4   5                                  4   5   6   7
                                         
 
Donc à priori T3 doit garder la propriété d'un TAS binaire (donc le déséquilibre n'est pas toléré). Sachant que T1 et T2 sont de même cardinalité (nb noeud) cad n = 2^(k+1) avec k>=0.

- Dans ton post precedant tu oublie volontairement de mettre a jour ce champs ??
 
- Justement le truc c'est que je ne pense pas avoir le droit a ce "rank"

Dans mon exemple ils ont pas la même cardinalité zut
 
     T1            T2     (Fusion T1 T2)=>    T3
 
      1            3                          1    
   2           4                       2            3
 
                                  4    
 
Voila.

Je pense que on O(log n) c'est impossible car si l'insertion, rien qu'a elle seul pompe O(log n) alors l'insertion de n éléments prendra O (n * log n).
Il y a peut etre un truc avec cette histoire de "même cardinalité" ...

Les "SKEW HEAPS", t'en a entendu parler ?
 
J'ai trouvé un cours en anglais sur ça, ils en parlent à la fin et ils disent que ça "amortis" la complexité a O(M*log n) ou M est le nombres d'opérations ... j'ai pas tout pigé
 
http://students.washington.edu/muk [...] -Heaps.ppt

Je pense qu'il faut juste que tu trouve un "petit" moyen de mémoriser la hauteur du sous-arbre gauche et celle du sous-arbre droit soit en attribut, soit en paramètre à ta fonction de fusion.
 
A partir de là le calcul de la hauteur (rank) n'en n'est plus un et on a une complexité O(log n1 + log n2)
si n1 = n2 = n, alors complexité de O(2 * log n) = O(log n) CQFD.
 
Skew heaps : entendu parlé mais juste de nom.
 
Bon, je dois préparer mes affaires pour mes vacances...
 
Bon courage

J'ai lu le lien. Très bon.
 
Les skew heaps seraient une amélioration algorithmique des leftist heaps. L'inconvénient de ces derniers est effectivement le stockage supplémentaire de la hauteur (ils appellent ca NullPathLength ou NPL). De plus lors de la fusion, on a tendance à alourdir d'office le sous-arbre droit alors qu'on sait pertinemment qu'on veut un arbre gaucher à la fin.
 
Donc, lors du merge, de l'arbre de plus petite racine on échange le sous-arbre gauche du sous-arbre droit, et on merge sur la gauche de cet arbre l'autre arbre de racine supérieure.
 
Ca à l'air plus simple et plus élégant que les arbres gauchers.

Tout ça sans le NPL  
 
Bonne vacances et merci