Comment je peut fusionner deux arbres binaires
J'ai deux arbres binaires, et je tiens à les fusionner.
Ma première question est que si l'on peut fusionner deux arbres binaires, et si oui comment efficacement, je peux effectuer les opérations de fusion et quelles sont les différentes façons d'effectuer les opérations de fusion. ..?
La fusion des arbres binaires est trivial, juste un lien de la racine d'un enfant de l'un des nœuds feuilles de l'autre. Avez-vous une autre structure que vous souhaitez conserver, comme l'a ordonné ou équilibré?
permet de commencer avec de simples non ordonnée déséquilibrée de l'arbre . Vous avez dit que c'est trivial si u peut juste me montrer comment c'est fait..?
permet de commencer avec de simples non ordonnée déséquilibrée de l'arbre . Vous avez dit que c'est trivial si u peut juste me montrer comment c'est fait..?
OriginalL'auteur saurabh ranu | 2011-08-22
Vous devez vous connecter pour publier un commentaire.
Pas tenu compte de l'efficacité de cette réponse peut travailler Algorithme de la combinaison de deux arbres binaires? . Si triés ou équilibré, la discussion sur l'efficacité de Comment fusionner deux BST est efficace? et La concaténation/Fusion/association de deux arbres AVL
OriginalL'auteur David Andersson
1) Aplatissez les deux arbres de listes triées.
2) Fusionner les listes de ce que vous avez obtenu en 1)
3) Construire l'arbre de ce que vous avez obtenu en 2)
Vous pouvez aplatir les arbres dans des listes en O(n) fois à l'aide d'un standard dans l'ordre de marche. La fusion de deux listes triées peut être fait en O(n) fois. Une fois que vous avez fusionné les listes, vous pouvez construire le BST en O(n) fois par de manière récursive la construction d'arbres de la moitiés gauche et droite, puis de les coller ensemble. La complexité est donc en O(n).
Merci pour la réponse. Oui, la complexité est O(n).
le bien est tout ce qui peut être fait en log(n)?
normal: je ne le crois pas.
OriginalL'auteur hari
Cette algorithme peut vous aider.
Oui, c'est fait. Depuis que nous savons qu'ils sont BST, nous pouvons organiser les arbres dans une liste triée. Une fois que nous avons les 2 listes triées, cet algorithme s'applique.
OriginalL'auteur Dan W
Créer un nouveau nœud et point d'une seule queue à la tête de l'un des arbres et point à l'autre de la queue à la tête de l'autre arbre. Peut-être vous avez besoin de clarifier votre question pour être plus précis. Quelles sont les relations qui sont que vous essayez de conserver?
OriginalL'auteur jones
D'un arbre est aussi un graphe, de sorte que la sortie de la pointe de vertex-paires (u,v) pour chaque arbre, et ensuite de l'union de ces carres, et sortie le graphe obtenu.
La question se pose de savoir comment la carte sommets d'un arbre à l'sommets dans l'autre (par exemple, nous avons de bord la paire (5,9) dans l'arbre 1 et bord la paire (5,6) de l'arbre 2, ces 5s correspondent à la même sommet ? ).
À venir avec une numérotation des sommets (peut-être qui attribue un numéro à chaque sommet incomplète arbre binaire, comme si c'était un arbre binaire complet, en d'autres mots attribue les sommets en toute partielle arbre binaire de logements d'une hypothétique complète arbre binaire dont l'arbre est un sous-arbre), qui fournit en quelque sorte une souhaitable d'équivalence est quelque chose qui fonctionne.
OriginalL'auteur user2530580