Tas binaire et arbre de recherche binaire en C++

En programmation C++, le tas binaire et l'arbre de recherche binaire sont deux structures de données couramment utilisées. Elles présentent des similitudes, mais elles présentent également des différences. Cet article présentera respectivement les concepts, les opérations de base et les scénarios d'application des tas binaires et des arbres de recherche binaires.

1. Tas binaire

1.1 Concept

Un tas binaire est un arbre binaire complet qui satisfait les deux propriétés suivantes :

1.1.1 Ordre des tas

L'ordre des tas signifie que dans un tas binaire, chacun La valeur de chacun Le nœud n’est pas supérieur (ni inférieur) à la valeur de son nœud parent. Ici, nous prenons le tas maximum comme exemple, c'est-à-dire que la valeur du nœud racine est la plus grande valeur de tout l'arborescence et que les valeurs de tous les nœuds enfants sont inférieures ou égales à la valeur du nœud racine.

1.1.2 Propriétés complètes de l'arbre binaire

À l'exception de la couche la plus basse, toutes les autres couches doivent être remplies et tous les nœuds doivent être alignés à gauche.

Ici, le tableau suivant est utilisé pour représenter un tas maximum :

[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]

Le tas correspondant est comme indiqué ci-dessous :

16

/
14 10
/ /
8 7 9 3
/
2 4

1

1.2 Opérations de base

1.2.1 Opération d'insertion

Insérer un nouvel élément dans un tas binaire, en utilisant " Ajuster par " passer au crible " :

• Insérez le nouvel élément dans l'espace vide le plus à gauche en bas du tas ;
• Comparez le nouvel élément avec son nœud parent, si la valeur du nouvel élément est supérieure à celle de son nœud parent, puis échangez le positions des deux, et répétez ce processus jusqu'à ce que le nouvel élément ne soit plus plus grand que son nœud parent ou atteigne le sommet du tas.

1.2.2 Opération de suppression

L'opération de suppression de l'élément supérieur du tas dans un tas binaire est ajustée en utilisant la méthode "sift down":

• L'élément supérieur du tas et l'élément le plus à droite au niveau le bas du tas est ajusté Échange d'éléments ;
• Supprimez l'élément supérieur d'origine du tas ;
• Comparez le nouvel élément supérieur du tas avec ses nœuds enfants couche par couche si sa valeur est inférieure à la valeur maximale dans l'enfant. nœud, comparez-le avec la valeur maximale du nœud enfant. Les valeurs sont échangées et ce processus est répété jusqu'à ce que l'ordre du tas soit satisfait.

1.3 Scénarios d'application

Le tas binaire est souvent utilisé pour implémenter des files d'attente prioritaires et des algorithmes de tri basés sur le tas, tels que le tri par tas, le problème topK, etc.

2. Arbre de recherche binaire

2.1 Concept

L'arbre de recherche binaire (BST) est un arbre ordonné qui satisfait aux propriétés suivantes :

2.1.1 Les valeurs de tous les nœuds du sous-arbre de gauche sont égales et inférieures à la valeur de son nœud racine.

2.1.2 Les valeurs de tous les nœuds du sous-arbre droit sont supérieures à la valeur de son nœud racine.

2.1.3 Les sous-arbres gauche et droit sont également respectivement des arbres de recherche binaires.

Prenons l'exemple de l'arbre suivant :

    6
  /   
 2     7

/
1 4 9

   /    /
  3   5 8

Alors c'est un arbre de recherche binaire.

2.2 Opérations de base

2.2.1 Opération de recherche

L'opération de recherche d'un nœud dans un arbre de recherche binaire L'essence est de comparer en permanence la taille de la valeur du nœud à trouver avec la valeur actuelle du nœud et d'avancer. la recherche récursive du sous-arbre gauche/droite.

2.2.2 Opération d'insertion

L'opération d'insertion d'un nouveau nœud dans un arbre de recherche binaire nécessite une comparaison en partant du nœud racine et en trouvant la position où il doit être inséré. Après l'insertion, les propriétés de l'arbre de recherche binaire doivent. se satisfaire.

2.2.3 Opération de suppression

L'opération de suppression d'un nœud dans l'arbre de recherche binaire peut être divisée en trois situations :

• Le nœud à supprimer est un nœud feuille, il suffit de le supprimer directement
• Il n'y a que ; un nœud à supprimer
• Lorsque le nœud à supprimer a deux nœuds enfants, remplacez le nœud par le plus petit nœud du sous-arbre droit du nœud, et supprimez le plus petit nœud du sous-arbre droit du nœud.

2.3 Scénarios d'application

Les arbres de recherche binaires sont souvent utilisés pour mettre en œuvre des scénarios avec des opérations de recherche et d'insertion tels que des dictionnaires et des tables de symboles. Les performances de recherche sont liées à la distribution des données.

3. Comparaison des tas binaires et des arbres de recherche binaires

3.1 Similitudes

Les tas binaires et les arbres de recherche binaires sont tous deux des arbres binaires et ont certaines des mêmes propriétés :

• La position initiale du nœud racine peut être C'est n'importe quel nœud ;
• peut être utilisé pour implémenter une file d'attente prioritaire ;
• La complexité temporelle de l'insertion et de la suppression est O(logn).

3.2 Différences

Il existe également des différences évidentes entre les tas binaires et les arbres de recherche binaires :

3.2.1 Distribution des données

Dans un tas binaire, les éléments sont répartis entre les nœuds sans aucune régularité. Dans , c'est seulement nécessaire pour garantir que chaque nœud satisfait à l'ordre du tas ; dans un arbre de recherche binaire, la taille des éléments a une règle de tri spécifique, c'est-à-dire qu'elle satisfait la propriété de petite gauche et de grande droite.

3.2.2 Accès aux valeurs minimales/maximales

Dans un tas binaire, la valeur maximale/minimale est accessible en temps O(1), c'est-à-dire qu'elle est obtenue dans le nœud racine, mais la complexité temporelle d'accès aux autres elements est O(logn) ; dans un arbre de recherche binaire, trouver la valeur minimale/maximale nécessite de parcourir le sous-arbre, et la complexité temporelle est également O(logn).

3.2.3 Opérations de suppression et d'insertion

Dans un tas binaire, chaque opération de suppression et d'insertion doit suivre l'ordre du tas, c'est-à-dire la complexité temporelle de O(logn) dans un arbre de recherche binaire, trouver une complexité temporelle ; de nœuds et l'insertion d'un nouveau nœud est liée à la hauteur de l'arborescence, donc dans le pire des cas, cela peut nécessiter une complexité temporelle O(n).

3.3 Suggestions de sélection

Lors du choix d'un tas binaire et d'un arbre de recherche binaire, vous devez choisir en fonction des conditions spécifiques du scénario d'application.

Si vous avez besoin d'obtenir rapidement la valeur minimum/maximum et que vous n'avez pas d'exigence particulière sur la taille des éléments, vous pouvez donner la priorité au tas binaire.

Si vous devez insérer/supprimer des éléments rapidement et que les tailles des éléments doivent être triées dans un certain ordre, vous pouvez envisager de choisir un arbre de recherche binaire.

IV. Conclusion

En résumé, les tas binaires et les arbres de recherche binaires sont tous deux des structures de données importantes et ont leurs propres avantages et inconvénients dans différents scénarios. Comprendre les concepts, les opérations de base et les scénarios d'application des tas binaires et des arbres de recherche binaires est d'une grande importance pour l'écriture de programmes efficaces.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!