Arbres

1.1 Concepts et Structure des Arbres

Un arbre est une structure de données non linéaire composée de N (N ≥ 0) nœuds finis formant une hiérarchie. Sa structure rappelle celle d'un arbre inversé, avec la racine en haut et les feuilles en bas.

• Il existe un nœud spécial appelé racine, qui n'a pas de nœud parent.
• Tous les autres nœuds sont divisés en M (M > 0) ensembles disjoints T1, T2, ..., Tm. Chaque ensemble Ti est lui-même une sous-arborescence avec une structure similaire à celle d'un arbre.
• Chaque sous-arborescence a une racine avec exactement un nœud parent et zéro ou plusieurs nœuds enfants.
• La définition de l'arbre est donc récursive.

Important : Les sous-arborescences ne doivent pas se chevaucher ; sinon, il s'agirait d'un graphe.

• Chaque nœud, à l'exception de la racine, a exactement un parenet.
• Un arbre avec N nœuds possède N-1 arêtes.

1.2 Terminologie des Arbres

• Parent/Nœud parent : Un nœud qui a des nœuds enfants. Par exemple, A est le parent de B.
• Enfant/Nœud enfant : La racine d'une sous-arborescence d'un nœud donné. Par exemple, B est un enfant de A.
• Degré d'un nœud : Le nombre d'enfants d'un nœud. Par exemple, A a un degré de 6, F a un degré de 2, et K a un degré de 0.
• Degré d'un arbre : Le degré maximal parmi tous les nœuds de l'arbre. Dans l'exemple, le degré de l'arbre est 6.
• Feuille/Nœud terminal : Un nœud dont le degré est 0. Par exemple, B, C, H, I sont des feuilles.
• Nœud de branche/Nœud non terminal : Un nœud dont le degré n'est pas 0. Par exemple, D, E, F, G sont des nœuds de branche.
• Frères/Sœurs : Des nœuds qui partagent le même parent. Par exemple, B et C sont frères.
• Niveau d'un nœud : En partant de la racine au niveau 1, les enfants de la racine sont au niveau 2, et ainsi de suite.
• Hauteur/Profondeur d'un arbre : Le niveau maximal atteint par un nœud dans l'arbre. L'arbre a une hauteur de 4.
• Ancêtre d'un nœud : Tous les nœuds rencontrés sur le chemin de la racine à ce nœud. A est l'ancêtre de tous les nœuds.
• Chemin : Une séquence de nœuds allant d'un nœud quelconque à un autre en suivant les liens parent-enfant. Le chemin de A à Q est A-E-J-Q. Le chemin de H à Q est H-D-A-E-J-Q.
• Descendant : Tout nœud dans la sous-arborescence dont un nœud donné est la racine. Tous les nœuds sont des descendants de A.
• Forêt : Une collection de M (M > 0) arbres disjoints.

1.3 Représentation des Arbres

Une méthode courante est la représentation par liste d'enfants et de frères :

struct TreeNode {
    struct Node* first_child; // Pointeur vers le premier enfant
    struct Node* next_sibling; // Pointeur vers le frère suivant
    int data; // Données du nœud
};

Arbres Binaires

2.1 Concepts et Structure des Arbres Binaires

L'arbre binaire est une structure couramment utilisée. C'est un ensemble fini de nœuds qui est soit vide, soit composé d'une racine et de deux sous-arbres binaires distincts appelés sous-arbre gauche et sous-arbre droit.

Les caractéristiques d'un arbre binaire sont :

1. Aucun nœud n'a un degré supérieur à 2.
2. Les sous-arbres gauche et droit sont distincts et leur ordre est important. Par conséquent, un arbre binaire est un arbre ordonné.

Un arbre binaire peut être composé des situations suivantes :

2.2 Arbres Binaires Spéciaux

Arbre Binaire Complet

