Arborescence vs recherche binary (BST)

Quelle est la différence entre un tas et BST?

Quand utiliser un tas et quand utiliser un BST?

Si vous voulez obtenir les éléments de manière sortingée, est-ce que BST est plus performant que le tas?

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 cette table sont les mêmes que leurs pires moments, sauf pour l’insertion.

  • * : partout dans cette réponse, BST == BST équilibré, car déséquilibré suce asymptotiquement
  • ** : en utilisant une modification sortingviale expliquée dans cette réponse
  • *** : log(n) pour l’arborescence du pointeur, n pour le tas du tableau dynamic

Avantages du tas binary sur un BST

  • l’insertion de temps moyen dans un tas binary est O(1) , pour BST est O(log(n)) . Ceci est la caractéristique de tueur de tas.

    Il y a aussi d’autres tas qui atteignent O(1) amorti (plus fort) comme le tas de Fibonacci , et même pire, comme la queue Brodal , bien qu’ils ne soient pas pratiques en raison de performances non asymptotiques. en pratique n’importe où?

  • Les segments binarys peuvent être efficacement mis en œuvre sur des tableaux dynamics ou des arbres basés sur des pointeurs, des arbres basés uniquement sur des pointeurs BST. Donc, pour le tas, nous pouvons choisir une implémentation de tableaux plus efficace si nous pouvons nous permettre des latences de redimensionnement occasionnelles.

  • la création de tas binary est O(n) pire cas , O(n log(n)) pour BST.

Avantage de BST sur le tas binary

  • la recherche d’éléments arbitraires est O(log(n)) . Ceci est la caractéristique de tueur de BST.

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

“Faux” avantage de tas sur BST

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

    Ceci est une idée fausse commune, car il est sortingvial de modifier un BST pour garder la trace du plus grand élément, et de le mettre à jour chaque fois que cet élément pourrait être modifié: Peut-on utiliser l’arbre de recherche binary pour simuler une opération de tas? (mentionné par Yeo ).

    En fait, il s’agit d’une limitation des tas par rapport aux BST: la seule recherche efficace est celle du plus grand élément.

L’insertion de stack binary moyenne est O(1)

Sources:

Argument intuitif:

  • les niveaux inférieurs des arbres ont exponentiellement plus d’éléments que les niveaux supérieurs, de sorte que les nouveaux éléments sont presque certainement au bas de l’échelle
  • insertion de tas commence par le bas , BST doit commencer par le haut

Dans un tas binary, augmenter la valeur à un index donné est également 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 segment de mémoire. Comment implémenter l’opération de clé réduite O (logn) pour les files de priorité min-heap? par exemple pour Dijkstra. Possible sans coût supplémentaire.

Critère d’insertion de bibliothèque standard GCC C ++

J’ai comparé l’insertion de std::set ( Red-black tree BST ) et std::priority_queue ( tas de tableau dynamic ) avec ce code et ce script pour voir si j’avais raison sur les temps d’insertion, et c’est ce que j’ai eu :

entrer la description de l'image ici

Donc clairement:

  • le temps d’insertion de tas est essentiellement constant.

    Nous pouvons clairement voir les points de redimensionnement du tableau dynamic. Comme nous faisons la moyenne de chaque insertion de 10k pour pouvoir voir quoi que ce soit au-dessus du bruit du système , ces pics sont en fait environ 10k fois plus grands que ceux affichés!

    Le graphique agrandi exclut essentiellement uniquement les points de redimensionnement du tableau, et montre que presque toutes les insertions tombent en dessous de 25 nanosecondes.

  • BST est logarithmique. Toutes les insertions sont beaucoup plus lentes que l’insertion de tas moyenne.

Ubuntu 18.04, GCC 7.3, processeur Intel i7-7820HQ, RAM DDR4 2400 MHz, Lenovo Thinkpad P51.

gem5 insert benchmark

Etant donné que je connais bien gem5 , j’ai essayé d’obtenir un peu plus de détails sur chaque insert individuel avec les m5 dumpstats :

entrer la description de l'image ici

