Scribd
Importer
7 vues3 pages

Implémentation d'un arbre AVL en C

Ce document présente une implémentation d'un arbre AVL en C, incluant la définition de la structure de nœud et des fonctions pour insérer des éléments tout en maintenant l'équilibre de l'arbre. Les rotations gauche et droite sont utilisées pour rééquilibrer l'arbre après les insertions. Un exemple d'insertion et d'affichage des éléments de l'arbre en ordre croissant est également fourni.

Transféré par

Souha Lassoued
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats TXT, PDF, TXT ou lisez en ligne sur Scribd
7 vues3 pages

Implémentation d'un arbre AVL en C

Ce document présente une implémentation d'un arbre AVL en C, incluant la définition de la structure de nœud et des fonctions pour insérer des éléments tout en maintenant l'équilibre de l'arbre. Les rotations gauche et droite sont utilisées pour rééquilibrer l'arbre après les insertions. Un exemple d'insertion et d'affichage des éléments de l'arbre en ordre croissant est également fourni.

Transféré par

Souha Lassoued
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats TXT, PDF, TXT ou lisez en ligne sur Scribd

#include <stdio.

h>
#include <stdlib.h>

// D�finition de la structure de n�ud


typedef struct Node {
int key;
struct Node* left;
struct Node* right;
int height;
} Node;

// D�finition du type AVL comme pointeur sur Node


typedef Node* AVL;

// Fonction pour obtenir la hauteur d'un n�ud


int height(AVL A) {
if (A == NULL)
return 0;
else
return A->height;
}

// Fonction pour obtenir le maximum entre deux valeurs


int max(int a, int b) {
if (a > b)
return a;
else
return b;
}

// Cr�ation d'un nouveau n�ud


AVL createNode(int e) {
AVL A = (AVL)malloc(sizeof(Node));
A->key = e;
A->left = NULL;
A->right = NULL;
A->height = 1; // Hauteur initiale d'un n�ud
return A;
}

// Rotation droite
AVL rotateRight(AVL A) {
AVL B = A->left;
AVL T2 = B->right;

// Effectuer la rotation
B->right = A;
A->left = T2;

// Mettre � jour les hauteurs


A->height = max(height(A->left), height(A->right)) + 1;
B->height = max(height(B->left), height(B->right)) + 1;

return B; // Nouveau n�ud racine


}

// Rotation gauche
AVL rotateLeft(AVL A) {
AVL B = A->right;
AVL T2 = B->left;

// Effectuer la rotation
B->left = A;
A->right = T2;

// Mettre � jour les hauteurs


A->height = max(height(A->left), height(A->right)) + 1;
B->height = max(height(B->left), height(B->right)) + 1;

return B; // Nouveau n�ud racine


}

// Calculer le facteur d'�quilibre d'un n�ud


int getBalance(AVL A) {
if (A == NULL)
return 0;
else
return height(A->left) - height(A->right);
}

// Insertion d'un �l�ment dans l'arbre AVL


AVL insert(AVL A, int e) {
// �tape 1 : Insertion standard dans un arbre binaire de recherche
if (A == NULL)
return createNode(e);

if (e < A->key)
A->left = insert(A->left, e);
else if (e > A->key)
A->right = insert(A->right, e);
else
return A; // Les cl�s en double ne sont pas autoris�es

// �tape 2 : Mettre � jour la hauteur de l'anc�tre


A->height = max(height(A->left), height(A->right)) + 1;

// �tape 3 : Obtenir le facteur d'�quilibre


int balance = getBalance(A);

// Si le n�ud devient d�s�quilibr�, effectuer les rotations n�cessaires

// Cas 1 : Gauche-Gauche
if (balance > 1 && e < A->left->key)
return rotateRight(A);

// Cas 2 : Droite-Droite
if (balance < -1 && e > A->right->key)
return rotateLeft(A);

// Cas 3 : Gauche-Droite
if (balance > 1 && e > A->left->key) {
A->left = rotateLeft(A->left);
return rotateRight(A);
}

// Cas 4 : Droite-Gauche
if (balance < -1 && e < A->right->key) {
A->right = rotateRight(A->right);
return rotateLeft(A);
}

return A; // Retourner le pointeur du n�ud inchang�


}

// Affichage de l'arbre en parcours In-Order


void inOrder(AVL A) {
if (A != NULL) {
inOrder(A->left);
printf("%d ", A->key);
inOrder(A->right);
}
}

// Programme principal
int main() {
AVL root = NULL; // D�clarer un arbre AVL

// Insertion de cl�s dans l'arbre AVL


root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 5);
root = insert(root, 40);
root = insert(root, 11);
root = insert(root, 25);

// Afficher l'arbre en ordre croissant


printf("Arbre AVL en parcours In-Order : ");
inOrder(root);
printf("\n");

return 0;
}

Vous aimerez peut-être aussi