Un arbre binaire est dit complet si chaque niveau, à l'exception potentiellement du dernier, est entièrement rempli, et si tous les nœuds du dernier niveau sont autant que possible alignés à gauche.

Arbre Binaire Parfait

Un arbre binaire est parfait si tous ses niveaux sont entièrement remplis. Si un arbre binaire a une profondeur K et contient 2K - 1 nœuds, alors c'est un arbre binaire parfait.

Propriétés des Arbres Binaires

• Pour un arbre binaire de profondeur h (la racine étant au niveau 1), le nombre maximal de nœuds au niveau i est 2i-1.
• La profondeur d'un arbre binaire avec h niveaux est au maximum 2h - 1.
• La profondeur d'un arbre binaire parfait avec n nœuds est log2(n + 1).

2.3 Structure de Stockage des Arbres Binaires

Les arbres binaires peuvent être stockés en utilisant soit une structure séquentielle (tableau), soit une structure chaînée (pointeurs).

La structure séquentielle est généralemant implémentée à l'aide d'un tableau. Elle est particulièrement efficace pour représenter les arbres binaires complets, car elle évite le gaspillage d'espace. Pour les arbres binaires non complets, la structure séquentielle peut entraîner une perte d'espace.

Les tas, qui sont un type spécial d'arbre binaire, sont souvent implémentés en utilisant un tableau pour une structure séquentielle. Il est important de noter que le "tas" en tant que structure de données est différent du "tas" en tant que région de mémoire dans la gestion de la mémoire d'un système d'exploitation.

Implémentation d'un Arbre Binaire Séquentiel (Tas)

Un tas est un arbre binaire spécial qui utilise un tableau pour le stockage séquentiel. Il possède les propriétés des arbres binaires, ainsi que d'autres caractéristiques spécifiques.

3.1 Concepts et Structure d'un Tas

Un tas est une structure de données basée sur un arbre binaire complet où les nœuds satisfont une certaine propriété d'ordre.

• Tas Minimum (Min-Heap) : La valeur de chaque nœud est inférieure ou égale à la valeur de ses enfants. La racine contient la plus petite valeur.
• Tas Maximum (Max-Heap) : La valeur de chaque nœud est supérieure ou égale à la valeur de ses enfants. La racine contient la plus grande valeur.

Propriétés d'un tas binaire complet stocké dans un tableau (indexation à partir de 0) :

• Pour un nœud à l'index i (où i > 0), son parent est à l'index (i - 1) / 2.
• Pour un nœud à l'index i :
  • Son enfant gauche est à l'index 2 * i + 1 (s'il existe).
  • Son enfant droit est à l'index 2 * i + 2 (s'il existe).

3.2 Implémentation d'un Tas (Exemple de Tas Minimum)

Heap.h

#include &ltstdio.h>
#include &ltstdlib.h>
#include &ltassert.h>
#include &ltstdbool.h>

typedef int HPDataType;

typedef struct Heap {
    HPDataType* arr; // Tableau pour stocker les éléments du tas
    int size;        // Nombre actuel d'éléments dans le tas
    int capacity;    // Capacité totale du tableau
} HP;

// Initialise le tas
void HPInit(HP* php);

// Détruit le tas et libère la mémoire
void HPDestroy(HP* php);

// Ajoute un élément au tas
void HPPush(HP* php, HPDataType x);

// Supprime l'élément racine du tas
void HPPop(HP* php);

// Retourne l'élément racine du tas (sans le supprimer)
HPDataType HPTop(HP* php);

// Vérifie si le tas est vide
bool HPEmpty(HP* php);

Heap.c

Initialisation par défaut du tas

void HPInit(HP* php) {
    assert(php);
    php->arr = NULL;
    php->capacity = php->size = 0;
}

Destruction du tas

void HPDestroy(HP* php) {
    assert(php);
    if (php->arr) {
        free(php->arr);
        php->arr = NULL;
        php->capacity = 0; // Réinitialiser la capacité
        php->size = 0;     // Réinitialiser la taille
    }
}

