L'arbre Splay est une structure de données d'arbre de recherche binaire auto-ajustable, ce qui signifie que la structure arborescente est ajustée dynamiquement en fonction des éléments consultés ou insérés. En d’autres termes, l’arborescence se réorganise automatiquement afin que les éléments fréquemment consultés ou insérés se rapprochent du nœud racine.

1. L'arbre évasé a été introduit pour la première fois par Daniel Dominic Sleator et Robert Endre Tarjan en 1985. Il a une implémentation simple et efficace qui lui permet d'effectuer des opérations de recherche, d'insertion et de suppression dans une complexité temporelle amortie O (log n), où n est le nombre d'éléments dans l'arbre.
2. L'idée de base derrière les arbres évasés est d'amener l'élément le plus récemment accédé ou inséré à la racine de l'arbre en effectuant une séquence de rotations d'arbre, appelée évasement. L'évasement est un processus de restructuration de l'arborescence en faisant de l'élément le plus récemment accédé ou inséré la nouvelle racine et en rapprochant progressivement les nœuds restants de la racine.
3. Les arbres évasés sont très efficaces dans la pratique en raison de leur nature auto-ajustable, ce qui réduit le temps d'accès global aux éléments fréquemment consultés. Cela en fait un bon choix pour les applications qui nécessitent des structures de données rapides et dynamiques, telles que les systèmes de mise en cache, la compression des données et les algorithmes de routage réseau.
4. Cependant, le principal inconvénient des arbres évasés est qu’ils ne garantissent pas une structure arborescente équilibrée, ce qui peut conduire à une dégradation des performances dans le pire des cas. De plus, les arbres évasés ne conviennent pas aux applications qui nécessitent des performances garanties dans le pire des cas, telles que les systèmes en temps réel ou les systèmes critiques pour la sécurité.

Dans l’ensemble, les arbres splay constituent une structure de données puissante et polyvalente qui offre un accès rapide et efficace aux éléments fréquemment consultés ou insérés. Ils sont largement utilisés dans diverses applications et offrent un excellent compromis entre performances et simplicité.

Un arbre évasé est un arbre de recherche binaire auto-équilibré, conçu pour un accès efficace aux éléments de données en fonction de leurs valeurs clés.

• La principale caractéristique d'un arbre évasé est que chaque fois qu'un élément est accédé, il est déplacé vers la racine de l'arborescence, créant ainsi une structure plus équilibrée pour les accès ultérieurs.
• Les arbres évasés se caractérisent par l'utilisation de rotations, qui sont des transformations locales de l'arbre qui changent sa forme mais préservent l'ordre des éléments.
• Les rotations sont utilisées pour amener l'élément accédé à la racine de l'arborescence, et également pour rééquilibrer l'arborescence si elle devient déséquilibrée après plusieurs accès.

Opérations dans un arbre évasé :

• Insertion: Pour insérer un nouvel élément dans l'arborescence, commencez par effectuer une insertion régulière d'arborescence de recherche binaire. Ensuite, appliquez des rotations pour amener l’élément nouvellement inséré à la racine de l’arborescence.
• Effacement : Pour supprimer un élément de l'arborescence, localisez-le d'abord à l'aide d'une recherche arborescente binaire. Ensuite, si l’élément n’a pas d’enfant, supprimez-le simplement. S'il a un enfant, promouvez cet enfant à sa position dans l'arbre. S'il a deux enfants, recherchez le successeur de l'élément (le plus petit élément de son sous-arbre droit), échangez sa clé avec l'élément à supprimer et supprimez le successeur à la place.
• Recherche : Pour rechercher un élément dans l'arborescence, commencez par effectuer une recherche arborescente binaire. Si l'élément est trouvé, appliquez des rotations pour l'amener à la racine de l'arbre. S'il n'est pas trouvé, appliquez des rotations au dernier nœud visité dans la recherche, qui devient la nouvelle racine.
• Rotation : Les rotations utilisées dans un arbre évasé sont soit une rotation Zig, soit une rotation Zig-Zig. Une rotation Zig est utilisée pour amener un nœud à la racine, tandis qu'une rotation Zig-Zig est utilisée pour équilibrer l'arbre après plusieurs accès aux éléments d'un même sous-arbre.

Voici une explication étape par étape des opérations de rotation :