Interprétation:

  • heap est toujours constant, mais maintenant nous voyons plus en détail qu’il y a quelques lignes, et chaque ligne supérieure est plus clairsemée.

    Cela doit correspondre aux latences d’access à la mémoire pour les insertions de plus en plus hautes.

  • TODO Je ne peux pas vraiment interpréter complètement le BST car il n’a pas l’air si logarithmique et un peu plus constant.

    Avec ce plus grand détail, cependant, nous pouvons voir quelques lignes distinctes, mais je ne suis pas sûr de ce qu’elles représentent: je pense que la ligne de fond sera plus mince, puisque nous insérons le haut en bas?

Benchmarké avec cette installation Buildroot sur un processeur HPA aarch64.

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

Les opérations de tas ne doivent que remonter ou descendre dans une seule twig d’arbre, de sorte que O(log(n)) écarte le pire des cas, O(1) moyen.

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

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

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

Il n’y a pas d’opérations d’équilibrage comme BST.

Supprimer min est l’opération la plus inquiétante car elle doit être top down. Mais cela peut toujours être fait en “percolant” une seule twig du tas comme expliqué ici . Cela conduit à un pire O (log (n)), puisque le tas est toujours bien équilibré.

Si vous insérez un seul nœud pour chacun des fichiers que vous supprimez, vous perdez l’avantage de l’insert moyen asymptotique O (1) 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 nous allons bien.

Tas de tableau dynamic vs tas d’arbres de pointeur

Les tas peuvent être efficacement mis en œuvre au-dessus des tas de pointeurs: est-il possible de réaliser des implémentations de tas binarys efficaces basées sur des pointeurs?

L’implémentation de tableau dynamic est plus efficace en termes d’espace. Supposons que chaque élément de segment ne contienne qu’un pointeur sur une struct :

  • L’implémentation de l’arborescence doit stocker trois pointeurs pour chaque élément: parent, enfant gauche et enfant droit. Donc, l’utilisation de la mémoire est toujours 4n (3 pointeurs d’arbre + 1 pointeur de struct ).

    Les BST d’arbres nécessiteraient également des informations d’équilibrage supplémentaires, par exemple le noir et blanc.

  • la mise en œuvre du tableau dynamic peut être de taille 2n juste après un doublement. Donc, en moyenne, il sera 1.5n .

D’un autre côté, le tas d’arborescence contient le pire des cas, car copier le tableau dynamic de backing pour doubler sa taille prend le pire des cas, alors que le tas d’arbre ne fait que de petites allocations pour chaque nœud.

Cependant, le doublage de la masortingce de support est amorti en O(1) , ce qui revient à une considération de latence maximale. Mentionné ici .

Philosophie

  • Les BST maintiennent une propriété globale entre un parent et tous ses descendants (plus petit, plus grand).

    Le nœud supérieur d’un fichier BST est l’élément central, ce qui nécessite une connaissance globale à gérer (en sachant combien d’éléments plus petits et plus grands sont présents).

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

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

    La note supérieure d’un tas est le gros élément, qui ne nécessite que des connaissances locales à maintenir (connaître votre parent).

Liste doublement liée

Une liste à double lien peut être vue 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 n’avons que des pointeurs vers ces éléments.
      • tas binary: l’élément inséré peut se retrouver dans n’importe quelle position. Moins ressortingctif que la liste liée.
    • temps:
      • liste doublement liée: O(1) pire cas puisque nous avons des pointeurs vers les éléments, et la mise à jour est vraiment simple
      • tas binary: O(1) moyenne, donc pire que la liste chaînée. Compromis pour avoir une position d’insertion plus générale.
  • recherche: O(n) pour les deux

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

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

Voir également

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

Heap garantit simplement que les éléments des niveaux supérieurs sont plus grands (pour max-heap) ou plus petits (pour les min-heap) que les éléments des niveaux inférieurs, tandis que BST garantit l’ordre (de “gauche” à “droit”). Si vous voulez des éléments sortingés, allez avec BST.

Quand utiliser un tas et quand utiliser un BST

Heap est meilleur à findMin / findMax ( O(1) ), tandis que BST est bon à toutes les recherches ( O(logN) ). L’insertion est O(logN) pour les deux structures. Si vous ne vous souciez que de findMin / findMax (par exemple, lié à la priorité), allez avec heap. Si vous voulez tout sortingé, allez avec BST.

Les premières diapositives d’ ici expliquent les choses très clairement.

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