Insertion dans le tas (Réajustement vers le haut)

Lors de l'insertion d'un nouvel élément, celui-ci est d'abord placé à la fin du tableau. Si la propriété du tas est violée, l'élément est déplacé vers le haut jusqu'à ce que la propriété soit rétablie.

// Fonction utilitaire pour échanger deux entiers
void swap(int* x, int* y) {
    int z = *x;
    *x = *y;
    *y = z;
}

// Réajuste le tas vers le haut après une insertion
void AdjustUp(HPDataType* arr, int child_index) {
    int parent_index = (child_index - 1) / 2;

    while (child_index > 0) {
        // Pour un tas minimum, si l'enfant est plus petit que le parent
        if (arr[child_index] < arr[parent_index]) {
            swap(&arr[child_index], &arr[parent_index]);
            child_index = parent_index; // Passer au parent
            parent_index = (child_index - 1) / 2;
        } else {
            break; // La propriété du tas est satisfaite
        }
    }
}

void HPPush(HP* php, HPDataType x) {
    assert(php);

    // Vérifier si une extension de capacité est nécessaire
    if (php->size == php->capacity) {
        int new_capacity = (php->capacity == 0) ? 4 : 2 * php->capacity;
        HPDataType* tmp = (HPDataType*)realloc(php->arr, new_capacity * sizeof(HPDataType));

        if (tmp == NULL) {
            perror("realloc failed!");
            exit(1);
        }
        php->arr = tmp;
        php->capacity = new_capacity;
    }

    // Insérer le nouvel élément à la fin
    php->arr[php->size] = x;
    php->size++;

    // Réajuster le tas vers le haut
    AdjustUp(php->arr, php->size - 1);
}

Suppression de l'élément racine (Réajustement vers le bas)

Pour supprimer l'élément racine, on l'échange avec le dernier élément du tas. Ensuite, le dernier élément est supprimé (taille réduite). L'élément qui est maintenant à la racine (celui qui était le dernier) peut violer la propriété du tas. On utilise alors l'algorithme de réajustement vers le bas pour le replacer à la bonne posision.

// Réajuste le tas vers le bas après la suppression de la racine
void AdjustDown(HPDataType* arr, int parent_index, int heap_size) {
    int left_child_index = 2 * parent_index + 1;

    while (left_child_index < heap_size) {
        int right_child_index = left_child_index + 1;
        int smaller_child_index = left_child_index; // Assumer que l'enfant gauche est le plus petit

        // Trouver l'enfant le plus petit s'il existe
        if (right_child_index < heap_size && arr[right_child_index] < arr[left_child_index]) {
            smaller_child_index = right_child_index;
        }

        // Si l'enfant le plus petit est plus petit que le parent
        if (arr[smaller_child_index] < arr[parent_index]) {
            swap(&arr[smaller_child_index], &arr[parent_index]);
            // Continuer le réajustement à partir du nœud enfant échangé
            parent_index = smaller_child_index;
            left_child_index = 2 * parent_index + 1;
        } else {
            break; // La propriété du tas est satisfaite
        }
    }
}

void HPPop(HP* php) {
    assert(php && php->size); // S'assurer que le tas n'est pas vide

    // Échanger la racine avec le dernier élément
    swap(&php->arr[0], &php->arr[php->size - 1]);

    // Réduire la taille du tas (l'ancien dernier élément est maintenant "supprimé")
    php->size--;

    // Réajuster le tas vers le bas à partir de la racine
    AdjustDown(php->arr, 0, php->size);
}

Test de l'implémentation

#include "Heap.h"

void HeapTest() {
    HP hp;
    HPInit(&hp);

    int initial_elements[] = {17, 25, 60, 54, 30, 70};
    int num_elements = sizeof(initial_elements) / sizeof(initial_elements[0]);

    for (int i = 0; i < num_elements; i++) {
        HPPush(&hp, initial_elements[i]);
    }

    // Exemple de suppression de l'élément racine
    if (!HPEmpty(&hp)) {
        HPPop(&hp);
    }

    // ... d'autres tests peuvent être ajoutés ici ...

    HPDestroy(&hp); // Nettoyage de la mémoire
}

