Quelle ' est la différence entre un arbre de recherche binaire et un tas binaire?

Heap garantit simplement que les éléments des niveaux supérieurs sont plus grands (pour max-heap) ou plus petits (pour min-heap) que les éléments des niveaux inférieurs, alors que BST garantit lordre (de « gauche » à « droite ») . Si vous voulez des éléments triés, choisissez BST. par Dante nest pas un geek

Heap est meilleur à findMin / findMax (O ( 1)), alors que BST est bon dans tous les domaines trouvés (O (logN)). Insert est O (logN) pour les deux structures. Si vous ne vous souciez que de findMin / findMax (par exemple lié à la priorité), optez pour le tas. Si vous voulez tout est trié, utilisez BST.

par xysun

Commentaires

• Je pense que BST est meilleur dans findMin & findMax stackoverflow .com / a / 27074221/764592
• Je pense que ce nest quune communication sur une idée fausse. Un arbre binaire peut être facilement modifié pour trouver min et max comme indiqué par Yeo. Il sagit en fait dune restriction du tas: la seule recherche efficace est min ou max. Le véritable avantage du tas est insertion moyenne O (1) comme je lexplique: stackoverflow.com/a/29548834/895245
• Selon cette vidéo , vous pouvez avoir des valeurs plus élevées à un niveau inférieur, à condition que la plus grande ne descende pas de la plus basse.
• Le tas est trié de la racine à la feuille et BST est trié de gauche à droite.
• Et si je veux trouver la médiane en temps constant et supprimer la médiane en temps logarithmique? quelle structure de données dois-je choisir? la mise en œuvre de MinHeap fonctionnera-t-elle? Veuillez suggérer.

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 de ce tableau sont les mêmes que leurs pires moments sauf pour Insertion.

• *: partout dans cette réponse, BST == Balanced BST, puisque déséquilibré aspire asymptotiquement
• **: en utilisant une modification triviale expliquée dans cette réponse
• ***: log(n) pour le tas de larborescence du pointeur, n pour le tas de tableaux dynamiques

Avantages du tas binaire sur un BST

• Le temps moyen dinsertion dans un tas binaire est O(1), pour BST est O(log(n)). Cette est la fonctionnalité qui tue les tas.

  Il existe également dautres tas qui atteignent O(1) amorti (plus fort) comme le Fibonacci Heap , et même le pire des cas, comme le Brodal queue , même si elles peuvent ne pas être pratiques en raison de performances non asymptotiques: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• Les tas binaires peuvent être efficacement implémentés au-dessus des tableaux dynamiques ou des arbres basés sur des pointeurs, BST uniquement des arbres basés sur des pointeurs. Donc, pour le tas, nous pouvons choisir limplémentation de tableau la plus économe en espace, si nous pouvons nous permettre des latences de redimensionnement occasionnelles.

• création de tas binaire est le O(n) le pire des cas , O(n log(n)) pour BST.

Lavantage du BST par rapport au tas binaire

• la recherche déléments arbitraires est O(log(n)). Cette est la fonctionnalité qui tue des BST.

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

« Faux » avantage du tas sur BST

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

  Ceci est une idée fausse courante, car il est trivial de modifier un BST pour garder une trace du plus grand élément, et de le mettre à jour chaque fois que cet élément pourrait être modifié: lors de linsertion dun plus grand swap, lors de la suppression, trouvez le deuxième plus grand. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (mentionné par Yeo ).

  En fait, il sagit dune limitation de tas par rapport aux BST: la seule recherche efficace est celle du plus grand élément.

Linsertion moyenne du tas binaire est O(1)

Sources:

• Papier: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Diapositives WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Argument intuitif:

• les niveaux inférieurs de larborescence ont exponentiellement plus déléments que les niveaux supérieurs, donc les nouveaux éléments sont presque certains daller en bas
• insertion de tas commence par le bas , BST doit commencer par le haut

