Un arbre binaire équilibré est également connu sous le nom d’arbre équilibré en hauteur. Il est défini comme un arbre binaire lorsque la différence entre la hauteur du sous-arbre gauche et du sous-arbre droit n'est pas supérieure à m, où m est généralement égal à 1. La hauteur d'un arbre est le nombre d'arêtes sur le chemin le plus long entre le le nœud racine et le nœud feuille.
L'arbre ci-dessus est un arbre de recherche binaire . Un arbre de recherche binaire est un arbre dans lequel chaque nœud du côté gauche a une valeur inférieure à celle de son nœud parent et le nœud du côté droit a une valeur supérieure à son nœud parent. Dans l’arborescence ci-dessus, n1 est un nœud racine et n4, n6, n7 sont les nœuds feuilles. Le nœud n7 est le nœud le plus éloigné du nœud racine. Les n4 et n6 contiennent 2 arêtes et il existe trois arêtes entre le nœud racine et le nœud n7. Puisque n7 est le plus éloigné du nœud racine ; par conséquent, la hauteur de l’arbre ci-dessus est de 3.
carte dactylographiée
Nous allons maintenant voir si l'arbre ci-dessus est équilibré ou non. Le sous-arbre de gauche contient les nœuds n2, n4, n5 et n7, tandis que le sous-arbre de droite contient les nœuds n3 et n6. Le sous-arbre de gauche a deux nœuds feuilles, c'est-à-dire n4 et n7. Il n'y a qu'une seule arête entre les nœuds n2 et n4 et deux arêtes entre les nœuds n7 et n2 ; par conséquent, le nœud n7 est le plus éloigné du nœud racine. La hauteur du sous-arbre de gauche est 2. Le sous-arbre de droite ne contient qu'un seul nœud feuille, c'est-à-dire n6, et n'a qu'une seule arête ; par conséquent, la hauteur du sous-arbre droit est 1. La différence entre les hauteurs du sous-arbre gauche et du sous-arbre droit est 1. Puisque nous avons obtenu la valeur 1, nous pouvons donc dire que l'arbre ci-dessus est un arbre équilibré en hauteur. Ce processus de calcul de la différence entre les hauteurs doit être effectué pour chaque nœud comme n2, n3, n4, n5, n6 et n7. Lorsque nous traitons chaque nœud, nous constaterons que la valeur de k n'est pas supérieure à 1, nous pouvons donc dire que l'arbre ci-dessus est un arbre équilibré. arbre binaire .
Dans l'arborescence ci-dessus, n6, n4 et n3 sont les nœuds feuilles, où n6 est le nœud le plus éloigné du nœud racine. Trois arêtes existent entre le nœud racine et le nœud feuille ; par conséquent, la hauteur de l'arbre ci-dessus est de 3. Lorsque nous considérons n1 comme nœud racine, alors le sous-arbre de gauche contient les nœuds n2, n4, n5 et n6, tandis que le sous-arbre contient le nœud n3. Dans le sous-arbre de gauche, n2 est un nœud racine et n4 et n6 sont des nœuds feuilles. Parmi les nœuds n4 et n6, n6 est le nœud le plus éloigné de son nœud racine et n6 a deux arêtes ; par conséquent, la hauteur du sous-arbre gauche est 2. Le sous-arbre droit a des enfants à sa gauche et à sa droite ; par conséquent, la hauteur du sous-arbre droit est 0. Puisque la hauteur du sous-arbre gauche est 2 et que le sous-arbre droit est 0, donc la différence entre la hauteur du sous-arbre gauche et du sous-arbre droit est 2. Selon la définition, la différence entre la hauteur du sous-arbre gauche et du sous-arbre droit ne doit pas être supérieure à 1. Dans ce cas, la différence est de 2, ce qui est supérieur à 1 ; par conséquent, l’arbre binaire ci-dessus est un arbre de recherche binaire déséquilibré.
Pourquoi avons-nous besoin d’un arbre binaire équilibré ?
Comprenons la nécessité d'un arbre binaire équilibré à travers un exemple.
L'arbre ci-dessus est un arbre de recherche binaire car tous les nœuds du sous-arbre gauche sont plus petits que son nœud parent et tous les nœuds du sous-arbre droit sont supérieurs à son nœud parent. Supposons que nous voulions trouver la valeur 79 dans l’arborescence ci-dessus. Tout d’abord, nous comparons la valeur du nœud n1 avec 79 ; puisque la valeur de 79 n'est pas égale à 35 et qu'elle est supérieure à 35 donc on passe au nœud n3, soit 48. Puisque la valeur 79 n'est pas égale à 48 et que 79 est supérieur à 48, on se déplace donc vers la droite enfant de 48. La valeur de l'enfant droit du nœud 48 est 79 qui est égale à la valeur à rechercher. Le nombre de sauts requis pour rechercher un élément 79 est de 2 et le nombre maximum de sauts requis pour rechercher un élément est de 2. Le cas moyen pour rechercher un élément est O (logn).
L'arbre ci-dessus est également un arbre de recherche binaire car tous les nœuds du sous-arbre de gauche sont plus petits que son nœud parent et tous les nœuds du sous-arbre de droite sont supérieurs à son nœud parent. Supposons que nous voulions trouver la valeur 79 dans l’arborescence ci-dessus. Tout d’abord, nous comparons la valeur 79 avec un nœud n4, c’est-à-dire 13. Puisque la valeur 79 est supérieure à 13, nous passons donc au bon enfant du nœud 13, c’est-à-dire n2 (21). La valeur du nœud n2 est 21, ce qui est inférieur à 79, nous nous déplaçons donc à nouveau vers la droite du nœud 21. La valeur de l'enfant droit du nœud 21 est 29. Puisque la valeur 79 est supérieure à 29, nous nous déplaçons donc vers la droite. enfant du nœud 29. La valeur de l'enfant droit du nœud 29 est 35, ce qui est inférieur à 79, nous passons donc à l'enfant droit du nœud 35, soit 48. La valeur 79 est supérieure à 48, nous passons donc à l'enfant droit. du nœud 48. La valeur du nœud enfant droit de 48 est 79, ce qui est égal à la valeur à rechercher. Dans ce cas, le nombre de sauts requis pour rechercher un élément est de 5. Dans ce cas, le pire des cas est O(n).
outil de guérison
Si le nombre de nœuds augmente, la formule utilisée dans l’arborescence1 est plus efficace que la formule utilisée dans l’arborescence2. Supposons que le nombre de nœuds disponibles dans les deux arbres ci-dessus soit de 100 000. Pour rechercher n'importe quel élément dans un diagramme arborescent2, le temps nécessaire est de 100 000 µs alors que le temps nécessaire pour rechercher un élément dans un diagramme arborescent est de log(100 000), ce qui est égal à 16,6 µs. Nous pouvons observer l'énorme différence de temps entre deux arbres. Par conséquent, nous concluons que l’arbre binaire équilibré permet une recherche plus rapide que la structure de données arborescente linéaire.