• Rotation en zigzag : Si un nœud a un enfant droit, effectuez une rotation droite pour l'amener à la racine. S'il a un enfant à gauche, effectuez une rotation à gauche.
• Rotation zigzig : Si un nœud a un petit-enfant qui est également l’enfant droit ou gauche de son enfant, effectuez une double rotation pour équilibrer l’arbre. Par exemple, si le nœud a un enfant de droite et que l'enfant de droite a un enfant de gauche, effectuez une rotation droite-gauche. Si le nœud a un enfant de gauche et que l'enfant de gauche a un enfant de droite, effectuez une rotation gauche-droite.
• Note: Les détails spécifiques de mise en œuvre, y compris les rotations exactes utilisées, peuvent varier en fonction de la forme exacte de l'arbre évasé.

Rotations dans l'arbre évasé

• Rotation en zigzag
• Rotation Zag
• Zig – Rotation en zigzag
• Zag – Rotation Zag
• Rotation Zig-Zag
• Zag – Rotation en zigzag

1) Rotation en zigzag :

La rotation en zigzag dans les arbres évasés fonctionne d'une manière similaire à la rotation simple à droite dans les rotations d'arbres AVL. Cette rotation entraîne le déplacement des nœuds d'une position vers la droite par rapport à leur emplacement actuel. Par exemple, considérons le scénario suivant :

Rotation en zigzag (rotation simple)

2) Rotation Zag :

La rotation Zag dans les arbres évasés fonctionne de la même manière que la rotation simple vers la gauche dans les rotations d'arbres AVL. Au cours de cette rotation, les nœuds se déplacent d'une position vers la gauche par rapport à leur emplacement actuel. Par exemple, considérons l’illustration suivante :

rekha indien

Rotation Zag (rotation simple à gauche)

3) Rotation zigzig :

La rotation zig-zig dans les arbres évasés est une double rotation en zigzag. Cette rotation entraîne le déplacement des nœuds de deux positions vers la droite par rapport à leur emplacement actuel. Jetez un œil à l’exemple suivant pour une meilleure compréhension :

Rotation zig-zig (double rotation à droite)

4) Rotation Zag-Zag :

Dans les arbres évasés, la rotation Zag-Zag est une rotation double zag. Cette rotation amène les nœuds à se déplacer de deux positions vers la gauche par rapport à leur position actuelle. Par exemple:

Rotation Zag-Zag (Double rotation à gauche)

bloquer les publicités YouTube sur Android

5) Rotation en zigzag :

La rotation en zigzag dans les arbres évasés est une combinaison d'une rotation en zigzag suivie d'une rotation en zag. À la suite de cette rotation, les nœuds se déplacent d’une position vers la droite puis d’une position vers la gauche par rapport à leur emplacement actuel. L'illustration suivante fournit une représentation visuelle de ce concept :

Rotation en zigzag

6) Rotation Zag-Zig :

La rotation Zag-Zig dans les arbres évasés est une série de rotations en zag suivies d'une rotation en zig. Cela entraîne le déplacement des nœuds d'une position vers la gauche, suivi d'un déplacement d'une position vers la droite par rapport à leur emplacement actuel. L'illustration suivante offre une représentation visuelle de ce concept :

Rotation Zag-Zig

Vous trouverez ci-dessous le code C++ pour implémenter les rotations dans l'arborescence Splay :

#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->clé = clé ;  nœud->gauche = nœud->droite = nullptr ;  nœud de retour ; } Noeud* rightRotate(Node* x) { Node* y = x->left;  x->gauche = y->droite ;  y->droite = x ;  retourner y ; } Noeud* leftRotate(Node* x) { Noeud* y = x->right;  x->droite = y->gauche ;  y->gauche = x ;  retourner y ; } Node* splay(Node* root, int key) { if (root == nullptr || root->key == key) return root;  if (root->key> key) { if (root->left == nullptr) return root ;  if (root->left->key> key) { root->left->left = splay(root->left->left, key);  racine = rotation droite(racine);  } else if (racine->gauche->clé< key) {  root->gauche->droite = splay(root->gauche->droite, clé);  if (root->left->right != nullptr) root->left = leftRotate(root->left);  } return (root->left == nullptr) ? racine : rightRotate(racine);  } else { if (root->right == nullptr) return root ;  if (root->right->key> key) { root->right->left = splay(root->right->left, key);  if (root->right->left != nullptr) root->right = rightRotate(root->right);  } else if (root->right->key< key) {  root->droite->droite = splay(root->droite->droite, clé);  racine = leftRotate(racine);  } return (root->right == nullptr) ? racine : leftRotate(racine);  } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key);  root = splay (racine, clé);  if (root->key == key) renvoie la racine ;  Noeud* node = newNode(clé);  if (root->key> key) { node->right = root;  nœud->gauche = racine->gauche ;  racine->gauche = nullptr ;  } else { noeud->gauche = racine ;  nœud->droit = ​​racine->droite ;  racine->droite = nullptr ;  } nœud de retour ; } void preOrder(Node* node) { if (node ​​!= nullptr) { cout<< node->clé<< ' ';  preOrder(node->gauche);  preOrder(nœud->droite);  } } int main() { Noeud* root = nullptr;  racine = insert(racine, 100);  racine = insert(racine, 50);  racine = insert(racine, 200);  racine = insert(racine, 40);  racine = insert(racine, 60);  cout<< 'Preorder traversal of the modified Splay tree:' << endl;  preOrder(root);  return 0; }>