Dans ce fichier BST modifié, vous gardez une trace des nœuds min et max chaque fois que vous effectuez une opération susceptible de modifier la structure des données. Par exemple, dans l’opération d’insertion, vous pouvez vérifier si la valeur min est supérieure à la nouvelle valeur insérée, puis atsortingbuez la valeur min au nouveau noeud ajouté. La même technique peut être appliquée à la valeur maximale. Par conséquent, cette BST contient ces informations que vous pouvez les récupérer dans O (1). (identique au tas binary)

Dans ce BST (Balanced BST), lorsque vous pop min ou pop max , la valeur minimale suivante à affecter est le successeur du nœud min, tandis que la valeur maximale suivante à affecter est le prédécesseur du nœud max. Ainsi, il effectue dans O (1). Cependant, nous devons ré-équilibrer l’arbre, donc il lancera toujours O (log n). (identique au tas binary)

Je serais intéressé d’entendre votre pensée dans le commentaire ci-dessous. Merci 🙂

Mettre à jour

Renvoi à une question similaire Peut-on utiliser l’arbre de recherche binary pour simuler une opération de tas? pour plus de discussion sur la simulation de tas en utilisant BST.

Un arbre de recherche binary utilise la définition: pour chaque nœud, le nœud situé à gauche a une valeur inférieure (clé) et le nœud situé à droite a une valeur supérieure (clé).

Où, en tant que segment, être une implémentation d’un arbre binary utilise la définition suivante:

Si A et B sont des nœuds, où B est le nœud enfant de A, alors la valeur (clé) de A doit être supérieure ou égale à la valeur (clé) de B. C’est la clé (A) ≥ clé (B ).

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

J’ai couru la même question aujourd’hui pour mon examen et j’ai bien compris. sourire … 🙂

Une autre utilisation de BST sur Heap; à cause d’une différence importante:

  • trouver le successeur et le prédécesseur dans un BST prendra O (h) le temps. (O (logn) dans BST équilibré)
  • dans Heap, prendrait O (n) le temps de trouver le successeur ou le prédécesseur d’un élément.

Utilisation de la BST sur un tas : Disons que nous utilisons une structure de données pour stocker l’heure d’arrivée des vols. Nous ne pouvons pas planifier un vol pour atterrir si la différence de temps d’atterrissage est inférieure à «d». Et supposons que de nombreux vols ont été programmés pour atterrir dans une structure de données (BST ou Heap).

Maintenant, nous voulons programmer un autre vol qui atterrira à t . Par conséquent, nous devons calculer la différence de t avec son successeur et son prédécesseur (devrait être> d). Ainsi, nous aurons besoin d’un BST pour cela, qui le fait rapidement, c’est- à- dire dans O (logn) s’il est équilibré.

Édité:

Le sorting de BST prend O (n) temps pour imprimer des éléments dans l’ordre sortingé (traversée de commande), alors que Heap peut le faire en temps O (n logn). Heap extrait min element et re-tasifie le tableau, ce qui lui permet d’effectuer le sorting en temps O (n logn).

Insérez tous les n éléments d’un tableau dans les sockets BST O (n logn). n elemnts dans un tableau peuvent être insérés dans un tas en temps O (n). Ce qui donne un avantage certain au tas

Heap garantit simplement que les éléments des niveaux supérieurs sont plus grands (pour max-heap) ou plus petits (pour les min-heap) que les éléments des niveaux inférieurs

J’aime la réponse ci-dessus et mettre mon commentaire juste plus spécifique à mes besoins et à mon utilisation. Je devais obtenir la liste des n emplacements trouver la distance de chaque emplacement à un point spécifique dire (0,0) et puis retourner les emplacements am ayant une distance plus petite. J’ai utilisé la queue prioritaire qui est Heap. Pour trouver des distances et mettre en tas, il m’a fallu n (log (n)) n-emplacements log (n) à chaque insertion. Ensuite, pour obtenir m avec les plus courtes distances, il a fallu m (log (n)) m-emplacements log (n) suppressions de tas.

Je serais obligé de le faire avec BST, cela m’aurait pris n (n) insertion dans le pire des cas. (Supposons que la première valeur est très petite et que toutes les autres soient de plus en plus longues et que l’arbre couvre uniquement dans le cas de plus en plus petit, le min aurait pris O (1) mais je devais à nouveau équilibrer.Alors de ma situation et de toutes les réponses ci-dessus, ce que j’ai est quand vous êtes seulement après les valeurs à la priorité min ou max go pour le tas.