Aller au contenu

🍇Tas binaire⚓︎

Hors programme ?

L'étude des tas est hors programme en cours, mais cela constitue un lot d'exercices simples sur les arbres binaires. Considérer donc ce chapitre non pas comme un chapitre de cours, mais un chapitre d'exercices sur les arbres binaires. Excellents exercices et très utiles !

On considère des arbres binaires particuliers, avec des données toutes de même type, un type qui possède une relation d'ordre. Par exemple : des entiers, on peut les comparer.

Définition⚓︎

Un tas binaire (ou tas-max) est un arbre binaire presque complet à gauche, tel que s'il est non vide :

  • le nœud racine porte une donnée supérieure ou égale à celle des autres nœuds ;
  • ses deux sous-arbres sont aussi des tas.

Un tas-min est une structure équivalente, mais avec la racine portant une valeur inférieure ou égale à celles de sa filiation.

La structure de tas binaire est utilisée dans un algorithme de tri efficace (le tri par tas), dans la gestion des files de priorité, etc.

Exemple⚓︎

expressionTas-max110281->2341->3452->4562->5623->6713->7844->8924->91035->10115->11

expressionTas-min11221->2351->3422->4532->5663->67103->7844->8984->91045->10115->11

Construction d'une classe Tas⚓︎

Implémentation avec un tableau⚓︎

Tout arbre binaire presque complet gauche peut être implémenté en stockant les données dans un tableau.

  • L'indice \(0\) ne stocke pas de données, ou alors peut servir à stocker la taille en cours du tableau.
  • Si l'arbre est non vide, sa racine est stockée à l'indice \(1\).
  • Pour tout nœud stocké à l'indice \(i\), ses enfants sont stockés aux indices \(2i\) et \(2i+1\).

Par exemple, le tas-max précédent peut être stocké dans le tableau :

Indice \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\)
Élément \(10\) \(8\) \(4\) \(5\) \(6\) \(2\) \(1\) \(4\) \(2\) \(3\)

Ce tableau correspond à une lecture lors d'un parcours en largeur.

Exercice 1

Donner le tableau correspondant au tas-min donné en exemple.

Réponse
Indice \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\)
Élément \(1\) \(2\) \(5\) \(2\) \(3\) \(6\) \(10\) \(4\) \(8\) \(4\)

Exercice 2 : Compléter ...

Cette implémentation permet de se déplacer facilement à partir d'un nœud.

  • L'enfant gauche d'un nœud stocké à l'indice \(i\) est stocké à l'indice ...
  • L'enfant droite d'un nœud stocké à l'indice \(i\) est stocké à l'indice ...
  • Le parent d'un nœud stocké à l'indice \(i > 1\) est stocké à l'indice ...
Réponse
  • L'enfant gauche d'un nœud stocké à l'indice \(i\) est stocké à l'indice \(2i\).
  • L'enfant droite d'un nœud stocké à l'indice \(i\) est stocké à l'indice \(2i+1\).
  • Le parent d'un nœud stocké à l'indice \(i > 1\) est stocké à l'indice \(i//2\).

Rédaction

Quels sont les avantages à utiliser un tel tableau comme structure de base pour le tas ?

Réponse

Les données sont stockées serrées (pas d'adresse à gérer), et il est facile de trouver les indices du parent ou des enfants.

La classe Tas⚓︎

On propose de stocker :

  • Les données dans une liste dynamique Python, avec l'élément d'indice \(0\) mis à None. Nous l'utiliserons en interne comme une pile.
  • La taille dans un attribut stocké à part.

Mais pourquoi à part ?

La taille est souvent stockée à l'indice \(0\). Nous ne le ferons pas, en effet, la taille est un entier, mais les éléments du tas ne le sont peut-être pas ! Si les éléments du tas sont des entiers, alors pourquoi pas.

On propose les méthodes :

  • Initialisation, qui fait suite au constructeur ;
  • .est_vide(self) qui indique la vacuité du tas, ou non ;
  • .ajout(self, x) qui ajoute un élément au tas (en respectant les règles) ;
  • .extrait(self) qui supprime et renvoie l'élément à la racine, si l'arbre est non vide, en réagençant le tas en respectant les règles.
🐍 Script Python
class Tas:
    """ Implémentation de la structure de données tas-max
    """
    def __init__(self):
        self.__tas = [None]
        self.__taille = 0

    def _échange(self, i, j):
        tmp = self.__tas[i]
        self.__tas[i] = self.__tas[j]
        self.__tas[j] = tmp

    def __str__(self):
        return str(self.__tas)

    def est_vide(self):
        return (self.__tas == [None]) and (self.__taille == 0)

    def ajoute(self, x):
        self.__taille += 1
        self.__tas.append(x)
        i = self.__taille
        parent_i = i // 2
        while (i > 1) and self.__tas[parent_i] < self.__tas[i]:
            self._échange(i, parent_i)
            i = parent_i
            parent_i = i // 2

    def extrait(self):

        def est_valide(i):
            """Indique si la règle est respectée pour le nœud stocké en i
            """
            if 2*i > self.__taille:
                # On est sur une feuille
                return True
            if 2*i == self.__taille:
                # Le nœud n'a qu'un enfant à gauche
                return self.__tas[i] >= self.__tas[2*i]
            # Le nœud possède deux enfant, à gauche, à droite
            return     self.__tas[i] >= self.__tas[2*i] \
                   and self.__tas[i] >= self.__tas[2*i + 1]

        if self.est_vide():
            raise ValueError("Tas vide")
        if self.__taille == 1:
            self.__taille = 0
            return self.__tas.pop()
        élément = self.__tas[1] # l'élément à renvoyer
        # On place à la racine le dernier élément
        self.__tas[1] = self.__tas.pop()
        self.__taille -= 1
        # On va le remettre à une place qui respecte la règle
        i = 1
        while not est_valide(i):
            if (2*i == self.__taille) \
               or (self.__tas[2*i] > self.__tas[2 * i + 1]):
                    j = 2 * i     # vers l'enfant gauche
            else:
                j = 2 * i + 1 # vers l'enfant droite
            self._échange(i, j)
            i = j
        return élément

if __name__ == '__main__':
    # tests
    test = Tas()

    # test est_vide
    assert test.est_vide()

    # test un ajoute/extrait
    univers = 42
    test.ajoute(univers)
    élément = test.extrait()
    assert élément == univers
    assert test.est_vide()

    # test plusieurs ajout/extrait
    #  dans l'ordre
    premiers = [2, 3, 5, 7, 11]

    for élément in premiers:
        test.ajoute(élément)
    assert [test.extrait()
            for élément in premiers] == premiers[::-1]
    assert test.est_vide()

    #  dans le désordre
    from random import shuffle
    bazar = premiers[:]
    for _ in range(100):
        shuffle(bazar)
        for élément in bazar:
            test.ajoute(élément)
        shuffle(bazar)
        assert [test.extrait()
                for élément in bazar] == premiers[::-1]
        assert test.est_vide()