Guide des arborescences AVL en Java

1. Introduction

Dans ce didacticiel, nous présenterons l'arborescence AVL et nous examinerons les algorithmes d'insertion, de suppression et de recherche de valeurs.

2. Qu'est-ce que AVL Tree?

L'arbre AVL, nommé d'après ses inventeurs Adelson-Velsky et Landis, est un arbre de recherche binaire à équilibrage automatique (BST).

Un arbre auto-équilibré est un arbre de recherche binaire qui équilibre la hauteur après insertion et suppression selon certaines règles d'équilibrage.

La complexité temporelle dans le pire des cas d'un BST est fonction de la hauteur de l'arbre. Plus précisément, le chemin le plus long de la racine de l'arbre à un nœud. Pour un BST avec N nœuds, disons que chaque nœud n'a que zéro ou un enfant. Par conséquent, sa hauteur est égale à N, et le temps de recherche dans le pire des cas est O (N). Donc, notre objectif principal dans un BST est de garder la hauteur maximale proche de la bûche (N).

Le facteur d'équilibre du nœud N est hauteur (droite (N)) - hauteur (gauche (N)) . Dans une arborescence AVL, le facteur d'équilibre d'un nœud ne peut être que l'une des valeurs 1, 0 ou -1.

Définissons un objet Node pour notre arbre:

public class Node { int key; int height; Node left; Node right; ... }

Ensuite, définissons l' AVLTree :

public class AVLTree { private Node root; void updateHeight(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); } int height(Node n) { return n == null ? -1 : n.height; } int getBalance(Node n) { return (n == null) ? 0 : height(n.right) - height(n.left); } ... }

3. Comment équilibrer un arbre AVL?

L'arborescence AVL vérifie le facteur d'équilibre de ses nœuds après l'insertion ou la suppression d'un nœud. Si le facteur d'équilibre d'un nœud est supérieur à un ou inférieur à -1, l'arbre se rééquilibre.

Il existe deux opérations pour rééquilibrer un arbre:

  • rotation droite et
  • rotation à gauche.

3.1. Rotation à droite

Commençons par la bonne rotation.

Supposons que nous ayons un BST appelé T1, avec Y comme nœud racine, X comme enfant gauche de Y et Z comme enfant droit de X. Étant donné les caractéristiques d'un BST, nous savons que X <Z <Y.

Après une rotation droite de Y, nous avons un arbre appelé T2 avec X comme racine et Y comme enfant droit de X et Z comme enfant gauche de Y. T2 est toujours un BST car il garde l'ordre X <Z <Y .

Jetons un coup d'œil à la bonne opération de rotation pour notre AVLTree :

Node rotateRight(Node y) { Node x = y.left; Node z = x.right; x.right = y; y.left = z; updateHeight(y); updateHeight(x); return x; }

3.2. Opération de rotation gauche

Nous avons également une opération de rotation à gauche.

Supposons un BST appelé T1, avec Y comme nœud racine, X comme enfant droit de Y et Z comme enfant gauche de X. Compte tenu de cela, nous savons que Y <Z <X.

Après une rotation gauche de Y, nous avons un arbre appelé T2 avec X comme racine et Y comme enfant gauche de X et Z comme enfant droit de Y. T2 est toujours un BST car il garde l'ordre Y <Z <X .

Jetons un coup d'œil à l'opération de rotation à gauche pour notre AVLTree :

Node rotateLeft(Node y) { Node x = y.right; Node z = x.left; x.left = y; y.right = z; updateHeight(y); updateHeight(x); return x; }

3.3. Techniques de rééquilibrage

Nous pouvons utiliser les opérations de rotation droite et gauche dans des combinaisons plus complexes pour maintenir l'équilibre de l'arbre AVL après tout changement de ses nœuds . Dans une structure déséquilibrée, au moins un nœud a un facteur d'équilibre égal à 2 ou -2. Voyons comment nous pouvons équilibrer l'arbre dans ces situations.

Lorsque le facteur d'équilibre du nœud Z est 2, le sous-arbre avec Z comme racine est dans l'un de ces deux états, considérant Y comme le bon enfant de Z.

Pour le premier cas, la hauteur de l'enfant droit de Y (X) est supérieure à la hauteur de l'enfant gauche (T2). On peut facilement rééquilibrer l'arbre par une rotation gauche de Z.

Pour le second cas, la hauteur de l'enfant droit de Y (T4) est inférieure à la hauteur de l'enfant gauche (X). Cette situation nécessite une combinaison d'opérations de rotation.

Dans ce cas, nous faisons d'abord pivoter Y vers la droite, de sorte que l'arbre a la même forme que le cas précédent. Ensuite, nous pouvons rééquilibrer l'arbre par une rotation gauche de Z.

