1.1 Définition d'un arbre

Un arbre est une structure de données non linéaire composée d'un ensemble fini de nœuds organisés de manière hiérarchique. Chaque arbre possède un nœud racine à partir duquel se ramifient les autres éléments.

1.2 Terminologie essentielle

Degré d'un nœud : nombre de sous-arbres attachés à ce nœud.

Nœud feuille : nœud dont le degré est égal à zéro.

Nœud parent : nœud qui possède des sous-arbres.

Nœud enfant : tout nœud appartenant à un sous-arbre d'un autre nœud.

Degré de l'arbre : valeur maximale des degrés de tous les nœuds.

Niveau d'un nœud : distance par rapport à la racine (la racine étant au niveau 1).

Hauteur ou profondeur : niveau maximal atteint par les nœuds de l'arbre.

Ancêtre : tout nœud situé sur le chemin entre la racine et un nœud donné.

Descendant : tout nœud situé dans le sous-arbre issu d'un nœud donné.

Forêt : ensemblle de plusieurs arbres disjoints.

1.3 Représentation d'un arbre

Pour représenter un arbre, il faut stocker à la fois les données et les relations entre les nœuds. La méthode "premier enfant - prochain frère" est particulièrement efficace :

typedef int DonneeNoeud;
typedef struct NoeudArbre
{
    DonneeNoeud donnee;
    struct NoeudArbre* premierEnfant;
    struct NoeudArbre* prochainFrere;
} NA;

2. Arbres binaires : concepts et structures ===========================================

2.1 Définition d'un arbre binaire

Un arbre binaire est un arbre où chaque nœud possède au maximum deux enfants, désignés分别是左子树 et 右子树.

2.1.1 Arbre binaire parfait

Un arbre binaire est dit parfait lorsque tous ses niveaux sont complètement remplis. Si un arbre a h niveaux, alors le nombre total de nœuds est exactement 2^h - 1.

2.1.2 Arbre binaire complet

Un arbre binaire de profondeur K avec n nœuds est complet si chacun de ses nœuds correspond à un nœud numéroté de 1 à n dans un arbre parfait de même profondeur.

2.2 Propriétés fondamentales

