Comment fusionner deux BST est efficace?

Comment fusionner deux arbres binaires de maintenir la propriété de BST?

Si nous décidons de prendre chaque élément de l'arbre et de l'insérer dans l'autre, la complexité de cette méthode serait O(n1 * log(n2)), où n1 est le nombre de nœuds de l'arbre (dire T1), qui nous ont séparés, et n2 est le nombre de nœuds de l'autre arbre (dire T2). Après cette opération, un seul BST a n1 + n2 nœuds.

Ma question est: peut-on faire mieux que O(n1 * log(n2))?

  • L'insertion de la racine de l'arbre 1 arbre 2 ne fonctionnera pas dans tous les cas.
  • Vous faites l'hypothèse que tous les arbres binaires équilibrés. (Par exemple, s'écartent les arbres ne sont pas) je pense Également que votre complexité est un peu hors. Parce que n2 est en augmentation, l'arbre va plus profondément que vous insérez des valeurs. Peut-être (n1 + n2) / 2 est une meilleure approximation (Parce qu'au début de l'insert, il est O(log n2) pour insérer et à la fin il est O(log(n1 + n2)).
  • Teran, un<-c->h union b<-d->f par exemple, leur intervalle [a,h] et [b,f] se chevauchent et donc ne peut être insérée dans un autre comme un nœud feuille