// Java Program for the above approach class Node {  public int key;  public Node left, right; } class SplayTree {  static Node newNode(int key) {  Node node = new Node();  node.key = key;  node.left = node.right = null;  return node;  }  static Node rightRotate(Node x) {  Node y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static Node leftRotate(Node x) {  Node y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static Node splay(Node root, int key) {  if (root == null || root.key == key)  return root;  if (root.key>clé) { if (root.left == null) return root ;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  racine = rotation droite(racine);  } sinon si (root.left.key< key) {  root.left.right = splay(root.left.right, key);  if (root.left.right != null)  root.left = leftRotate(root.left);  }  return (root.left == null) ? root : rightRotate(root);  }  else {  if (root.right == null)  return root;  if (root.right.key>clé) { root.right.left = splay(root.right.left, clé);  if (root.right.left != null) root.right = rightRotate(root.right);  } sinon si (root.right.key< key) {  root.right.right = splay(root.right.right, key);  root = leftRotate(root);  }  return (root.right == null) ? root : leftRotate(root);  }  }  static Node insert(Node root, int key) {  if (root == null)  return newNode(key);  root = splay(root, key);  if (root.key == key)  return root;  Node node = newNode(key);  if (root.key>clé) { node.right = racine ;  noeud.left = racine.left;  racine.left = null ;  } else { node.left = racine ;  noeud.right = root.right;  root.right = null ;  } nœud de retour ;  } static void preOrder(Node node) { if (node ​​!= null) { System.out.println();  System.out.print(node.key + '');  preOrder(node.left);  preOrder(node.right);  } } public static void main(String[] args) { Racine du nœud = null ;  racine = insert(racine, 100);  racine = insert(racine, 50);  racine = insert(racine, 200);  racine = insert(racine, 40);  racine = insert(racine, 60);  System.out.println('Parcours de précommande de l'arbre Splay modifié :');  preOrder(racine);  } } // Ce code est contribué par princekumaras>

class Node: def __init__(self, key): self.key = key self.left = None self.right = None def new_node(key): return Node(key) def right_rotate(x): y = x.left x.left = y.right y.right = x return y def left_rotate(x): y = x.right x.right = y.left y.left = x return y def splay(root, key): if root is None : return new_node(key) if root.key == key: return root if root.key>key : si root.left est None : renvoie root si root.left.key> key : root.left.left = splay(root.left.left, key) root = right_rotate(root) elif root.left.key< key: root.left.right = splay(root.left.right, key) if root.left.right: root.left = left_rotate(root.left) return root.left if root.left is None else right_rotate(root) else: if root.right is None: return root if root.right.key>clé : root.right.left = splay(root.right.left, key) si root.right.left : root.right = right_rotate(root.right) elif root.right.key< key: root.right.right = splay(root.right.right, key) root = left_rotate(root) return root.right if root.right is None else left_rotate(root) def insert(root, key): if root is None: return new_node(key) root = splay(root, key) if root.key == key: return root node = new_node(key) if root.key>clé : node.right = racine node.left = root.left root.left = Aucun autre : node.left = racine node.right = root.right root.right = Aucun return node def pre_order(node) : if node : print (node.key, end=' ') pre_order(node.left) pre_order(node.right) si __name__ == '__main__' : root = Aucun root = insert (root, 100) root = insert (root , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Parcours de précommande de l'arbre Splay modifié :') pre_order(root)>