Dans un tas binaire, augmenter la valeur à un index donné est aussi O(1) pour la même raison. Mais si vous voulez faire cela, il est probable que vous souhaitiez garder un index supplémentaire à jour sur les opérations de tas https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu par exemple pour Dijkstra. Possible sans frais de temps supplémentaire.

Benchmark dinsertion de bibliothèque standard C ++ GCC sur du matériel réel

Jai évalué le C ++ std::set ( Arbre rouge-noir BST ) et std::priority_queue ( tas de tableau dynamique ) pour voir si javais raison sur les temps dinsertion, et voici ce que jai obtenu:

• code de référence
• script de tracé
• données de tracé
• testé sur Ubuntu 19.04, GCC 8.3.0 dans un ordinateur portable Lenovo ThinkPad P51 avec CPU: CPU Intel Core i7-7820HQ (4 cœurs / 8 threads , 2,90 GHz de base, 8 Mo de mémoire cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 Go, 3.000 Mo / s)

Donc clairement:

• insert de tas t ime est fondamentalement constant.

  Nous pouvons clairement voir les points de redimensionnement des tableaux dynamiques. Étant donné que nous calculons en moyenne tous les 10 000 inserts pour pouvoir voir quoi que ce soit au-dessus du bruit du système , ces pics sont en fait environ 10 000 fois plus grands que ceux indiqués!

  Le graphique agrandi exclut essentiellement uniquement les points de redimensionnement du tableau, et montre que presque toutes les insertions sont inférieures à 25 nanosecondes.

• BST est logarithmique. Toutes les insertions sont beaucoup plus lentes que linsertion moyenne du tas.

• Analyse détaillée BST vs hashmap à: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

Benchmark dinsertion de bibliothèque standard C ++ GCC sur gem5

gem5 est un simulateur de système complet, et fournit donc une horloge infiniment précise avec avec m5 dumpstats. Jai donc essayé de lutiliser pour estimer les horaires des insertions individuelles.

Interprétation:

• le tas est toujours constant, mais maintenant nous voyons plus en détail quil y a quelques lignes, et chaque ligne supérieure est plus clairsemée .

  Cela doit correspondre aux latences d’accès à la mémoire qui sont faites pour des insertions de plus en plus élevées.

• TODO Je ne peux pas vraiment interpréter le BST complètement comme il ne semble pas si logarithmique et un peu plus constant.

  Avec ce plus de détails, cependant, nous pouvons voir que nous pouvons également voir quelques lignes distinctes, mais je ne suis pas sûr de ce quelles représentent: je mattendrais à ce que la ligne du bas être plus mince, puisque nous insérons du haut en bas?

Benchmarké avec cette configuration Buildroot sur un aarch64 HPI CPU .

BST ne peut pas être efficacement implémenté sur un tableau

Tas les opérations nont besoin que de remonter ou de descendre une seule branche darbre, donc O(log(n)) swaps dans le pire des cas, O(1) en moyenne.

Garder un BST équilibré nécessite des rotations darbres, ce qui peut changer lélément supérieur pour un autre, et nécessiterait de déplacer tout le tableau autour (O(n)).

Les tas peuvent être efficacement implémentés sur un tableau

Les index parents et enfants peuvent être calculés à partir de lindex actuel comme indiqué ici .

Il ny a pas dopérations déquilibrage comme BST.

Supprimer min est lopération la plus inquiétante car elle doit être descendante. Mais cela peut toujours être fait en « percolant » une seule branche du tas comme expliqué ici . Cela conduit au pire des cas O (log (n)), car le tas est toujours bien équilibré.

Si vous insérez un seul nœud pour chacun que vous supprimez, alors vous perdez lavantage de lasymptotique O (1) insert moyen que les tas fournissent car la suppression dominerait, et vous pourriez aussi bien utiliser un BST. Dijkstra met cependant à jour les nœuds plusieurs fois pour chaque suppression, donc tout va bien.

Les tas de tableaux dynamiques et les tas darbres de pointeurs

