Les arbres évasés sont des arbres de recherche binaires auto-équilibrés ou auto-ajustés. En d’autres termes, on peut dire que les arbres évasés sont les variantes des arbres de recherche binaires. La condition préalable aux arbres évasés que nous devrions connaître sur les arbres de recherche binaires.
Comme nous le savons déjà, la complexité temporelle d'un arbre de recherche binaire dans tous les cas. La complexité temporelle d'un arbre de recherche binaire dans le cas moyen est O (connexion) et la complexité temporelle dans le pire des cas est O(n). Dans un arbre de recherche binaire, la valeur du sous-arbre gauche est inférieure à celle du nœud racine et la valeur du sous-arbre droit est supérieure à celle du nœud racine ; dans ce cas, la complexité temporelle serait O (connexion) . Si l’arbre binaire est asymétrique à gauche ou à droite, alors la complexité temporelle serait O(n). Pour limiter l'asymétrie, le AVL et arbre Rouge-Noir est entré en scène, ayant O (connexion ) complexité temporelle pour toutes les opérations dans tous les cas. Nous pouvons également améliorer cette complexité temporelle en effectuant des implémentations plus pratiques, comme le nouveau Tree Qu'est-ce qu'un Splay Tree ?
Un arbre évasé est un arbre auto-équilibré, mais Les arbres AVL et Rouge-Noir sont donc également des arbres auto-équilibrés. Ce qui rend l'arbre évasé unique, c'est deux arbres. Il possède une propriété supplémentaire qui le rend unique : l’évasement.
Un arbre évasé contient les mêmes opérations qu'un Arbre de recherche binaire , c'est-à-dire l'insertion, la suppression et la recherche, mais il contient également une opération supplémentaire, à savoir l'évasement. Donc. toutes les opérations dans l'arbre d'évasement sont suivies d'un évasement.
Les arbres évasés ne sont pas des arbres strictement équilibrés, mais ce sont des arbres à peu près équilibrés. Comprenons l'opération de recherche dans le splay-tree.
Supposons que nous souhaitions rechercher 7 éléments dans l'arborescence, illustrée ci-dessous :
Pour rechercher n’importe quel élément dans l’arbre splay, nous effectuerons d’abord l’opération d’arbre de recherche binaire standard. Comme 7 est inférieur à 10 nous viendrons donc à gauche du nœud racine. Après avoir effectué l'opération de recherche, nous devons effectuer un évasement. Ici, l'évasement signifie que l'opération que nous effectuons sur n'importe quel élément doit devenir le nœud racine après avoir effectué quelques réarrangements. Le réarrangement de l'arbre se fera au fil des rotations.
Remarque : L'arbre évasé peut être défini comme l'arbre auto-ajusté dans lequel toute opération effectuée sur l'élément réorganiserait l'arbre de sorte que l'élément sur lequel l'opération a été effectuée devienne le nœud racine de l'arbre.
Rotations
Il existe six types de rotations utilisées pour l'évasement :
- Rotation zig (rotation à droite)
- Rotation Zag (Rotation à gauche)
- Zigzag (Zig suivi de zag)
- Zag zig (Zag suivi de zig)
- Zig zig (deux rotations à droite)
- Zag zag (deux rotations à gauche)
Facteurs requis pour sélectionner un type de rotation
Voici les facteurs utilisés pour sélectionner un type de rotation :
- Le nœud que nous essayons de faire pivoter a-t-il un grand-parent ?
- Le nœud est-il l'enfant gauche ou droit du parent ?
- Le nœud est-il l'enfant gauche ou droit du grand-parent ?
Cas pour les rotations
Cas 1: Si le nœud n'a pas de grand-parent, et s'il est l'enfant droit du parent, alors on effectue la rotation vers la gauche ; sinon, la bonne rotation est effectuée.
Cas 2 : Si le nœud a un grand-parent, alors en fonction des scénarios suivants : la rotation s'effectuerait :
Scénario 1: Si le nœud est à droite du parent et que le parent est également à droite de son parent, alors zig zig droite rotation à droite est effectuée.
Scénario 2 : Si le nœud est à gauche d'un parent, mais que le parent est à droite de son parent, alors zigzag rotation droite gauche est effectuée.
Scénario 3 : Si le nœud est à droite du parent et que le parent est à droite de son parent, alors zig zig gauche rotation gauche est effectuée.
Scénario 4 : Si le nœud est à droite d'un parent, mais que le parent est à gauche de son parent, alors zigzag rotation droite-gauche est effectuée.
Maintenant, comprenons les rotations ci-dessus avec des exemples.
Pour réorganiser l’arbre, nous devons effectuer quelques rotations. Voici les types de rotations dans l'arbre évasé :
Les rotations en zigzag sont utilisées lorsque l'élément à rechercher est soit un nœud racine, soit l'enfant d'un nœud racine (c'est-à-dire l'enfant gauche ou droit).
Voici les cas qui peuvent exister dans l'arborescence évasée lors de la recherche :
Cas 1: Si l'élément de recherche est un nœud racine de l'arborescence.
Cas 2 : Si l'élément de recherche est un enfant du nœud racine, alors les deux scénarios seront là :
- Si l'enfant est un enfant de gauche, la rotation à droite sera effectuée, connue sous le nom de rotation en zigzag à droite.
- Si l'enfant est un enfant de droite, la rotation à gauche sera effectuée, connue sous le nom de rotation en zigzag à gauche.
Examinons les deux scénarios ci-dessus à travers un exemple.
Considérez l'exemple ci-dessous :
Dans l’exemple ci-dessus, nous devons rechercher 7 éléments dans l’arborescence. Nous suivrons les étapes ci-dessous :
Étape 1: Tout d’abord, nous comparons 7 avec un nœud racine. Comme 7 est inférieur à 10, c'est donc un enfant gauche du nœud racine.
Étape 2: Une fois l’élément trouvé, nous procéderons à l’évasement. La rotation à droite est effectuée pour que 7 devienne le nœud racine de l'arbre, comme indiqué ci-dessous :
Prenons un autre exemple.
Dans l’exemple ci-dessus, nous devons rechercher 20 éléments dans l’arborescence. Nous suivrons les étapes ci-dessous :
Étape 1: Tout d’abord, nous comparons 20 avec un nœud racine. Comme 20 est supérieur au nœud racine, il s’agit donc d’un enfant droit du nœud racine.
Étape 2: Une fois l’élément trouvé, nous procéderons à l’évasement. La rotation vers la gauche est effectuée de manière à ce que 20 éléments deviennent le nœud racine de l'arborescence.
Parfois, la situation se présente lorsque l'élément à rechercher possède à la fois un parent et un grand-parent. Dans ce cas, il faut effectuer quatre rotations pour l'évasement.
Comprenons ce cas à travers un exemple.
Supposons que nous devions rechercher 1 élément dans l'arborescence, illustré ci-dessous :
Étape 1: Tout d’abord, nous devons effectuer une opération de recherche BST standard afin de rechercher le 1 élément. Comme 1 est inférieur à 10 et 7, il sera donc à gauche du nœud 7. Par conséquent, l'élément 1 a un parent, c'est-à-dire 7, ainsi qu'un grand-parent, c'est-à-dire 10.
Étape 2: Dans cette étape, nous devons effectuer un évasement. Nous devons faire du nœud 1 un nœud racine à l’aide de quelques rotations. Dans ce cas, on ne peut pas simplement effectuer une rotation en zigzag ou en zag ; nous devons implémenter une rotation en zigzig.
Afin de faire du nœud 1 un nœud racine, nous devons effectuer deux rotations à droite appelées rotations en zigzig. Lorsque nous effectuons la rotation à droite, alors 10 se déplacera vers le bas et le nœud 7 montera comme le montre la figure ci-dessous :
Encore une fois, nous effectuerons une rotation en zigzag vers la droite, le nœud 7 se déplacera vers le bas et le nœud 1 montera comme indiqué ci-dessous :
Comme nous l'observons dans la figure ci-dessus, le nœud 1 est devenu le nœud racine de l'arbre ; la recherche est donc terminée.
Supposons que nous voulions rechercher 20 dans l’arborescence ci-dessous.
Pour rechercher 20, nous devons effectuer deux rotations vers la gauche. Voici les étapes requises pour rechercher 20 nœuds :
Étape 1: Tout d’abord, nous effectuons l’opération de recherche BST standard. Comme 20 est supérieur à 10 et 15, il sera donc à droite du nœud 15.
Étape 2: La deuxième étape consiste à effectuer un évasement. Dans ce cas, deux rotations vers la gauche seraient effectuées. Lors de la première rotation, le nœud 10 se déplacera vers le bas et le nœud 15 vers le haut, comme indiqué ci-dessous :
Lors de la deuxième rotation à gauche, le nœud 15 se déplacera vers le bas et le nœud 20 deviendra le nœud racine de l'arborescence, comme indiqué ci-dessous :
Comme nous avons observé que deux rotations à gauche sont effectuées ; on parle donc de rotation à gauche en zigzig.
Jusqu'à présent, nous avons lu que les parents et les grands-parents sont tous deux en relation RR ou LL. Nous allons maintenant voir la relation RL ou LR entre le parent et le grand-parent.
Comprenons ce cas à travers un exemple.
Supposons que nous souhaitions rechercher 13 éléments dans l’arborescence ci-dessous :
Étape 1: Tout d’abord, nous effectuons une opération de recherche BST standard. Comme 13 est supérieur à 10 mais inférieur à 15, le nœud 13 sera donc l'enfant gauche du nœud 15.
Étape 2: Puisque le nœud 13 est à gauche de 15 et que le nœud 15 est à droite du nœud 10, la relation RL existe donc. Tout d’abord, nous effectuons la rotation droite sur le nœud 15, et 15 se déplacera vers le bas, et le nœud 13 montera, comme indiqué ci-dessous :
Néanmoins, le nœud 13 n'est pas le nœud racine et 13 est à droite du nœud racine, nous allons donc effectuer une rotation vers la gauche connue sous le nom de rotation zag. Le nœud 10 se déplacera vers le bas et 13 deviendra le nœud racine comme indiqué ci-dessous :
Comme nous pouvons l'observer dans l'arborescence ci-dessus, ce nœud 13 est devenu le nœud racine ; la recherche est donc terminée. Dans ce cas, nous avons d’abord effectué la rotation en zig puis la rotation en zag ; c’est donc ce qu’on appelle une rotation en zigzag.
Comprenons ce cas à travers un exemple.
Supposons que nous souhaitions rechercher 9 éléments dans l'arborescence, illustrée ci-dessous :
Étape 1: Tout d’abord, nous effectuons l’opération de recherche BST standard. Comme 9 est inférieur à 10 mais supérieur à 7, ce sera donc le bon enfant du nœud 7.
Étape 2: Puisque le nœud 9 est à droite du nœud 7 et que le nœud 7 est à gauche du nœud 10, la relation LR existe donc. Tout d’abord, nous effectuons la rotation à gauche sur le nœud 7. Le nœud 7 se déplacera vers le bas et le nœud 9 se déplacera vers le haut comme indiqué ci-dessous :
Pourtant, le nœud 9 n'est pas un nœud racine, et 9 est à gauche du nœud racine, nous allons donc effectuer la rotation à droite connue sous le nom de rotation zig. Après avoir effectué la rotation à droite, le nœud 9 devient le nœud racine, comme indiqué ci-dessous :
Comme nous pouvons l'observer dans l'arborescence ci-dessus, ce nœud 13 est un nœud racine ; la recherche est donc terminée. Dans ce cas, nous avons d’abord effectué la rotation en zag (rotation à gauche), puis la rotation en zig (rotation à droite) est effectuée, c’est donc ce qu’on appelle une rotation en zag zig.
Avantages de l'arbre Splay
- Dans l’arborescence évasée, nous n’avons pas besoin de stocker les informations supplémentaires. En revanche, dans les arbres AVL, nous devons stocker le facteur d'équilibre de chaque nœud qui nécessite un espace supplémentaire, et les arbres Rouge-Noir nécessitent également de stocker un bit d'information supplémentaire qui indique la couleur du nœud, rouge ou noir.
- Il s’agit du type d’arbre de recherche binaire le plus rapide pour diverses applications pratiques. Il est utilisé dans Compilateurs Windows NT et GCC .
- Il offre de meilleures performances car les nœuds fréquemment consultés se rapprocheront du nœud racine, grâce à quoi les éléments seront accessibles rapidement dans les arbres évasés. Il est utilisé dans l'implémentation du cache car les données récemment consultées sont stockées dans le cache afin que nous n'ayons pas besoin d'accéder à la mémoire pour accéder aux données, et cela prend moins de temps.
Inconvénient de l’arbre Splay
L’inconvénient majeur de l’arbre évasé serait que les arbres ne sont pas strictement équilibrés, c’est-à-dire qu’ils sont à peu près équilibrés. Parfois, les arbres évasés sont linéaires, cela prendra donc une complexité temporelle O(n).
Opération d'insertion dans l'arborescence Splay
Dans le insertion opération, nous insérons d’abord l’élément dans l’arborescence puis effectuons l’opération d’évasement sur l’élément inséré.
15, 10, 17, 7
Étape 1: Tout d’abord, nous insérons le nœud 15 dans l’arborescence. Après l'insertion, nous devons effectuer un évasement. Comme 15 est un nœud racine, nous n’avons donc pas besoin d’effectuer d’évasement.
Étape 2: L'élément suivant est 10. Comme 10 est inférieur à 15, le nœud 10 sera donc l'enfant gauche du nœud 15, comme indiqué ci-dessous :
Maintenant, nous effectuons ébrasement . Pour en faire 10 comme nœud racine, nous allons effectuer la bonne rotation, comme indiqué ci-dessous :
Étape 3: L'élément suivant est 17. Comme 17 est supérieur à 10 et 15, il deviendra donc l'enfant droit du nœud 15.
Maintenant, nous allons procéder à l'évasement. Comme 17, c'est avoir un parent ainsi qu'un grand-parent, nous effectuerons donc des rotations en zigzig.
Dans la figure ci-dessus, nous pouvons observer que 17 devient le nœud racine de l’arbre ; par conséquent, l'insertion est terminée.
Étape 4: L'élément suivant est 7. Comme 7 est inférieur à 17, 15 et 10, le nœud 7 restera donc l'enfant de 10.
Maintenant, nous devons évaser l'arbre. Comme 7 signifie avoir un parent et un grand-parent, nous allons donc effectuer deux rotations à droite comme indiqué ci-dessous :
Pourtant, le nœud 7 n'est pas un nœud racine, c'est un enfant gauche du nœud racine, c'est-à-dire 17. Nous devons donc effectuer une rotation supplémentaire à droite pour faire du nœud 7 un nœud racine, comme indiqué ci-dessous :
Algorithme pour l'opération d'insertion
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
Dans l'algorithme ci-dessus, T est l'arbre et n est le nœud que nous voulons insérer. Nous avons créé une variable temporaire qui contient l'adresse du nœud racine. Nous exécuterons la boucle while jusqu'à ce que la valeur de temp devienne NULL.
Une fois l'insertion terminée, l'évasement sera effectué
Algorithme pour l'opération d'évasement
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
Dans l'implémentation ci-dessus, x est le nœud sur lequel la rotation est effectuée, alors que y est l'enfant gauche du nœud x.
Implémentation de left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
Dans l'implémentation ci-dessus, x est le nœud sur lequel la rotation est effectuée et y est l'enfant droit du nœud x.
Suppression dans l'arborescence Splay
Comme nous savons que les arbres évasés sont des variantes de l'arbre de recherche binaire, l'opération de suppression dans l'arbre évasé serait similaire au BST, mais la seule différence est que l'opération de suppression est suivie dans les arbres évasés par l'opération d'évasement.
Types de suppressions :
Il existe deux types de suppressions dans les arbres évasés :
- Évasement ascendant
- Évasement descendant
Évasement ascendant
Dans l'évasement ascendant, nous supprimons d'abord l'élément de l'arborescence, puis nous effectuons l'évasement sur le nœud supprimé.
Comprenons la suppression dans l'arborescence Splay.
Supposons que nous souhaitions supprimer 12, 14 de l'arborescence ci-dessous :
tests et types de tests
- Tout d’abord, nous effectuons simplement l’opération de suppression BST standard pour supprimer 12 éléments. Comme 12 est un nœud feuille, nous supprimons simplement le nœud de l’arborescence.
La suppression n'est toujours pas terminée. Nous devons évaser le parent du nœud supprimé, c'est-à-dire 10. Nous devons effectuer Évasé(10) sur l'arbre. Comme nous pouvons observer dans l'arbre ci-dessus, 10 est à droite du nœud 7 et le nœud 7 est à gauche du nœud 13. Ainsi, d'abord, nous effectuons la rotation à gauche sur le nœud 7, puis nous effectuons la rotation à droite sur le nœud 13, comme indiqué ci-dessous :
Pourtant, le nœud 10 n’est pas un nœud racine ; le nœud 10 est l'enfant gauche du nœud racine. Nous devons donc effectuer la bonne rotation sur le nœud racine, c'est-à-dire 14 pour faire du nœud 10 un nœud racine comme indiqué ci-dessous :
- Maintenant, nous devons supprimer le 14e élément de l’arborescence, illustré ci-dessous :
Comme nous le savons, nous ne pouvons pas simplement supprimer le nœud interne. Nous remplacerons la valeur du nœud soit par dans l'ordre prédécesseur ou dans l'ordre successeur . Supposons que nous utilisions un successeur dans l'ordre dans lequel nous remplaçons la valeur par la valeur la plus basse existant dans le sous-arbre de droite. La valeur la plus basse dans le sous-arbre droit du nœud 14 est 15, nous remplaçons donc la valeur 14 par 15. Puisque le nœud 14 devient le nœud feuille, nous pouvons simplement le supprimer comme indiqué ci-dessous :
Pourtant, la suppression n’est pas terminée. Nous devons effectuer une opération supplémentaire, c'est-à-dire un évasement dans lequel nous devons faire du parent du nœud supprimé le nœud racine. Avant la suppression, le parent du nœud 14 était le nœud racine, c'est-à-dire 10, nous devons donc effectuer un évasement dans ce cas.
Évasement descendant
Dans l'évasement descendant, nous effectuons d'abord l'évasement sur lequel la suppression doit être effectuée, puis supprimons le nœud de l'arborescence. Une fois l’élément supprimé, nous effectuerons l’opération de jointure.
Comprenons l'évasement descendant à travers un exemple.
Supposons que nous souhaitions supprimer 16 de l’arborescence ci-dessous :
Étape 1: Dans l'évasement descendant, nous effectuons d'abord l'évasement sur le nœud 16. Le nœud 16 a à la fois un parent et un grand-parent. Le nœud 16 est à droite de son parent et le nœud parent est également à droite de son parent, c'est donc une situation zag zag. Dans ce cas, nous effectuerons d’abord la rotation gauche sur le nœud 13 puis 14 comme indiqué ci-dessous :
Le nœud 16 n'est toujours pas un nœud racine, et c'est un enfant droit du nœud racine, nous devons donc effectuer une rotation à gauche sur le nœud 12 pour faire du nœud 16 un nœud racine.
Une fois que le nœud 16 devient un nœud racine, nous supprimerons le nœud 16 et nous obtiendrons deux arbres différents, c'est-à-dire un sous-arbre gauche et un sous-arbre droit, comme indiqué ci-dessous :
Comme nous le savons, les valeurs du sous-arbre de gauche sont toujours inférieures aux valeurs du sous-arbre de droite. La racine du sous-arbre de gauche est 12 et la racine du sous-arbre de droite est 17. La première étape consiste à trouver le maximum d’éléments dans le sous-arbre de gauche. Dans le sous-arbre de gauche, l'élément maximum est 15, et nous devons ensuite effectuer une opération d'évasement sur 15.
Comme nous pouvons l'observer dans l'arbre ci-dessus, l'élément 15 a un parent ainsi qu'un grand-parent. Un nœud est à droite de son parent, et le nœud parent est également à droite de son parent, nous devons donc effectuer deux rotations vers la gauche pour faire du nœud 15 un nœud racine comme indiqué ci-dessous :
Après avoir effectué deux rotations sur l'arbre, le nœud 15 devient le nœud racine. Comme nous pouvons le voir, le bon enfant du 15 est NULL, nous attachons donc le nœud 17 à la partie droite du 15 comme indiqué ci-dessous, et cette opération est connue sous le nom de rejoindre opération.
Remarque : Si l'élément n'est pas présent dans l'arborescence d'évasement qui doit être supprimée, l'évasement sera effectué. L'évasement serait effectué sur le dernier élément accédé avant d'atteindre le NULL.
Algorithme d'opération de suppression
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
Dans l'algorithme ci-dessus, nous vérifions d'abord si la racine est Null ou non ; si la racine est NULL, cela signifie que l'arborescence est vide. Si l'arborescence n'est pas vide, nous effectuerons l'opération d'évasement sur l'élément qui doit être supprimé. Une fois l'opération d'évasement terminée, nous comparerons les données racine avec l'élément qui doit être supprimé ; si les deux ne sont pas égaux, cela signifie que l’élément n’est pas présent dans l’arborescence. S'ils sont égaux, alors les cas suivants peuvent se produire :
Cas 1 : La gauche de la racine est NULL, la droite de la racine devient le nœud racine.
Cas 2 : Si les deux gauche et droite existent, alors nous évasons le maximum d'éléments dans le sous-arbre gauche. Lorsque l'évasement est terminé, l'élément maximum devient la racine du sous-arbre gauche. Le sous-arbre droit deviendrait l'enfant droit de la racine du sous-arbre gauche.