De plus, lorsque le facteur d'équilibre du nœud Z est -2, son sous-arbre est dans l'un de ces deux états, nous considérons donc Z comme la racine et Y comme son enfant gauche.

La hauteur de l'enfant gauche de Y est supérieure à celle de son enfant droit, nous équilibrons donc l'arbre avec la rotation droite de Z.

Ou dans le second cas, l'enfant droit de Y a une taille plus grande que son enfant gauche.

Donc, tout d'abord, nous la transformons en la forme précédente avec une rotation gauche de Y, puis nous équilibrons l'arbre avec la rotation droite de Z.

Jetons un coup d'œil à l'opération de rééquilibrage de notre AVLTree :

Node rebalance(Node z) { updateHeight(z); int balance = getBalance(z); if (balance > 1) { if (height(z.right.right) > height(z.right.left)) { z = rotateLeft(z); } else { z.right = rotateRight(z.right); z = rotateLeft(z); } } else if (balance  height(z.left.right)) z = rotateRight(z); else { z.left = rotateLeft(z.left); z = rotateRight(z); } } return z; }

Nous utiliserons le rééquilibrage après avoir inséré ou supprimé un nœud pour tous les nœuds du chemin du nœud modifié à la racine.

4. Insérez un nœud

Lorsque nous allons insérer une clé dans l'arborescence, nous devons localiser sa bonne position pour passer les règles BST. Nous partons donc de la racine et comparons sa valeur avec la nouvelle clé. Si la clé est plus grande, nous continuons vers la droite - sinon, nous allons vers l'enfant de gauche.

Une fois que nous avons trouvé le nœud parent approprié, nous ajoutons la nouvelle clé en tant que nœud à gauche ou à droite, en fonction de la valeur.

Après avoir inséré le nœud, nous avons un BST, mais ce n'est peut-être pas un arbre AVL. Par conséquent, nous vérifions les facteurs d'équilibre et rééquilibrons le BST pour tous les nœuds du chemin allant du nouveau nœud à la racine.

Jetons un coup d'œil à l'opération d'insertion:

Node insert(Node node, int key) { if (node == null) { return new Node(key); } else if (node.key > key) { node.left = insert(node.left, key); } else if (node.key < key) { node.right = insert(node.right, key); } else { throw new RuntimeException("duplicate Key!"); } return rebalance(node); }

Il est important de se rappeler qu'une clé est unique dans l'arborescence - aucun nœud ne partage la même clé.

La complexité temporelle de l'algorithme d'insertion est fonction de la hauteur. Puisque notre arbre est équilibré, nous pouvons supposer que la complexité temporelle dans le pire des cas est O (log (N)).

5. Supprimer un nœud

Pour supprimer une clé de l'arborescence, nous devons d'abord la trouver dans le BST.

Après avoir trouvé le nœud (appelé Z), nous devons introduire le nouveau candidat pour le remplacer dans l'arbre. Si Z est une feuille, le candidat est vide. Si Z n'a qu'un seul enfant, cet enfant est le candidat, mais si Z a deux enfants, le processus est un peu plus compliqué.

Assume the right child of Z called Y. First, we find the leftmost node of the Y and call it X. Then, we set the new value of Z equal to X ‘s value and continue to delete X from Y.

Finally, we call the rebalance method at the end to keep the BST an AVL Tree.

Here is our delete method:

Node delete(Node node, int key) { if (node == null) { return node; } else if (node.key > key) { node.left = delete(node.left, key); } else if (node.key < key) { node.right = delete(node.right, key); } else { if (node.left == null || node.right == null) { node = (node.left == null) ? node.right : node.left; } else { Node mostLeftChild = mostLeftChild(node.right); node.key = mostLeftChild.key; node.right = delete(node.right, node.key); } } if (node != null) { node = rebalance(node); } return node; }

The time complexity of the delete algorithm is a function of the height of the tree. Similar to the insert method, we can assume that time complexity in the worst case is O(log(N)).

6. Search for a Node

Searching for a node in an AVL Tree is the same as with any BST.

Start from the root of the tree and compare the key with the value of the node. If the key equals the value, return the node. If the key is greater, search from the right child, otherwise continue the search from the left child.

La complexité temporelle de la recherche est fonction de la hauteur. Nous pouvons supposer que la complexité temporelle dans le pire des cas est O (log (N)).

Voyons l'exemple de code:

Node find(int key) { Node current = root; while (current != null) { if (current.key == key) { break; } current = current.key < key ? current.right : current.left; } return current; }

7. Conclusion

Dans ce didacticiel, nous avons implémenté une arborescence AVL avec des opérations d'insertion, de suppression et de recherche.

Comme toujours, vous pouvez trouver le code sur Github.