Les tas peuvent être mis en œuvre efficacement au-dessus des tas de pointeurs: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Limplémentation du tableau dynamique est plus efficace en termes despace. Supposons que chaque élément du tas contienne juste un pointeur vers un struct:

• limplémentation de larborescence doit stocker trois pointeurs pour chaque élément: parent, enfant gauche et enfant droit. Ainsi, lutilisation de la mémoire est toujours 4n (3 pointeurs darbre + 1 pointeur struct).

  Les BST darbre seraient également besoin dinformations supplémentaires sur léquilibrage, par ex black-red-ness.

• limplémentation du tableau dynamique peut être de taille 2n juste après un doublement. Donc, en moyenne, ce sera 1.5n.

Dun autre côté, le tas darbre a une meilleure insertion dans le pire des cas, parce que copier le tableau dynamique de sauvegarde pour doubler sa taille prend O(n) le pire des cas, alors que le tas de larborescence ne fait que de nouvelles petites allocations pour chaque nœud.

Pourtant, le support le doublement du tableau est O(1) amorti, donc il revient à une considération de latence maximale. Mentionné ici .

Philosophie

• Les BST conservent une propriété globale entre un parent et tous les descendants (plus petit à gauche, plus grand à droite).

  Le nœud supérieur dun BST est lélément du milieu , ce qui nécessite une connaissance globale pour être maintenue (savoir combien il y a déléments plus petits et plus grands).

  Cette propriété globale est plus coûteuse à maintenir (log n insert), mais donne des recherches plus puissantes (log n search) .

• Les tas conservent une propriété locale entre les parents et les enfants directs (parents> enfants).

  La note supérieure dun tas est le gros élément, qui ne nécessite que des connaissances locales à maintenir (connaître ses parents).

Comparaison de BST vs Heap vs Hashmap:

• BST: peut être soit un raisonnable:

  • ensemble non ordonné (une structure qui détermine si un élément a déjà été inséré ou non). Mais hashmap a tendance à être meilleur en raison de linsert amorti O (1).
  • machine de tri. Mais le tas est généralement meilleur à cela, cest pourquoi heapsort est beaucoup plus connu que tri darbre

• tas: est juste une machine de tri. Il ne peut pas sagir dun ensemble non ordonné efficace, car vous ne pouvez rechercher que lélément le plus petit / le plus grand rapidement.

• carte de hachage: ne peut être quun ensemble non ordonné, pas une machine de tri efficace, parce que le hachage confond nimporte quel ordre.

Liste à double lien

Une liste doublement liée peut être considérée comme un sous-ensemble du tas où le premier élément a la plus grande priorité, alors comparons-les ici aussi:

• insertion:
  • position:
    • liste doublement liée: lélément inséré doit être le premier ou le dernier, car nous navons que des pointeurs vers ces éléments.
    • tas binaire: lélément inséré peut se retrouver dans nimporte quelle position. Moins restrictif que la liste liée.
  • heure:
    • liste doublement liée: O(1) pire des cas puisque nous avons des pointeurs vers les éléments, et que la mise à jour est vraiment simple
    • tas binaire: O(1) moyen, donc pire que la liste chaînée. Compromis pour ayant une position dinsertion plus générale.
• recherche: O(n) pour les deux

Un cas dutilisation pour cela est lorsque la clé du tas est lhorodatage actuel: dans ce cas, les nouvelles entrées iront toujours au début de la liste. Ainsi, nous pouvons même oublier complètement lhorodatage exact, et simplement garder la position dans la liste comme priorité.

Cela peut être utilisé pour implémenter un cache LRU . Tout comme pour les applications de tas comme Dijkstra , vous voudrez conserver un hashmap supplémentaire de la clé au nœud correspondant de la liste, pour trouver le nœud à mettre à jour rapidement .

Comparaison de différents BST équilibrés

Bien que linsertion asymptotique et trouver les temps pour toutes les structures de données qui sont communément classées comme «BST équilibrées» que jai vues jusquà présent sont les mêmes, différents BBST ont des compromis différents. Je nai pas encore étudié complètement cela, mais il serait bon de résumer ces compromis ici:

