TechCodeview

Avant de comprendre le Arbre rouge-noir et arbre AVL différences, nous devrions connaître séparément l’arbre Rouge-Noir et l’arbre AVL.

Qu'est-ce qu'un arbre rouge-noir ?

L'arbre rouge-noir est un arbre auto-équilibré arbre de recherche binaire dans lequel chaque nœud contient un bit d'information supplémentaire qui indique la couleur du nœud. La couleur du nœud peut être rouge ou noire, en fonction des informations binaires stockées par le nœud.

Propriétés

Voici les propriétés associées à un arbre Rouge-Noir :

• Le nœud racine de l’arbre doit être noir.
• Un nœud rouge ne peut avoir que des enfants noirs. Ou bien, nous pouvons dire que deux nœuds adjacents ne peuvent pas être de couleur rouge.
• Si le nœud n’a pas d’enfant gauche ou droit, alors ce nœud est dit être un nœud feuille. Nous plaçons donc les enfants gauche et droit sous le nœud feuille appelé néant

La profondeur du noir ou la hauteur du noir d'un nœud feuille peut être définie comme le nombre de noir que nous rencontrons lorsque nous passons du nœud feuille au nœud racine. L’une des propriétés clés de l’arbre Rouge-Noir est que chaque nœud feuille doit avoir la même profondeur de noir.

Comprenons cette propriété à travers un exemple.

Dans l’arborescence ci-dessus, il y a cinq nœuds, dont l’un est rouge et les quatre autres nœuds sont noirs. Il y a trois nœuds feuilles dans l’arborescence ci-dessus. Nous calculons maintenant la profondeur du noir de chaque nœud feuille. Comme nous pouvons observer que la profondeur du noir des trois nœuds feuilles est de 2 ; c'est donc un arbre rouge-noir.

Si l’arbre n’obéit à aucune des trois propriétés ci-dessus, alors ce n’est pas un arbre Rouge-Noir.

Hauteur d'un arbre rouge-noir

Considérons h comme la hauteur de l’arbre à n nœuds. Quelle serait la plus petite valeur de n ?. La valeur de n est la plus petite lorsque tous les nœuds sont noirs. Si l’arbre contient tous les nœuds noirs, alors l’arbre serait un arbre binaire complet. Si la hauteur d’un arbre binaire complet est h, alors le nombre de nœuds dans un arbre est :

n = 2h -1

Quelle serait la plus grande valeur de n ?

j'essaie d'entrer

La valeur de n est la plus grande lorsque chaque nœud noir a deux enfants rouges, mais le nœud rouge ne peut pas avoir d’enfants rouges, il aura donc des enfants noirs. De cette façon, il y a des couches alternées d’enfants noirs et rouges. Ainsi, si le nombre de couches noires est h, alors le nombre de couches rouges est également h ; la hauteur totale de l'arbre devient donc 2h. Le nombre total de nœuds est :

n = 2*2h-1

Qu'est-ce que l'arbre AVL ?

Un Arbre AVL est un arbre de recherche binaire auto-équilibré si l'on observe le cas ci-dessous, qui est un arbre de recherche binaire et un arbre équilibré.

Dans l’arbre ci-dessus, la complexité temporelle dans le pire des cas pour rechercher un élément est O(h), c’est-à-dire la hauteur de l’arbre. Dans le cas ci-dessus, le nombre de comparaisons effectuées pour rechercher 17 éléments est de 4, et la hauteur de l'arbre est également de 4.

Si l’on considère l’arbre binaire asymétrique, comme indiqué ci-dessous :

Dans l'arbre asymétrique de droite ci-dessus, le nombre de comparaisons effectuées pour rechercher 17 éléments est de 5, et le nombre d'éléments présents dans l'arbre est également de 5. Par conséquent, nous pouvons dire que si l'arbre est un arbre binaire asymétrique, alors la complexité temporelle serait O(n).

Maintenant, nous devons équilibrer ces arbres asymétriques pour qu’ils aient la complexité temporelle O(h). Il existe un terme connu sous le nom de facteur d'équilibre , qui est utilisé pour auto-équilibrer l'arbre de recherche binaire. Le facteur d’équilibre peut être calculé comme suit :

