🍇 Tas binaire

Sommaire

• Définition
  • Exemple
• Construction d'une classe Tas
  • Implémentation avec un tableau
  • La classe Tas

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

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.

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 ...

La classe Tas

On propose de stocker :

• Les données dans une liste dynamique Python, avec l'élément d'indice $0$ mis à None.
• La taille dans un attribut stocké à 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 !

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.

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, x):

        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")
        é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