// C# program for the above approach using System; class Node {  public int key;  public Node left, right; } class SplayTree {  static Node newNode(int key)  {  Node node = new Node();  node.key = key;  node.left = node.right = null;  return node;  }  static Node rightRotate(Node x)  {  Node y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static Node leftRotate(Node x)  {  Node y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static Node splay(Node root, int key)  {  if (root == null || root.key == key)  return root;  if (root.key>clé) { if (root.left == null) return root ;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  racine = rotation droite(racine);  } sinon si (root.left.key< key) {  root.left.right  = splay(root.left.right, key);  if (root.left.right != null)  root.left = leftRotate(root.left);  }  return (root.left == null) ? root  : rightRotate(root);  }  else {  if (root.right == null)  return root;  if (root.right.key>clé) { root.right.left = splay(root.right.left, clé);  if (root.right.left != null) root.right = rightRotate(root.right);  } sinon si (root.right.key< key) {  root.right.right  = splay(root.right.right, key);  root = leftRotate(root);  }  return (root.right == null) ? root  : leftRotate(root);  }  }  static Node insert(Node root, int key)  {  if (root == null)  return newNode(key);  root = splay(root, key);  if (root.key == key)  return root;  Node node = newNode(key);  if (root.key>clé) { node.right = racine ;  noeud.left = racine.left;  racine.left = null ;  } else { node.left = racine ;  noeud.right = root.right;  root.right = null ;  } nœud de retour ;  } static void preOrder(Node node) { if (node ​​!= null) { Console.Write(node.key + ' ');  preOrder(node.left);  preOrder(node.right);  } } public static void Main(string[] args) { Racine du nœud = null ;  racine = insert(racine, 100);  racine = insert(racine, 50);  racine = insert(racine, 200);  racine = insert(racine, 40);  racine = insert(racine, 60);  Console.WriteLine( 'Parcours de précommande de l'arbre Splay modifié :');  preOrder(racine);  } } // Ce code est fourni par Prince Kumar>

// Javascript code addition  class Node {  constructor(key) {  this.key = key;  this.left = null;  this.right = null;  } } class SplayTree {  static newNode(key) {  const node = new Node(key);  return node;  }  static rightRotate(x) {  const y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static leftRotate(x) {  const y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static splay(root, key) {  if (root == null || root.key == key) {  return root;  }  if (root.key>clé) { if (root.left == null) { return root ;  } if (root.left.key> key) { root.left.left = SplayTree.splay(root.left.left, key);  racine = SplayTree.rightRotate(racine);  } sinon si (root.left.key< key) {  root.left.right = SplayTree.splay(root.left.right, key);  if (root.left.right != null) {  root.left = SplayTree.leftRotate(root.left);  }  }  return root.left == null ? root : SplayTree.rightRotate(root);  } else {  if (root.right == null) {  return root;  }  if (root.right.key>clé) { root.right.left = SplayTree.splay(root.right.left, clé);  if (root.right.left != null) { root.right = SplayTree.rightRotate(root.right);  } } sinon si (root.right.key< key) {  root.right.right = SplayTree.splay(root.right.right, key);  root = SplayTree.leftRotate(root);  }  return root.right == null ? root : SplayTree.leftRotate(root);  }  }  static insert(root, key) {  if (root == null) {  return SplayTree.newNode(key);  }  root = SplayTree.splay(root, key);  if (root.key == key) {  return root;  }  const node = SplayTree.newNode(key);  if (root.key>clé) { node.right = racine ;  noeud.left = racine.left;  racine.left = null ;  } else { node.left = racine ;  noeud.right = root.right;  root.right = null ;  } nœud de retour ;  } static preOrder(node) { if (node ​​!= null) { console.log(node.key + ' ');  SplayTree.preOrder(node.left);  SplayTree.preOrder(node.right);  } } } let root = null; racine = SplayTree.insert (racine, 100); racine = SplayTree.insert(racine, 50); racine = SplayTree.insert(racine, 200); racine = SplayTree.insert(racine, 40); racine = SplayTree.insert(racine, 60); console.log('Parcours de précommande de l'arbre Splay modifié :'); SplayTree.preOrder(racine); // Le code est contribué par Nidhi goel.>

Preorder traversal of the modified Splay tree:>