La valeur du facteur d'équilibre peut être 1, 0 ou -1. Si chaque nœud de l’arbre binaire a une valeur de 1, 0 ou -1, alors cet arbre est dit équilibré. arbre binaire ou arbre AVL.

L'arbre est appelé arbre parfaitement équilibré si le facteur d'équilibre de chaque nœud est de 0. L'arbre AVL est un arbre presque équilibré car chaque nœud de l'arbre a la valeur du facteur d'équilibre soit 1, 0 ou -1.

Différences entre l'arbre Rouge-Noir et l'arbre AVL.

Voici les différences entre l’arborescence Rouge-Noir et l’arborescence AVL :

Arbre de recherche binaire

L'arbre Rouge-Noir est un arbre de recherche binaire, et l'arbre AVL est également un arbre de recherche binaire.

Règles

Les règles suivantes sont appliquées dans un arbre rouge-noir :

1. Le nœud d'un arbre rouge-noir est de couleur rouge ou noire.
2. La couleur du nœud racine doit être noire.
3. Les nœuds adjacents ne doivent pas être rouges. En d’autres termes, nous pouvons dire que le nœud rouge ne peut pas avoir d’enfants rouges, mais que le nœud noir peut avoir des enfants noirs.
4. Il devrait y avoir le même nombre de nœuds noirs dans chaque chemin ; alors, seul un arbre peut être considéré comme un arbre Rouge-Noir.
5. Les nœuds externes sont les nœuds nuls, qui sont toujours de couleur noire.

Règle de l'arbre AVL :

Chaque nœud doit avoir un facteur d'équilibre de -1, 0 ou 1.

Exemple

Dans la figure ci-dessus, nous devons vérifier si l’arbre est un arbre rouge-noir ou non. Afin de vérifier cela, nous devons d’abord vérifier si l’arbre est un arbre de recherche binaire ou non. Comme nous pouvons le constater dans la figure ci-dessus, il satisfait toutes les propriétés de l'arbre de recherche binaire ; il s'agit donc d'un arbre de recherche binaire. Deuxièmement, nous devons vérifier s’il satisfait ou non aux règles susmentionnées. L'arbre ci-dessus satisfait aux cinq règles ci-dessus ; par conséquent, il conclut que l’arbre ci-dessus est un arbre rouge-noir.

Dans la figure ci-dessus, nous devons vérifier si l'arbre est un arbre AVL ou non. Comme chaque nœud a une valeur de facteur d'équilibre égale à -1, 0 ou 1, il s'agit donc d'un arbre AVL.

Comment l’arbre peut-il être considéré ou non comme un arbre équilibré ?

Dans le cas d'un arbre Rouge-Noir, si toutes les règles ci-dessus sont satisfaites, à condition qu'un arbre soit un arbre de recherche binaire, alors l'arbre est dit un arbre Rouge-noir.

Dans le cas de l'arbre AVL, si le facteur d'équilibre est -1, 0 ou 1, alors l'arbre ci-dessus est dit être un arbre AVL.

Outils utilisés pour l'équilibrage

Si l'arbre n'est pas équilibré, alors deux outils sont utilisés pour équilibrer l'arbre dans un arbre Rouge-Noir :

Recoloration Rotation

Si l'arborescence n'est pas équilibrée, un outil est utilisé pour équilibrer l'arborescence dans l'arborescence AVL :

Rotation

Efficace pour quelle opération

Dans le cas de l'arbre Rouge-Noir, les opérations d'insertion et de suppression sont efficaces. Si l'arbre s'équilibre grâce à la recoloration, alors les opérations d'insertion et de suppression sont efficaces dans l'arbre Rouge-Noir.

Dans le cas de l’arborescence AVL, l’opération de recherche est efficace car elle ne nécessite qu’un seul outil pour équilibrer l’arborescence.

Complexité temporelle

Dans le cas de l'arborescence Rouge-Noir, la complexité temporelle de toutes les opérations, c'est-à-dire l'insertion, la suppression et la recherche, est O(logn).

Dans le cas de l'arborescence AVL, la complexité temporelle de toutes les opérations, c'est-à-dire l'insertion, la suppression et la recherche, est O (logn).

Nick Pulos éclair noir

Comprenons les différences sous forme tabulaire.