1. Si le niveau de la racine est 1, alors le niveau i peut contenir au maximum 2^(i-1) nœuds.
2. Un arbre de hauteur h contient au maximum 2^h - 1 nœuds.
3. Pour un arbre parfait contenant n nœuds, la hauteur h = log₂(n+1).
4. Pour un arbre complet indexé de 0 à n-1 : ``` Si i > 0 : parent(i) = (i-1)/2 Si i = 0 : c'est la racine (pas de parent) Si 2i+1 < n : enfant gauche en position 2i+1 Si 2i+2 < n : enfant droit en position 2i+2

2.3 Structures de stockage

Structure séquentielle : utilisation d'un tableau, adaptée particulièrement aux arbres complets pour éviter le gaspillage d'espace mémoire.

Structure chaînée : chaque nœud contient un champ de données et deux pointeurs vers les enfants gauche et droit.

3. Implémentation séquentielle : les tas ========================================

3.1 Intérêt de la structure séquentielle

Les arbres binaires ordinaires ne sont pas adoptés au stockage tabulaire en raison des espaces perdus. Les arbres complets, en revanche, se prêtent parfaitement à cette représentation. Un tas (heap en anglais) est une structure basée sur un arbre binaire complet stocké séquentiellement.

3.2 Définition et propriétés des tas

Définition : un tas est un tableau représentant un arbre binaire complet où tous les éléments respectent une relation d'ordre particulière. Un tas maximal possède la plus grande valeur à la racine, tandis qu'un tas minimal possède la plus petite valeur à la racine.

Propriétés :

1. Chaque nœud a une valeur supérieure (ou inférieure) à celle de ses enfants.
2. L'arbre sous-jacent est toujours complet.

3.3 Implémentation d'un tas

3.3.1 Algorithme de percolation descendante

Soit un tableau représentant un arbre complet mais non ordonné. En appliquant l'algorithme de percolation descendante à partir du dernier nœud non-feuille jusqu'à la racine, on obtient un tas valide.

int donnees[] = {1, 5, 3, 8, 7, 6};

void AjusterVersBas(TypeDonnee* tableau, int taille, int indexParent)
{
    assert(tableau);
    int borne = taille - 1;
    
    while ((indexParent * 2 + 1) <= borne)
    {
        int indexEnfant = indexParent * 2 + 1;
        
        if ((indexEnfant + 1) <= borne && tableau[indexEnfant] < tableau[indexEnfant + 1])
        {
            indexEnfant++;
        }
        
        if (tableau[indexEnfant] > tableau[indexParent])
        {
            Echanger(&tableau[indexEnfant], &tableau[indexParent]);
            indexParent = indexEnfant;
        }
        else
        {
            break;
        }
    }
}

3.3.2 Insertion dans un tas

L'insertion s'effectue en ajoutant l'élément à la fin du tableau, puis en appliquant une percolation ascendante jusqu'à respecter les propriétés du tas.

3.3.3 Suppression dans un tas

La suppression consiste à échanger la racine avec le dernier élément, puis à supprimer cet élément et appliquer une percolation descendante depuis la nouvelle racine.

3.3.4 Implémentation complète

typedef int TypeDonneeTas;
typedef struct Tas
{
    TypeDonneeTas* elements;
    int nombreElements;
    int capacite;
} Tas;

// Fonctions primitives
void InitialiserTas(Tas* t);
void DetruireTas(Tas* t);
void InsererTas(Tas* t, TypeDonneeTas valeur);
void ExtraireRacine(Tas* t);
TypeDonneeTas ConsulterRacine(Tas* t);
int ObtenirTaille(Tas* t);
int EstVide(Tas* t);

// Échange de deux valeurs
void Echanger(TypeDonneeTas* a, TypeDonneeTas* b)
{
    TypeDonneeTas temp = *a;
    *a = *b;
    *b = temp;
}

// Percolation ascendante
void AjusterVersHaut(TypeDonneeTas* tableau, int indexEnfant)
{
    assert(tableau);
    
    while (indexEnfant > 0)
    {
        int indexParent = (indexEnfant - 1) / 2;
        
        if (tableau[indexEnfant] > tableau[indexParent])
        {
            Echanger(&tableau[indexEnfant], &tableau[indexParent]);
            indexEnfant = (indexEnfant - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

// Percolation descendante (déjà définie ci-dessus)

// Initialisation du tas
void InitialiserTas(Tas* t)
{
    assert(t);
    t->elements = NULL;
    t->capacite = t->nombreElements = 0;
}

// Destruction du tas
void DetruireTas(Tas* t)
{
    assert(t);
    free(t->elements);
    t->elements = NULL;
    t->capacite = t->nombreElements = 0;
}

// Insertion d'un élément
void InsererTas(Tas* t, TypeDonneeTas valeur)
{
    assert(t);
    
    if (t->capacite == t->nombreElements)
    {
        int nouvelleCapacite = t->capacite == 0 ? 4 : t->capacite * 2;
        TypeDonneeTas* nouveau = realloc(t->elements, sizeof(TypeDonneeTas) * nouvelleCapacite);
        if (nouveau == NULL)
        {
            perror("Échec de réallocation");
            exit(-1);
        }
        t->elements = nouveau;
        t->capacite = nouvelleCapacite;
    }
    
    t->elements[t->nombreElements] = valeur;
    t->nombreElements++;
    AjusterVersHaut(t->elements, t->nombreElements - 1);
}

// Extraction de la racine
void ExtraireRacine(Tas* t)
{
    assert(t);
    assert(t->nombreElements > 0);
    
    Echanger(&t->elements[t->nombreElements - 1], &t->elements[0]);
    t->nombreElements--;
    AjusterVersBas(t->elements, t->nombreElements, 0);
}

// Consultation de la racine
TypeDonneeTas ConsulterRacine(Tas* t)
{
    assert(t);
    return t->elements[0];
}

// Vérification si le tas est vide
int EstVide(Tas* t)
{
    assert(t);
    return t->nombreElements == 0;
}

// Obtenir la taille du tas
int ObtenirTaille(Tas* t)
{
    assert(t);
    return t->nombreElements;
}

// Affichage du tas
void AfficherTas(Tas* t)
{
    assert(t);
    for (int i = 0; i < t->nombreElements; i++)
    {
        printf("%d ", t->elements[i]);
    }
    printf("\n");
}

// Construction d'un tas à partir d'un tableau
void ConstruireTas(Tas* t, TypeDonneeTas* donnees, int nombre)
{
    assert(t);
    
    t->elements = malloc(sizeof(TypeDonneeTas) * nombre);
    if (t->elements == NULL)
    {
        perreur("Échec d'allocation");
        exit(-1);
    }
    
    t->capacite = t->nombreElements = nombre;
    memcpy(t->elements, donnees, nombre * sizeof(TypeDonneeTas));
    
    for (int i = (nombre - 2) / 2; i >= 0; i--)
    {
        AjusterVersBas(t->elements, nombre, i);
        AfficherTas(t);
    }
}

3.4 Applications des tas

3.4.1 Tri par tas

Le tri par tas s'effectue en deux étapes :

1. Construction du tas
   - Ordre croissant : construire un tas maximal
   - Ordre décroissant : construire un tas minimal

void TrierParTas(TypeDonneeTas* tableau, int taille)
{
    assert(tableau);
    
    // Construction du tas maximal
    for (int i = (taille - 2) / 2; i >= 0; i--)
    {
        AjusterVersBas(tableau, taille, i);
    }
    
    // Extraction successive des éléments
    while (taille >= 1)
    {
        Echanger(&tableau[0], &tableau[taille - 1]);
        taille--;
        AjusterVersBas(tableau, taille, 0);
    }
}

3.4.2 Problème des K meilleurs éléments

Ce problème consiste à trouver les K éléments les plus grands ou les plus petits dans un ensemble de données volumineux.

1. Utiliser les K premiers éléments pour construire un tas
   - Pour les K plus grands : construire un tas minimal
   - Pour les K plus petits : construire un tas maximal

2. Comparer chaque élément restant avec la racine du tas
   et remplacer si la condition n'est pas satisfies

4. Structure chaînée des arbres binaires ========================================

Cette section sera développée ultérieurement.