int main() {
    HeapTest();
    return 0;
}

3.3 Applications des Tas

Tri par Tas (Heap Sort)

Le tri par tas est un algorithme de tri efficace basé sur la structure de données tas.

Méthode 1 : Construction du tas puis extraction

Cette méthode consiste à construire un tas à partir d'un tableau donné, puis à extraire les éléments un par un pour obtenir le tableau trié.

// Nécessite la structure de données Heap définie précédemment
// Complexité spatiale : O(N) pour le tas
void HeapSort_Method1(int* arr_to_sort, int n) {
    HP heap;
    HPInit(&heap);

    // Construire le tas
    for (int i = 0; i < n; i++) {
        HPPush(&heap, arr_to_sort[i]);
    }

    // Extraire les éléments dans l'ordre
    int i = 0;
    while (!HPEmpty(&heap)) {
        arr_to_sort[i++] = HPTop(&heap); // Obtenir le minimum (pour un min-heap)
        HPPop(&heap); // Supprimer le minimum
    }
    HPDestroy(&heap); // Libérer la mémoire du tas
}

Méthode 2 : Tri par tas en place

Cette méthode réutilise le tableau d'origine pour construire le tas, puis effectue les échanges pour trier le tableau directement.

Pour un tri ascendant, on construit un tas maximum. Pour un tri descendant, on construit un tas minimum.

// Fonction utilitaire pour échanger deux entiers (si pas déjà définie)
void Swap(int* x, int* y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

// Fonction d'ajustement vers le bas pour un tableau donné (utilisée lors du tri)
// heap_size est la taille effective du tas à considérer dans le tableau
void AdjustDown_ForSort(int* arr, int heap_size, int parent_index) {
    int left_child_index = 2 * parent_index + 1;

    while (left_child_index < heap_size) {
        int right_child_index = left_child_index + 1;
        int smaller_or_larger_child_index = left_child_index; // Pour Max Heap: plus grand, pour Min Heap: plus petit

        // Trouver l'enfant le plus approprié (plus grand pour Max Heap, plus petit pour Min Heap)
        // Supposons ici qu'on veut un tri ascendant, donc on construit un Max Heap d'abord.
        // Pour un tri ascendant, on cherche l'enfant le plus grand.
        if (right_child_index < heap_size && arr[right_child_index] > arr[left_child_index]) {
            smaller_or_larger_child_index = right_child_index;
        }

        // Si le parent est plus petit que l'enfant le plus grand (pour Max Heap)
        if (arr[parent_index] < arr[smaller_or_larger_child_index]) {
            Swap(&arr[parent_index], &arr[smaller_or_larger_child_index]);
            parent_index = smaller_or_larger_child_index;
            left_child_index = 2 * parent_index + 1;
        } else {
            break;
        }
    }
}

// Tri par tas en place (pour un tri ascendant)
// Complexité temporelle : O(N log N)
void HeapSort_Method2(int* arr, int n) {
    // 1. Construire un Max Heap à partir du tableau O(N)
    // On commence par le dernier nœud parent et on descend jusqu'à la racine
    for (int i = (n / 2) - 1; i >= 0; --i) {
        AdjustDown_ForSort(arr, n, i);
    }

    // 2. Extraire les éléments un par un du tas
    // On échange la racine (le plus grand élément) avec le dernier élément,
    // puis on réduit la taille du tas et on réajuste.
    int end = n - 1;
    while (end > 0) {
        Swap(&arr[0], &arr[end]); // Mettre le plus grand élément à sa position finale
        AdjustDown_ForSort(arr, end, 0); // Réajuster le tas réduit
        --end;
    }
}

La suite à venir...