Inconvénients de la structure de données de l'arborescence évasée :

• Arbres déséquilibrés : Les arbres évasés peuvent devenir déséquilibrés et inefficaces s’ils tournent à plusieurs reprises dans la même direction.
• Utilisation de la mémoire: Les arbres splay peuvent utiliser beaucoup de mémoire par rapport à d'autres structures de données, car chaque nœud contient des informations supplémentaires.
• Complexité: Les arbres évasés peuvent présenter une complexité temporelle élevée pour les opérations de base telles que l'insertion et la suppression, car les arbres doivent être réorganisés après chaque opération.
• Frais généraux de réorganisation : L'opération d'évasement requise dans chaque opération peut prendre du temps et entraîner des frais généraux élevés.
• Cas d'utilisation limités : Les arbres Splay ne conviennent pas à toutes les structures de données et ont des cas d'utilisation limités car ils ne gèrent pas efficacement les clés en double.

Applications de l'arbre évasé :

• Mise en cache : Les arborescences Splay peuvent être utilisées pour implémenter la gestion de la mémoire cache, où les éléments les plus fréquemment consultés sont déplacés vers le haut de l'arborescence pour un accès plus rapide.
• Indexation de base de données : Les arbres Splay peuvent être utilisés pour indexer des bases de données afin d'accélérer la recherche et la récupération des données.
• Systèmes de fichiers : Les arborescences Splay peuvent être utilisées pour stocker les métadonnées du système de fichiers, telles que la table d'allocation, la structure des répertoires et les attributs de fichier.
• Compression des données : Les arbres évasés peuvent être utilisés pour compresser les données en identifiant et en codant des modèles répétitifs.
• Traitement de texte : Les arbres évasés peuvent être utilisés dans les applications de traitement de texte, telles que les correcteurs orthographiques, où les mots sont stockés dans un arbre évasé pour une recherche et une récupération rapides.
• Algorithmes graphiques : Les arbres évasés peuvent être utilisés pour implémenter des algorithmes graphiques, tels que la recherche du chemin le plus court dans un graphique pondéré.
• Jeux en ligne : Les arbres Splay peuvent être utilisés dans les jeux en ligne pour stocker et gérer les meilleurs scores, les classements et les statistiques des joueurs.

Bien sûr, voici quelques avantages et inconvénients des arbres évasés, ainsi que quelques livres recommandés pour en savoir plus sur le sujet :

Avantages des arbres évasés :

Les arbres splay ont amorti la complexité temporelle de O (log n) pour de nombreuses opérations, ce qui les rend plus rapides que de nombreuses autres structures de données arborescentes équilibrées dans certains cas.
Les arbres évasés s'ajustent automatiquement, ce qui signifie qu'ils s'équilibrent automatiquement lorsque des éléments sont insérés et supprimés. Cela peut aider à éviter la dégradation des performances qui peut survenir lorsqu'un arbre devient déséquilibré.

Inconvénients des arbres évasés :

Les arbres évasés peuvent avoir une complexité temporelle de O(n) dans le pire des cas pour certaines opérations, ce qui les rend moins prévisibles que d'autres structures de données arborescentes équilibrées comme les arbres AVL ou les arbres rouge-noir.
Les arbres évasés peuvent ne pas convenir à certaines applications où des performances prévisibles sont requises.

arbre binaire vs arbre de recherche binaire

Livres recommandés sur les arbres Splay :

Structures de données et analyse d'algorithmes en Java par Mark Allen Weiss
Introduction aux algorithmes par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein
Structures de données et algorithmes en C++ par Michael T. Goodrich et Roberto Tamassia

Conclusion:

En conclusion, les Splay Trees sont une structure de données d'arbre de recherche binaire dynamique et auto-équilibrée qui fournit un moyen efficace de rechercher, d'insérer et de supprimer des éléments. Ils diffèrent des arbres de recherche binaires équilibrés traditionnels comme les arbres AVL et Rouge-Noir, car ils réorganisent l'arborescence après chaque opération pour amener le nœud récemment accédé à la racine. Cela permet de réduire la hauteur de l’arbre et d’accélérer les opérations. Les Splay Trees sont très flexibles et peuvent être adaptés à divers cas d’utilisation. Même s’ils peuvent nécessiter davantage de rotations, leur simplicité et leur polyvalence en font des outils utiles pour résoudre un large éventail de problèmes.