Facteurs d'équilibre et rotations dans les arbres AVL

Balance Factor

• Definition: The balance factor of a node is the difference between the height of its left subtree and the height of its right subtree.
• Calculated as: balanceFactor = height(leftSubtree) - height(rightSubtree)
• Range: -1, 0, or 1 for a balanced AVL tree
• Purpose: Ensures the tree remains approximately balanced during insertion and deletion operations

Rotation

• Types:
  • Left rotation (LL rotation): when the right subtree is taller
  • Right rotation (RR rotation): when the left subtree is taller
  • Left-right rotation (LR rotation): when the left subtree is taller and the right subtree is shorter
  • Right-left rotation (RL rotation): when the right subtree is taller and the left subtree is shorter
• Purpose: Restores balance to the tree by rotating nodes to maintain a balanced tree

Height Balancing

• Definition: The process of maintaining a balanced AVL tree by rotating nodes to ensure the balance factor remains within the range of -1, 0, or 1
• Purpose: Ensures the tree remains approximately balanced, allowing for efficient search, insertion, and deletion operations
• Importance: Prevents the tree from becoming too unbalanced, which can lead to reduced performance and increased search times

Deletion

• Steps:
  1. Find the node to be deleted
  2. If the node has no children, simply remove it
  3. If the node has one child, replace it with its child node
  4. If the node has two children, find its inorder successor (smallest node in the right subtree) and replace the node with its inorder successor
  5. Rebalance the tree by rotating nodes as necessary to maintain a balanced tree
• Importance: Ensures the tree remains balanced and efficient after deletion operations

Insertion

• Steps:
  1. Find the location for the new node
  2. Insert the new node
  3. Rebalance the tree by rotating nodes as necessary to maintain a balanced tree
• Importance: Ensures the tree remains balanced and efficient after insertion operations

###Facteur d'Équilibre

• Définition: Le facteur d'équilibre d'un nœud est la différence entre la hauteur de son sous-arbre gauche et la hauteur de son sous-arbre droit.
• Calculé comme: facteurDEquilibre = hauteur(sousArbreGauche) - hauteur(sousArbreDroit)
• Plage: -1, 0 ou 1 pour un arbre AVL équilibré
• But: Assure que l'arbre reste approximativement équilibré lors des opérations d'insertion et de suppression.

Rotation

• Types:
  • Rotation gauche (LL rotation): lorsque le sous-arbre droit est plus haut
  • Rotation droite (RR rotation): lorsque le sous-arbre gauche est plus haut
  • Rotation gauche-droite (LR rotation): lorsque le sous-arbre gauche est plus haut et le sous-arbre droit est plus bas
  • Rotation droite-gauche (RL rotation): lorsque le sous-arbre droit est plus haut et le sous-arbre gauche est plus bas
• But: Rétablit l'équilibre de l'arbre en faisant pivoter les nœuds pour maintenir un arbre équilibré.

Équilibrage de Hauteur

• Définition: Le processus de maintien d'un arbre AVL équilibré en faisant pivoter les nœuds pour assurer que le facteur d'équilibre reste dans la plage de -1, 0 ou 1.
• But: Assure que l'arbre reste approximativement équilibré, permettant des opérations de recherche, d'insertion et de suppression efficaces.
• Importance: Empêche l'arbre de devenir trop déséquilibré, ce qui peut entraîner une réduction des performances et des temps de recherche accrus.

Suppression

• Étapes:
  • Trouver le nœud à supprimer
  • Si le nœud n'a pas d'enfants, le supprimer simplement
  • Si le nœud a un enfant, le remplacer par son nœud enfant
  • Si le nœud a deux enfants, trouver le successeur inordre (le plus petit nœud du sous-arbre droit) et le remplacer par le successeur inordre
  • Rééquilibrer l'arbre en faisant pivoter les nœuds au besoin pour maintenir un arbre équilibré
• Importance: Assure que l'arbre reste équilibré et efficace après les opérations de suppression.

Insertion

• Étapes:
  • Trouver la localisation du nouveau nœud
  • Insérer le nouveau nœud
  • Rééquilibrer l'arbre en faisant pivoter les nœuds au besoin pour maintenir un arbre équilibré
• Importance: Assure que l'arbre reste équilibré et efficace après les opérations d'insertion.