Avant de connaître les différences entre l'arbre de recherche binaire et l'arbre AVL, nous devons connaître séparément l'arbre de recherche binaire et l'arbre AVL.
Qu’est-ce qu’un arbre de recherche binaire ?
Le arbre de recherche binaire est un arbre arbre binaire. Comme nous le savons, cet arbre peut avoir un nombre n d'enfants, alors que ; l'arbre binaire peut contenir au maximum deux enfants. Ainsi, la contrainte d’un arbre binaire est également suivie par l’arbre de recherche binaire. Chaque nœud d'un arbre de recherche binaire doit avoir au maximum deux enfants ; en d’autres termes, on peut dire que l’arbre de recherche binaire est une variante de l’arbre binaire.
L'arbre de recherche binaire suit également les propriétés de la recherche binaire. En recherche binaire, tous les éléments d’un tableau doivent être triés. Nous calculons l'élément du milieu dans la recherche binaire dans laquelle la partie gauche de l'élément du milieu contient la valeur inférieure à la valeur du milieu et la partie droite de l'élément du milieu contient les valeurs supérieures à la valeur du milieu.
Dans l'arbre de recherche binaire, l'élément du milieu devient le nœud racine, la partie droite devient le sous-arbre droit et la partie gauche devient le sous-arbre gauche. Par conséquent, nous pouvons dire que l’arbre de recherche binaire est une combinaison d’un arbre binaire et recherche binaire .
Remarque : L'arbre de recherche binaire peut être défini comme l'arbre binaire dans lequel tous les éléments du sous-arbre gauche sont inférieurs au nœud racine et tous les éléments du sous-arbre droit sont supérieurs au nœud racine.
Complexité temporelle dans l'arbre de recherche binaire
Si l’arbre de recherche binaire est presque un arbre équilibré alors toutes les opérations auront une complexité temporelle de O (connexion) car la recherche est divisée soit vers le sous-arbre gauche, soit vers le sous-arbre droit.
définir Java
Si l'arbre de recherche binaire est asymétrique à gauche ou à droite, alors toutes les opérations auront la complexité temporelle de Sur) parce que nous devons parcourir jusqu'aux n éléments.
Qu’est-ce que l’arbre AVL ?
Un Arbre AVL est un arbre de recherche binaire auto-équilibré dans lequel la différence entre les hauteurs des sous-arbres gauche et droit ne peut pas être supérieure à un. Cette différence est connue sous le nom de facteur d’équilibre. Dans l'arborescence AVL, les valeurs du facteur d'équilibre peuvent être -1, 0 ou 1.
Comment se produit l’auto-équilibrage de l’arbre de recherche binaire ?
Comme nous le savons, l'arbre AVL est un arbre de recherche binaire auto-équilibré. Si l'arbre de recherche binaire n'est pas équilibré, il peut être auto-équilibré avec quelques réarrangements. Ces réarrangements peuvent être effectués à l'aide de quelques rotations.
Comprenons l'auto-équilibrage à travers un exemple.
Supposons que nous voulions insérer 10, 20, 30 dans un arbre AVL.
Voici les manières d'insérer 10, 20, 30 dans une arborescence AVL :
Étape 1: Tout d’abord, nous créons un arbre de recherche binaire, comme indiqué ci-dessous :
Étape 2: Dans la figure ci-dessus, nous pouvons observer que l'arbre est déséquilibré car le facteur d'équilibre du nœud 30 est de 2. Afin d'en faire un arbre AVL, nous devons effectuer quelques rotations. Si nous effectuons la rotation à droite sur le nœud 20 alors le nœud 30 se déplacera vers le bas, tandis que le nœud 20 se déplacera vers le haut, comme indiqué ci-dessous :
Comme nous pouvons l'observer, l'arbre final suit la propriété de l'arbre de recherche binaire et d'un arbre équilibré ; il s’agit donc d’un arbre AVL.
chaîne de format Java
Dans le cas présent, l'arbre était arbre déséquilibré gauche, on effectue donc la bonne rotation sur le nœud.
Étape 1: Nous créons d’abord un arbre de recherche binaire comme indiqué ci-dessous :
Étape 2: Dans la figure ci-dessus, nous pouvons observer que l'arbre est déséquilibré car le facteur d'équilibre du nœud 10 est de -2. Afin d’en faire un arbre AVL, nous devons effectuer quelques rotations. Il s’agit d’un arbre déséquilibré à droite, nous effectuerons donc une rotation à gauche. Si nous effectuons une rotation à gauche sur le nœud 20, alors le nœud 20 se déplacera vers le haut et le nœud 10 se déplacera vers le bas, comme indiqué ci-dessous :
Comme on peut le constater, l’arbre final suit la propriété du Arbre de recherche binaire et un arbre équilibré ; il s’agit donc d’un arbre AVL.
Étape 1: Nous créons d’abord l’arborescence de recherche binaire comme indiqué ci-dessous :
Étape 2: Dans la figure ci-dessus, nous pouvons observer que l'arbre est déséquilibré car le facteur d'équilibre du nœud racine est de 2. Afin d'en faire un arbre AVL, nous devons effectuer quelques rotations. Le scénario ci-dessus est déséquilibré gauche-droite car un nœud est à gauche de son nœud parent et un autre est à droite de son nœud parent. Tout d’abord, nous effectuerons la rotation à gauche, et la rotation se produit entre les nœuds 10 et 20. Après la rotation à gauche, 20 se déplacera vers le haut et 10 se déplacera vers le bas, comme indiqué ci-dessous :
comment transformer une chaîne en entier
Pourtant, l’arbre est déséquilibré, nous effectuons donc la bonne rotation sur l’arbre. Une fois la bonne rotation effectuée sur l'arbre, alors l'arbre souhaite, comme indiqué ci-dessous :
Comme nous pouvons l'observer dans l'arbre ci-dessus, l'arbre suit la propriété de l'arbre de recherche binaire et d'un arbre équilibré ; il s’agit donc d’un arbre AVL.
Étape 1: Tout d’abord, nous créons l’arborescence de recherche binaire, comme indiqué ci-dessous :
Étape 2: Dans la figure ci-dessus, nous pouvons observer que l'arbre est déséquilibré car le facteur d'équilibre du nœud racine est de 2. Afin d'en faire un arbre AVL, nous devons effectuer quelques rotations. Le scénario ci-dessus est déséquilibré droite-gauche car un nœud est à droite de son nœud parent et un autre nœud est à gauche de son nœud parent. Tout d’abord, nous effectuerons la rotation à droite qui se produit entre les nœuds 30 et 20. Après la rotation à droite, 20 se déplacera vers le haut et 30 vers le bas, comme indiqué ci-dessous :
Néanmoins, l'arborescence ci-dessus est déséquilibrée, nous devons donc effectuer une rotation à gauche sur le nœud. Une fois la rotation vers la gauche effectuée, le nœud 20 se déplacera vers le haut et le nœud 10 se déplacera vers le bas comme indiqué ci-dessous :
Comme nous pouvons l'observer dans l'arbre ci-dessus, l'arbre suit la propriété de l'arbre de recherche binaire et d'un arbre équilibré ; il s’agit donc d’un arbre AVL.
Différences entre l'arborescence de recherche binaire et l'arborescence AVL
| Arbre de recherche binaire | Arbre AVL |
|---|---|
| Chaque arbre de recherche binaire est un arbre binaire car les deux arbres contiennent au maximum deux enfants. | Chaque arbre AVL est également un arbre binaire car l'arbre AVL a également au maximum deux enfants. |
| Dans BST, il n’existe aucun terme tel que facteur d’équilibre. | Dans l'arborescence AVL, chaque nœud contient un facteur d'équilibre et la valeur du facteur d'équilibre doit être -1, 0 ou 1. |
| Chaque arbre de recherche binaire n'est pas un arbre AVL car BST peut être un arbre équilibré ou déséquilibré. | Chaque arbre AVL est un arbre de recherche binaire car l'arbre AVL suit la propriété du BST. |
| Chaque nœud de l'arborescence de recherche binaire se compose de trois champs, à savoir le sous-arbre gauche, la valeur du nœud et le sous-arbre droit. | Chaque nœud de l'arborescence AVL se compose de quatre champs, à savoir le sous-arbre gauche, la valeur du nœud, le sous-arbre droit et le facteur d'équilibre. |
| Dans le cas de l'arbre de recherche binaire, si nous voulons insérer un nœud dans l'arborescence, nous comparons la valeur du nœud avec la valeur racine ; si la valeur du nœud est supérieure à la valeur du nœud racine, alors le nœud est inséré dans le sous-arbre droit, sinon le nœud est inséré dans le sous-arbre gauche. Une fois le nœud inséré, il n’est pas nécessaire de vérifier le facteur d’équilibre en hauteur pour que l’insertion soit terminée. | Dans le cas de l’arborescence AVL, nous trouverons d’abord l’endroit approprié pour insérer le nœud. Une fois le nœud inséré, nous calculerons le facteur d’équilibre de chaque nœud. Si le facteur d'équilibre de chaque nœud est satisfait, l'insertion est terminée. Si le facteur d’équilibre est supérieur à 1, nous devons alors effectuer quelques rotations pour équilibrer l’arbre. |
| Dans l'arborescence de recherche binaire, la hauteur ou la profondeur de l'arborescence est O(n), où n est le nombre de nœuds dans l'arborescence de recherche binaire. | Dans l’arborescence AVL, la hauteur ou la profondeur de l’arborescence est O(logn). |
| C'est simple à mettre en œuvre car nous devons suivre les propriétés de recherche binaire pour insérer le nœud. | C'est complexe à mettre en œuvre car dans l'arborescence AVL, nous devons d'abord construire l'arborescence AVL, puis vérifier l'équilibre des hauteurs. Si la hauteur est déséquilibrée, nous devons effectuer quelques rotations pour équilibrer l'arbre. |
| BST n'est pas un arbre équilibré car il ne suit pas le concept de facteur d'équilibre. | L'arbre AVL est un arbre équilibré en hauteur car il suit le concept du facteur d'équilibre. |
| La recherche est inefficace dans BST lorsqu'il y a un grand nombre de nœuds disponibles dans l'arborescence car la hauteur n'est pas équilibrée. | La recherche est efficace dans l'arborescence AVL même lorsqu'il y a un grand nombre de nœuds dans l'arborescence car la hauteur est équilibrée. |