InformationsquelleAutor gowth08 | 2009-06-17
  1. 26

    Naaff de répondre avec un peu plus de détails:

    • De l'aplatissement d'un BST dans une liste triée est O(N)
      • C'est juste "dans l'ordre" itération sur l'ensemble de l'arbre.
      • De le faire pour les deux est O(n1+n2)
    • La fusion de deux listes triées est dans une liste triée est O(n1+n2).
      • Garder des pointeurs vers les têtes de listes
      • Choisir la plus petite tête et de faire avancer son pointeur
      • C'est comment la fusion de fusion-tri fonctionne
    • La création d'un parfait équilibre de la BST, à partir d'une liste triée est O(N)
      • Voir l'extrait de code ci-dessous pour l'algorithme[1]
      • Dans notre cas, la liste triée est de taille n1+n2. donc O(n1+n2)
      • L'arbre résultant serait le conceptuel BST binaire de recherche dans la liste

    Trois étapes de O(n1+n2) résultat en O(n1+n2)

    Pour n1 et n2 du même ordre de grandeur, c'est mieux que O(n1 * log(n2))

    [1] de l'Algorithme pour la création d'un équilibre BST à partir d'une liste triée (en Python):

    def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {'left': left, 'node': node, 'right': right}
    • Esquisse de la preuve que vous ne pouvez pas l'améliorer: Vous devez tenir compte de chaque élément. Entre 2 adjacentes valeurs dans l'arbre 1 il y a peut être de 0,1 ou plusieurs valeurs pour être trouvé dans l'arbre 2. Simplement en regardant N1+N2 éléments déjà prend O(N1+N2) de temps.
    • selon l'OP vous êtes autorisé à modifier un arbre en place. vous n'avez pas à regarder tous les éléments de l'arborescence en cours de modification
    • J'ai quelques difficultés dans la compréhension de la façon dont la dernière étape de la création de l'équilibre de la STB est O(N). Depuis la structure de données utilisée ici est une liste de, ne sera pas la complexité de trouver le "milieu" pour les n éléments à chaque niveau de la récursivité, n/2 ? De sorte que le total de la complexité de la création de l'équilibre BST serait n/2 log n, droite ? Si les données sont triées était dans un tableau, je peux voir comment cela peut être fait en O(N). Mais ce n'est pas le cas ici. Ce qui me manque?
    • Mon explication n'était en effet pas trop précis, a ajouté l'algorithme, avec un extrait de code pour la réponse maintenant.
    InformationsquelleAutor yairchu
  2. 20
    • Aplatir arbres dans les listes triées.
    • De fusion de listes triées.
    • Créer l'arborescence de liste fusionnée.

    IIRC, qui est en O(n1+n2).

    InformationsquelleAutor Stu
  3. 8

    Que sur l'aplatissement des deux arbres dans les listes triées, la fusion des listes et ensuite, la création d'une nouvelle arborescence?

    • Comme d'autres l'ont fait après mon post, la complexité de cette procédure est de O(n1+n2). Voir, par exemple, yairchu élaboration sur ma réponse.
    • infini redirection en boucle entre votre poste et @yairchu.
    InformationsquelleAutor Naaff
  4. 1

    Jonathan,

    Après le tri, nous avons une liste de longueur n1+n2. La construction d'un arbre binaire de il faudra log(n1+n2) de temps. C'est la même que la fusion de tri, seulement qu'à chaque étape récursive nous avons l'habitude d'avoir un O(n1+n2), terme que nous avons en fusion algorithme de tri . Donc, la complexité du temps est log(n1+n2).

    Maintenant la complexité de l'ensemble du problème est O(n1+n2).

    Aussi, je dirais que cette approche est bien si les deux listes sont de taille comparable. Si les tailles ne sont pas comparables, alors il est préférable d'insérer chaque nœud de l'arbre de petite taille dans un grand arbre. Cela permettrait de prendre en O(n1*log(n2), le temps.
    Par exemple, si nous avons deux arbres de taille 10 et un autre de taille 1024.
    Ici n1+n2 = 1034 où, comme n1log(n2) = 10*10 = 100.
    Donc, l'approche doit dépendre de la taille des deux arbres.

    • Je veux dire la construction d'un arbre avec une liste triée est de complexité log(n1+n2). Maintenant, la complexité de l'ensemble du problème est O(n1+n2)
    InformationsquelleAutor genthu
  5. 0

    O(n1 * log(n2)) est la moyenne du scénario, même si nous avons 2 fusion toute liste non triée dans un BST. Nous ne sommes pas en utilisant le fait que la liste est triée liste ou un BST.

    Selon moi
    Supposons un BST a n1-éléments et autres a n2 éléments.
    Maintenant convertir un BST dans un Tableau Trié la Liste L1 en O(n1).

    Fusionné BST(BST, Array)

    si (Tableau.taille == 0) return BST
    if(Tableau.taille ==1)
    insérer l'élément dans la BST. retour BST;

    Trouver l'index dans le tableau dont la gauche de l'élément < BST.rootnode et à droite de l'élément >=BST.rootnode dire de l'Index.
    si(BST.rootNode.leftNode ==null ) //je.e Pas de nœud de gauche
    {
    insérer le tableau de l'Index à 0 dans la gauche de la STB et
    }
    d'autre
    {
    Fusionné BST(BST.leftNode, Array{0 Index})
    }

    si(BST.rootNode.rightNode ==null)//je.e Pas le droit de nœud
    {
    insérer le tableau à partir de l'Index de Tableau.taille en droit de la STB
    }
    d'autre
    {
    Fusionné BST(BST.rightNode, Array{Index de Tableau.taille})
    }

    retour BST.

    Cet algorithme va prendre << temps de O(n1 * log(n2)), comme à chaque fois nous sommes partitionnement de la matrice et de la STB pour gérer la subproblem.

    InformationsquelleAutor Manu
  6. -1

    L'idée est d'utiliser itératif afinde traversée. Nous utilisons deux auxiliaires de piles pour les deux techniciennes se chargent. Depuis que nous avons besoin d'imprimer les éléments triés forme, chaque fois que nous obtenons un plus petit élément à partir des arbres, nous l'imprimer. Si l'élément est plus grand, alors nous pousser à revenir à pile pour la prochaine itération.

    • Double itératif afinde traversée pourrait fonctionner, mais ce que vous êtes sur sur ce qui concerne l'impression des éléments? Vous êtes censé retrouver avec un TBS.
    InformationsquelleAutor Soumajyoti