🍇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⚓︎
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.
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()