Tas vs Binaires un Arbre de Recherche (BST)

Quelle est la différence entre un segment et de la BST?

Quand utiliser un tas et quand utiliser un BST?

Si vous voulez obtenir les éléments triés de la mode, est cest mieux au fil du tas?

  • Cette question semble être hors-sujet, car il est sur l'ordinateur de la science et de la devraient être posées sur cs.stackexchange.com
  • il a été demandé il y à: cs.stackexchange.com/questions/27860/...
  • Je me sens comme il se rapporte à la fois de la pile d'échange et de dépassement de pile. Donc, avoir ici est très bien
InformationsquelleAutor kc3 | 2011-05-27
  1. 154

    Résumé

              Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

    Tous les temps moyens sur ce tableau sont les mêmes que leurs pires moments, sauf pour les Insérer.

    • *: partout dans cette réponse, BST == Équilibré de la STB, depuis déséquilibrée suce asymptotiquement
    • **: à l'aide d'un trivial modification expliqué dans cette réponse
    • ***: log(n) de pointeur arbre tas, n pour tableau dynamique tas

    Avantages des tas binaire sur un BST

    Avantage de la BST sur tas binaire

    • de recherche pour arbitraire des éléments est O(log(n)). Ce est la killer feature de techniciennes se chargent.

      Pour les tas, c'est O(n) en général, sauf pour le plus grand élément de qui est O(1).

    "False" l'avantage de tas plus de BST

    • tas est O(1) pour trouver max, BST O(log(n)).

      C'est une idée fausse commune, parce que c'est facile à modifier un BST pour garder une trace de l'élément le plus large et le mettre à jour à chaque fois que cet élément puisse être changé: à l'insertion d'un plus grand échange, sur la suppression de trouver la deuxième plus grande. Peut-on utiliser les binaires de recherche arbres pour simuler des tas de fonctionnement? (mentionné par Yeo).

      En fait, c'est un limitation de segments par rapport à techniciennes se chargent: le seulement l'efficacité de la recherche est que, pour le plus grand élément.

    Moyenne tas binaire insert est O(1)

    Sources:

    L'argument intuitif:

    • bas de l'arbre ont des niveaux de façon exponentielle plus d'éléments que les niveaux les plus élevés, de sorte que de nouveaux éléments sont à peu près certain d'aller au fond
    • tas d'insertion en partant du bas, BST doit commencer par le haut

    Dans un tas binaire, l'augmentation de la valeur à un index donné est également O(1) pour la même raison. Mais si vous voulez le faire, il est probable que vous aurez envie de garder un supplément d'index à jour sur les opérations segment Comment mettre en œuvre O(logn) diminution de la touche de fonctionnement pour min-tas en fonction de la Priorité de la File d'attente? par exemple pour Dijkstra. Possible sans supplément de coût.

    GCC C++ standard library insérer un repère de référence sur le matériel réel

    Je comparés le C++ std::set (Rouge-noir arbre de la STB) et std::priority_queue (tableau dynamique tas) insert pour voir si j'avais raison à propos de l'insérer fois, et c'est ce que j'ai:

    Tas vs Binaires un Arbre de Recherche (BST)

    • référence code
    • parcelle de script
    • parcelle de données
    • testé sur Ubuntu 19.04, GCC 8.3.0 en un Lenovo ThinkPad P51 ordinateur portable avec PROCESSEUR: Intel Core i7-7820HQ CPU (4 coeurs /8 threads, 2.90 GHz de base, 8 MO de cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbit /s), SSD: Samsung MZVLB512HAJQ-000L7 (512 GO, 3 000 MO/s)

    Clairement:

    GCC C++ standard library insérer une référence sur gem5

    gem5 est un système complet simulateur, et fournit donc une infiniment précis de l'horloge avec m5 dumpstats. J'ai donc essayé de l'utiliser pour estimer les horaires pour personne insère.

    Tas vs Binaires un Arbre de Recherche (BST)

    Interprétation:

    • tas est toujours constante, mais nous voyons maintenant plus en détail qu'il y a quelques lignes, et chaque ligne plus importante est plus clairsemée.

      Cela doit correspondre à la mémoire de la latence d'accès sont fait de plus en plus élevés des inserts.

    • TODO je ne peux pas vraiment interpréter le BST pleinement, comme il n'a pas l'air si logarithmique et un peu plus constant.

      Avec cela plus en détail, mais nous pouvons voir pouvez également voir quelques lignes distinctes, mais je ne suis pas sûr de ce qu'ils représentent: je pense à la ligne de fond pour être plus mince, puisque nous insérer en haut en bas?

    Comparés avec ce Le programme d'installation de Buildroot sur un aarch64 HPI CPU.

    BST ne peuvent pas être efficacement mis en œuvre sur un tableau

    Opérations segment seulement besoin de la bulle vers le haut ou vers le bas d'une simple branche d'arbre, de sorte O(log(n)) pire des cas, des swaps, des O(1) moyenne.

    En gardant un BST équilibrée nécessite l'arbre de rotation, ce qui peut modifier le premier élément à un autre, et serait d'exiger le déplacement de l'ensemble de la matrice autour de (O(n)).

    Tas peuvent être efficacement mis en œuvre sur un tableau

    Parent et les enfants indices peuvent être calculés à partir de l'indice actuel comme illustré ici.

    Il n'y a pas d'équilibrage des opérations comme la BST.

    Supprimer min est la plus préoccupante de l'opération, car il doit être de haut en bas. Mais il peut toujours être fait par la "percolation vers le bas" une branche de la tas comme expliqué ici. Cela conduit à un O(log(n)) le pire des cas, puisque le tas est toujours bien équilibré.

    Si vous êtes l'insertion d'un nœud unique pour chacun de vous retirer, vous perdez l'avantage de l'asymptotique O(1) moyenne insérer que des tas de fournir les supprimer dominer, et vous pourriez aussi bien utiliser un BST. Dijkstra cependant mises à jour des nœuds plusieurs fois pour chaque retrait, de sorte que nous sommes bien.

    Tableau dynamique des tas vs pointeur arbre des tas

    Tas peuvent être efficacement mises en œuvre sur le dessus de pointeur tas: Est-il possible de rendre efficace pointeur de base tas binaire implémentations?

    La dynamique de la matrice de mise en œuvre plus efficace de l'espace. Supposons que chaque élément de tas contient un pointeur vers un struct:

    • l'arbre de la mise en œuvre doit stocker trois pointeurs pour chaque élément: parent, à gauche de l'enfant et de droit de l'enfant. Donc, l'utilisation de la mémoire est toujours 4n (3 arbre pointeurs + 1 struct pointeur).

      Arbre techniciennes se chargent aussi besoin de plus d'équilibrer l'information, par exemple noir-rouge-ness.

    • la dynamique de la matrice de mise en œuvre peuvent être de taille 2n juste après un doublement. Donc en moyenne, il va être 1.5n.

    D'autre part, l'arbre tas est mieux pire des cas insert, parce que la copie de la sauvegarde de tableau dynamique à double de sa taille O(n) pire des cas, tandis que l'arbre tas juste fait de nouvelles petites allocations pour chaque nœud.

    Encore, le soutien de la matrice de doublement est O(1) amorti, de sorte qu'il se résume à un maximum de latence considération. Mentionné ici.

    Philosophie

    • Techniciennes se chargent de maintenir une propriété globale entre un parent et tous les descendants (à gauche plus petit, de droite plus).

      Le nœud supérieur de la STB est le milieu de l'élément, ce qui nécessite la connaissance globale de maintenir (sachant combien les petits et les grands éléments sont là).

      Cette propriété est plus cher à l'entretien (log n insert), mais donne plus de moteur de recherche puissant (n log de recherche).

    • Des tas de maintenir une propriété locale entre les parents et les enfants directs (parents > les enfants).

      La note de tête d'un segment est le grand élément, qui ne nécessite que des connaissances locales pour maintenir (en sachant que votre parent).

    Doublement lié liste

    Une liste doublement chaînée peut être vu comme sous-ensemble de la masse, où le premier élément est plus grande priorité, donc, nous allons comparer ici:

    • d'insertion:
      • position:
        • liste doublement chaînée: l'élément inséré doit être soit le premier ou le dernier, car nous n'avons que des pointeurs vers ces éléments.
        • tas binaire: l'élément inséré peuvent se retrouver dans n'importe quelle position. Moins restrictive que la liste liée.
      • temps:
        • liste doublement chaînée: O(1) pire des cas, puisque nous avons des pointeurs vers les objets, et la mise à jour est vraiment simple
        • tas binaire: O(1) moyenne, donc pire que la liste liée. Compromis pour avoir plus générale, en position d'insertion.
    • de recherche: O(n) pour les deux

    Un cas d'utilisation de ce est quand la clé de la tas est le timestamp actuel: dans ce cas, les nouvelles entrées seront toujours d'aller au début de la liste. Donc, on peut même oublier l'horodatage exact tout à fait, et il suffit de garder la position dans la liste, comme la priorité.

    Ceci peut être utilisé pour mettre en œuvre un Cache LRU. Tout comme pour des tas d'applications comme Dijkstra, vous voulez garder un supplément de table de hachage de la clé du nœud correspondant de la liste, pour trouver le nœud de mettre à jour rapidement.

    Voir aussi

    Question similaire sur CS: https://cs.stackexchange.com/questions/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

    • J' +1ed, mais le "papier" de nature à justifier la moyenne O(1) tas binaire de l'insertion est maintenant un lien mort, et les "slides" juste à l'état de la réclamation, sans preuve. Aussi, je pense que cela aiderait à préciser que "moyen" signifie ici la moyenne en supposant que les valeurs insérées viennent de certains de distribution en particulier, donc je ne suis pas sûr de la façon de "tueur" est réellement cette fonctionnalité.
    • BST et équilibrée BST semblent être interchangeables. Il doit être clair que la réponse se réfère à l'équilibre de la STB pour éviter toute confusion.
    • OK, je l'ai fait.
    • Ce à propos de max-extraction? Dans une file d'attente de priorité, nous souhaitons extraire le max ainsi. N'est-ce pas log(n)?
    • pour les deux max et min, il est trivial sur la BST, avec la modification mentionnée, et pour des tas je pense que vous avez juste à garder deux tas triés différemment pour les O(1).
    • Je vais réfléchir davantage sur le BST cas merci. Mais pour le tas, je ne suis pas la compréhension de "garder les deux tas triés". N'est-il pas juste un tas de? Et le tas n'est pas triée?
    • si vous souhaitez à la fois max et min je veux dire. Par triés je veux dire l'inversion de l'insérer fonction de comparaison.
    • Tas n'est pas triée, et c'est sa principale différence à la STB! Au lieu de cela, vous savez que chaque parent est supérieur (ou inférieur) que chez les enfants. Vous pouvez considérer cela comme de la famille à chaque parent est âgé de plus de des enfants, mais il n'y a pas d'autres restrictions. Donc sa garantie qui est la racine la plus ancienne de la famille, mais rien d'autre. Donc, si vous avez besoin de trouver le plus jeune de l'homme dans la famille, vous avez besoin de numériser l'ensemble du tas. Ou, alternativement, de maintenir le deuxième segment avec l'autre opérateur de comparaison, c'est à dire un segment de mémoire où chaque parent > les enfants, et un autre segment où chaque parent < enfants.
    • J'ai l'impression que nous sommes s'égarer un peu, mais si nous voulons à la fois max et min dans le même temps, nous pourrions rencontrer des problèmes avec le maintien de deux tas si nous ne faisons pas attention - stackoverflow.com/a/1098454/7154924. Il est probablement préférable d'utiliser un max-min tas (en raison de Atkinson et coll.), qui est spécialement conçu à cet effet.
    • Ce qui se passe quand supprimer les min / max élément? Dans le tas, on peut le trouver en O(1) mais nous aurons à l'équilibre en O(n). Lequel est le mieux ici?
    • non, tas de supprimer est O(log(n)). J'ai édité la réponse, revue de la suppression de l'algorithme. Mais ce serait un problème si vous faites un supprimer par insertion, vous pourriez aussi bien utiliser de la STB dans ce cas.
    • Merci de mettre à jour le lien sur la moyenne-la complexité de l'affaire. Rapidement, l'écrémage, il semble qu'ils traitent de 2 types différents: une distribution aléatoire uniforme sur le tas, et la distribution, sur le tas résultant de segment de mémoire-insérer les éléments d'un uniformément distribués de façon aléatoire permutation de 1, ..., n. Il est intéressant de noter, celles-ci s'avèrent être tout à fait différentes distributions!
    • si vous n'avez aller plus dans les détails, éventuellement de modifier directement dans "la Moyenne des tas binaire insert" ou ajouter une nouvelle réponse, par exemple, nous pouvons également citer quelque chose de plus précis sur l'article ou l'ajout de plein de preuve. Nous pouvons également étendre l'expérience graphique pour montrer les différences de comportement dans la pratique.
    • Je le ferai si j'ai du temps, mais probablement pas en ce moment...
    • Je ne comprends pas pourquoi l'opération de suppression d'un tas binaire est O(log n). Cela ne fonctionne que si vous avez un pointeur vers l'élément dans le tas, mais dans la plupart des cas d'utilisation, vous avez la clé et vous avez besoin de trouver l'élément premier qui prend O(n).
    • oui, supprimer sur le Tas se réfère uniquement à la racine de suppression qui est un peu trompeur, car il est sur la même ligne que celle de la STB. D'autre part, on peut considérer que la suppression de quelque chose implique de trouver en premier lieu, et que le coût de la recherche est calculée séparément de la suppression des coûts.
    • tas d'insertion est log(n) non o(1)
    • Il est o1 moyenne selon mes recherches et expériences
    • intéressant. pouvez-vous partager vos expériences et de ses résultats?
    • voir les graphiques dans la réponse à la section "GCC C++ standard library insérer un repère de référence sur le matériel réel". Laissez-moi savoir si vous trouvez quelque chose de mal avec mes méthodes 🙂

    InformationsquelleAutor Ciro Santilli 新疆改造中心996ICU六四事件
  2. 71

    Tas juste garantit que les éléments sur les niveaux les plus élevés sont plus (pour max-heap) ou plus petite (pour min-tas) que des éléments sur les niveaux inférieurs, tandis que la BST, les garanties de commande (de "gauche" et "droite"). Si vous voulez éléments triés, aller avec BST.

    • "Tas juste garantit que les éléments sur les niveaux les plus élevés sont plus (pour max-heap) ou plus petite (pour min-tas) que des éléments sur les niveaux inférieurs, ..." – sur le tas ne pas appliquer cette par niveau, mais seulement dans les cours parent–enfant-chaînes. [1, 5, 9, 7, 15, 10, 11] représente un valide min-segment, mais le 7 sur le niveau 3 est plus petit que 9 sur le niveau 2. Pour une visualisation, voir, par exemple, la 25 et 19 éléments dans l'exemple de Wikipédia image pour les segments. (Notez aussi que l'inégalité des relations entre les éléments ne sont pas strictes, puisque les éléments ne sont pas nécessairement uniques.)
    • je pense que cette réponse est beaucoup mieux : stackoverflow.com/a/29548834/2873507
    • Désolé pour le retard mais je veux juste obtenir de la clarté. Si le Tas Binaire est trié, puis pire des cas pour la recherche serait log n droit. Donc, dans ce cas, sont triés Binaire drôlement mieux que les Arbres Binaires(Rouge-Noir BST). Merci
    InformationsquelleAutor Dante May Code
  3. 47

    Quand utiliser un tas et quand utiliser un BST

    Tas est mieux à findMin/findMax (O(1)), tandis que le BST est bon à tous trouve (O(logN)). Insérer est O(logN) pour les deux structures. Si vous ne se soucient findMin/findMax (par exemple, la priorité en matière d', aller avec le tas. Si vous voulez tout trié, aller avec BST.

    D'abord quelques diapositives à partir de ici expliquer les choses très clairement.

    • Tout en insertion est logarithmique pour les deux, dans le pire des cas, la moyenne des tas insérer prend à temps constant. (Puisque la plupart des éléments existants sont sur le fond, dans la plupart des cas, un élément nouveau n'aura qu'à remonter jusqu'à un ou deux niveaux, le cas échéant.)
    • Je pense que la BST est de mieux en findMin & findMax stackoverflow.com/a/27074221/764592
    • Tas est mieux pour findMin xor findMax. Si vous avez besoin d' deux, puis BST est mieux.
    • Je pense que c'est juste une idée fausse commune. Un arbre binaire peut être facilement modifié pour trouver min et max comme indiqué par Yeo. C'est en fait un restriction de le tas: le que efficace de trouver des est min ou max. Le vrai avantage du tas est O(1) moyenne insert comme je l'explique: stackoverflow.com/a/29548834/895245
    • Utiliser un tas si vous prévoyez beaucoup de suppressions parce que cela peut déséquilibrer la hauteur de l'arbre à devenir √N au lieu de ln N, Aussi, si vos données ne sont pas ordonnés aléatoirement
    • Ciro Santilli la réponse est beaucoup mieux : stackoverflow.com/a/29548834/2873507

    InformationsquelleAutor xysun
  4. 7

    Comme mentionné par d'autres, Tas peut faire findMin ou findMax en O(1) mais pas les deux dans la même structure de données. Cependant je suis en désaccord que le Segment est de mieux en findMin/findMax. En fait, avec une légère modification, le BST peut faire les deux findMin et findMax en O(1).

    Dans cette modification de la STB, de garder une trace de la la min nœud et max nœud à chaque fois que vous effectuez une opération qui peut potentiellement modifier la structure de données. Par exemple, dans l'opération d'insertion, vous pouvez vérifier si la valeur min est plus grande que la nouvelle valeur insérée, puis affectez-lui la valeur min du nœud nouvellement ajouté. La même technique peut être appliquée sur la valeur de max. Par conséquent, cette BST contenir ces informations que vous pouvez les récupérer en O(1). (de même que le tas binaire)

    Dans ce BST (Équilibré BST), lorsque vous pop min ou pop max, la prochaine valeur min pour être affecté est le successeur de la min nœud, tandis que la prochaine valeur max d'être affecté est le prédécesseur de max nœud. Ainsi, il effectue en O(1). Cependant, nous avons besoin de ré-équilibrer l'arbre, donc il va encore s'exécuter en O(log n). (de même que le tas binaire)

    Je serais intéressé à entendre vos pensées dans les commentaires ci-dessous. Merci 🙂

    Mise à jour

    Renvoi à la question similaire Peut-on utiliser les binaires de recherche arbres pour simuler des tas de fonctionnement? pour plus de discussion sur la simulation Tas à l'aide de la STB.

    • Pourquoi êtes-vous en désaccord? pourriez-vous partager votre pensée ci-dessous?
    • Vous pourriez certainement stocker le maximum et/ou minimum de la valeur d'un BST, mais alors qu'advient-il si vous voulez de la pop? Vous avez à la recherche de l'arbre de l'enlever, puis de rechercher à nouveau pour le nouveau max/min, qui sont tous deux O(log n) opérations. C'est le même ordre que les insertions et les suppressions en priorité tas, avec une aggravation de la constante.
    • Désolé, j'ai oublié de l'indiquer dans ma réponse. Dans la STB, lorsque vous faites de la pop min, la prochaine valeur min pour être affecté est le successeur de la min nœud. et si vous sautez le max, la prochaine valeur max d'être affecté est le prédécesseur de la max nœud. Ainsi, il continue à effectuer en O(1).
    • Je corrige la position des mains.
    • Correction: pour popMin ou popMax il n'est pas O(1), mais il est O(log n), car il a bien l'Équilibre de la STB qui ont besoin d'être rééquilibrer chaque opération de suppression. Donc il le même que tas binaire popMin ou popMax qui exécuter en O(log n)
    • Vous pouvez obtenir le premier min/max, mais l'obtention de kth min/max allait revenir à la normale BST complexité.

    InformationsquelleAutor Yeo
  5. 3

    Un arbre de recherche binaire utilise la définition: pour chaque nœud,le nœud de la gauche, a une moindre valeur(key) et le nœud à la droite de celui-ci a une plus grande valeur(key).

    Où, comme le tas,en cours de mise en œuvre d'un arbre binaire utilise la définition suivante:

    Si A et B sont des nœuds, où B est l'enfant du nœud A,puis la valeur(key) de l'Un doit être supérieure ou égale à la valeur(key) de B. C'est,
    clé(Un) ≥ touche(B).

    http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

    J'ai couru dans la même question aujourd'hui pour mon examen et je l'ai eu droit. sourire ... 🙂

    • "en tas, en cours de mise en œuvre de l'arbre binaire" - tout en soulignant qu'un tas est un genre d'arbre binaire, pas une sorte de BST
    InformationsquelleAutor Yevgraf Andreyevich Zhivago
  6. 3

    Une autre utilisation de la BST sur Tas; en raison d'une différence importante :

    • trouver de successeur et prédécesseur dans un BST va prendre O(h) temps. ( O(logn) en équilibre BST)
    • tandis que dans le Tas, prendrait O(n) le temps de trouver un successeur ou le prédécesseur de certains éléments.

    Utilisation de la BST sur un Tas: Maintenant, disons que nous utilisons une structure de données pour stocker l'heure du débarquement des vols. Nous ne pouvons pas planifier un vol à la terre en cas de différence dans l'atterrissage temps est inférieur à "d". Et d'assumer de nombreux vols ont été programmés à la terre dans une structure de données(BST ou d'un Segment).

    Maintenant, nous voulons organiser un autre Vol qui va atterrir à t. Par conséquent, nous avons besoin de calculer la différence de t avec son successeur et prédécesseur (qui devrait être >d).
    Ainsi, nous avons besoin d'un BST pour cela, qui est-il rapide c'est à dire en O(logn) si équilibré.

    Édité:

    Tri BST prend O(n) le temps d'imprimer les éléments dans l'ordre de tri (Afinde traversal), tandis que le Segment peut le faire en O(n logn) de temps.
    Tas d'extraits min élément et re-heapifies le tableau, qui lui fait faire le tri en O(n logn) temps.

    • Oui. C'est à partir de non triés à la séquence triée. O(n) pour afinde de la traversée d'un BST, ce qui donne la séquence triée. Alors que dans le Tas, vous extrait min élément, puis re-heapify en O(log n) fois. DONC, il faudra du temps O(n logn) pour en extraire les n éléments. Et il vous laisse avec une séquence triée.
    • from unsorted to sorted sequence. O(n) time for inorder traversal of a BST, which gives sorted sequence. Bien, à partir de séquence non triée à la BST, je ne sais pas une méthode basée sur la comparaison clé avec moins de O(n logn) le temps, qui domine la BST à la séquence de la partie. (Alors qu'il n'y est O(n) segment de la construction.). Je considérerais-il juste (si inutile) à l'état de tas en étant à proximité de unsortedness et techniciennes se chargent du tri.
    • Ce que j'essaie d'expliquer ici est que si vous avez un BST et aussi un Tas de n éléments => ensuite, tous les éléments peuvent être imprimés dans l'ordre de tri à partir de deux structures de données et BST pouvez le faire en O(n) temps (Afinde traversal), tandis que le Tas pourrait prendre en O(n logn) de temps. Je ne comprends pas ce que vous essayez de dire ici. Comment voulez-vous dire BST va vous donner séquence triée en O(n logn).
    • Je pense que vous êtes également en compte le temps de construire un BST et un Tas. Mais je suppose que vous l'avez déjà fait, que vous avez le construire au fil du temps et maintenant, vous voulez obtenir le résultat trié. Je ne reçois pas votre point de vue?
    • Édité... j'espère que vous êtes satisfait aujourd'hui ;p et de donner un +1 s'il est correct.
    InformationsquelleAutor CODError
  7. 1

    Insérer tous les n éléments d'un tableau à la STB prend O(n logn). n elemnts dans un tableau peut être inséré à un segment de mémoire en O(n) fois. Ce qui donne tas un avantage certain

    InformationsquelleAutor AMR
  8. 0

    Tas juste garantit que les éléments sur les niveaux les plus élevés sont plus (pour max-heap) ou plus petite (pour min-tas) que des éléments sur les niveaux inférieurs

    J'adore la réponse ci-dessus et de mettre mon commentaire juste plus spécifiques à mon besoin et de l'utilisation. J'ai eu pour obtenir le n liste des emplacements trouver la distance à partir de chaque emplacement de point spécifique dire (0,0) et de revenir à l'a m emplacements ayant la plus petite distance. J'ai utilisé de la File d'attente de Priorité qui est Tas.
    Pour trouver les distances et les mettre dans le tas, il m'a fallu n(log(n)) n-emplacements log(n) chaque insertion.
    Ensuite, pour obtenir m avec les distances les plus courtes il a fallu m(log(n)) m-emplacements log(n) des suppressions d'accumulation.

    Si je l'aurais à faire avec la STB, ça m'aurait pris n(n) le pire des cas de l'insertion.(Disons que la première valeur est très petite et tous les autres vient de façon séquentielle de plus en plus longtemps et l'arbre s'étend au droit de l'enfant seul ou à gauche de l'enfant en cas de plus en plus petits. Le min aurait pris O(1) fois, mais j'ai à nouveau l'équilibre.
    Donc, à partir de ma situation et toutes les réponses ci-dessus, ce que j'ai, c'est quand vous êtes seulement après les valeurs min ou max priorité aller pour tas.

    InformationsquelleAutor Sahib Khan