• Arbre rouge-noir . Semble être le BBST le plus couramment utilisé à partir de 2019, par ex. cest celui utilisé par limplémentation C ++ de GCC 8.3.0
• arbre AVL . Semble être un peu plus équilibré que BST, il pourrait donc être préférable pour la latence de recherche, au prix de découvertes légèrement plus chères.Le wiki résume: «Les arborescences AVL sont souvent comparées aux arborescences rouge-noir car les deux prennent en charge le même ensemble d’opérations et prennent [le même] temps pour les opérations de base. Pour les applications nécessitant une recherche intensive, les arborescences AVL sont plus rapides que les arbres rouge-noir car ils sont plus strictement équilibrés. Semblables aux arbres rouge-noir, les arbres AVL sont équilibrés en hauteur. Les deux ne sont, en général, ni pondérés ni équilibrés en mu pour les mu < 1 / 2; autrement dit, les nœuds frères peuvent avoir des nombres de descendants extrêmement différents. « 
• WAVL . Le article original mentionne les avantages de cette version en termes de limites sur les opérations de rééquilibrage et de rotation.

Voir aussi

Question similaire sur CS: What ' est la différence entre un arbre de recherche binaire et un tas binaire?

Commentaires

• Excellente réponse . Les applications courantes du tas sont la médiane, k min, les k éléments supérieurs. Pour ces opérations les plus courantes, supprimez min puis insert (généralement nous avons un petit tas avec peu dopérations dinsertion pure). Il semble donc quen pratique, pour ces algorithmes, il ne surpasse pas la BST.
• Réponse exceptionnelle !!! En utilisant deque comme structure de tas sous-jacente, vous pouvez réduire considérablement les temps de redimensionnement, même sil sagit toujours du pire des cas, car il doit réallouer un tableau (plus petit) de pointeurs vers des morceaux.

Les deux arbres de recherche binaires et les tas binaires sont des structures de données arborescentes.

Les tas exigent que les nœuds aient une priorité sur leurs enfants. Dans un tas max, les enfants de chaque nœud doivent être inférieurs à lui-même. Cest le contraire pour un tas min:

Les arbres de recherche binaire (BST) suivent un ordre spécifique (pré-ordre, dans-ordre, post-ordre) parmi les nœuds frères. Larbre doit être trié, contrairement aux tas:

BST a une moyenne de $ O (\ log n) $ pour linsertion, la suppression et la recherche.
Les tas binaires ont une valeur moyenne de $ O (1) $ pour findMin / findMax et $ O (\ log n) $ pour insertion et suppression.

Commentaires

• @FrankW Extraction is $ O (\ log n) $, no?

Avec la structure de données, il faut distinguer les niveaux de préoccupation.

1. Les structures de données abstraites (objets stockés, leurs opérations) dans ce q les questions sont différentes. Lun implémente une file dattente prioritaire, lautre un ensemble. Une file dattente prioritaire nest pas intéressée à trouver un élément arbitraire, seulement celui avec la plus grande priorité.

2. La mise en œuvre concrète des structures. Ici, à première vue, les deux sont des arbres (binaires), avec des propriétés structurelles différentes. Lordre relatif des clés et les structures globales possibles diffèrent. (Un peu imprécis, dans un BST, les clés sont ordonnées de gauche à droite, dans un tas elles sont ordonnées de haut en bas.) Comme IPlant le remarque correctement, un tas doit également être « complet » .

3. Il y a une dernière différence dans la implémentation de bas niveau . Un arbre de recherche binaire (déséquilibré) a une implémentation standard utilisant des pointeurs. Un tas binaire au contraire a une implémentation efficace en utilisant un tableau (précisément à cause de la structure restreinte).

En plus des réponses précédentes, le tas doit avoir la propriété de structure de tas ; larborescence doit être pleine, et la couche la plus basse, qui ne peut pas toujours être pleine, doit être remplie de lextrême gauche à lextrême droite sans espaces.