Concaténer / Fusion / Unir deux arbres AVL

Question

Supposons que j'ai deux arbres AVL et en ce que chaque élément du premier arbre est plus petit que tous les éléments du deuxième arbre. Quelle est la manière la plus efficace de les concaténer en un seul arbre unique AVL? Je l'ai cherché partout, mais n'ai pas trouvé quelque chose d'utile.

Answer 1

En supposant que vous pouvez détruire les arbres d'entrée:

1. retirer l'élément le plus à droite de l'arbre gauche, et l'utiliser pour construire un nouveau nœud racine, dont l'enfant gauche est l'arbre gauche, et dont l'enfant est à droite de l'arbre droit: O (log n)
2. déterminer et régler le facteur d'équilibre de ce noeud: O (log n). En violation (temporaire) de l'invariant, le facteur d'équilibre peut être en dehors de la plage {-1, 0, 1}
3. tourner pour obtenir le facteur de l'équilibre dans plage: O (log n) rotations: O (log n)

Ainsi, l'opération peut être effectuée en O (log n).

Edit: la réflexion, il est plus facile de raisonner sur les rotations dans l'algorithme suivant. Il est également très probable plus rapide:

1. Déterminez la hauteur des deux arbres. O (log n)
   En supposant que l'arbre droit est plus grand (l'autre cas est symétrique):
2. retirer l'élément le plus à droite de l'arborescence de left (rotation et le réglage de sa hauteur calculée si nécessaire). Laissez n être cet élément. O (log n)
3. Dans l'arborescence droite, naviguer à gauche jusqu'à ce que vous atteignez un nœud dont le sous-arbre est au plus un plus grand que 1 left. Que r soit ce nœud. O (log n)

4. remplacer ce noeud à un nouveau noeud avec la valeur n, et des sous-arbres left et r. O (1)
   Par construction, le nouveau nœud est AVL équilibré, et son sous-arbre plus grand que 1 r.

5. incrémenter en conséquence l'équilibre de son parent. O (1)

6. et rééquilibrer comme vous le feriez après l'insertion. O (log n)

Answer 2

Une solution ultra simple (qui fonctionne sans aucune hypothèse dans les relations entre les arbres) est la suivante:

1. Faites une sorte de fusion des deux arbres dans un tableau fusionné (en même temps itérer les arbres).
2. Construire un arbre AVL à partir du tableau - prendre l'élément central à la racine, et appliquer de manière récursive à moitiés gauche et droite
.

Les deux étapes sont O (n). Le problème majeur avec c'est qu'il faut O (n) d'espace supplémentaire.

Answer 3

peut être trouvé la meilleure solution que je lis à ce problème . Est très proche de la réponse de Meriton si vous corrigez cette question:

Dans la troisième étape de l'algorithme gauche jusqu'à ce que vous Permet de naviguer à atteindre le nœud dont l'arbre sous a la même hauteur que l'arbre gauche . Ce n'est pas toujours possible, (voir l'image contre-). La bonne façon de faire cette étape est associé à deux pour un sous-arbre h hauteur ou h+1 où h est la hauteur de l'arbre gauche

Answer 4

Je soupçonne que vous aurez juste à marcher un arbre (espérons-le plus petit) et ajouter individuellement chacun il y a des éléments à l'autre arbre. Les opérations d'insertion / suppression AVL ne sont pas conçus pour gérer l'ajout d'un sous-arbre tout à la fois.