def ajouter(arbre,valeur):
if arbre is None:
return Noeud(valeur,None,None)
if valeur < arbre.valeur:
return Noeud(arbre.valeur,
ajouter(arbre.gauche,valeur),arbre.droit)
elif valeur > arbre.valeur:
return Noeud(arbre.valeur,arbre.gauche,
ajouter(arbre.droit,valeur))
else:
return arbre
def rechercher(arbre,valeur):
if arbre is None:
return False
if valeur < arbre.valeur:
return rechercher(arbre.gauche,valeur)
elif valeur > arbre.valeur:
return rechercher(arbre.droit,valeur)
else:
return True
class ABR:
def __init__(self):
self.racine = None
def ajouter(self,val):
self.racine = ajouter(self.racine,val)
def rechercher(self,val):
return rechercher(self.racine,val)
Ajouter les méthodes suivantes
Pour visualiser l'arbre utiliser graphviz comme au TP sur les arbres
Un arbre binaire de recherche dégénéré de n sommets a une taille de n et une hauteur de n aussi
Un arbre binaire de recherche complet de taille $2^{n} - 1$ a une hauteur $n$
Le quotient, appelé ici coefficient d'équilibre, $\dfrac{\ln_2(n+1)}{h}$ mesure le fait qu'un arbre binaire de recherche soit plus ou moins complet, donc plus ou moins "équilibré" et varie entre 1 le maximum pour un arbre complet et parfaitement équilibré et $\dfrac{\ln_2(n+1)}{n}$ le minimum pour un arbre dégénéré donc le plus déséquilibré possible
Un arbre binaire est essentiellement complet si tous les niveaux sont complets à part le dernier peut-être et toutes les feuilles sont tassées à gauche
Un tas max T est un arbre binaire essentiellement complet vérifiant :
Pour tout noeud i : T[parent(i)] >= T[i]
En conséquence contrairement aux arbres binaires de recherche les valeurs des sous arbre gauche et sous arbre droit d'un noeud sont inférieures ou égales à la valeur du noeud
De plus le plus grand élément du tas max est la racine de l'arbre
Pourquoi s'intéresser aux tas ?
Exemple
On range les valeurs d'un tas dans un tableau T ainsi
Dans T[0] on met la taille de l'arbre
Pour un noeud i rangé dans T[i], le fils droit est rangé dans T[2*i] le fils gauche dans T[2*i +1]
Pour un noeud i rangé dans T[i], son père est rangé en T[i//2]
On veut implémenter une classe Tas_max avec les méthodes suivantes
On crée un tas vide mais de taille n,puis ensuite on créé le tas à partir d'une liste d'entiers de taille n
Comment ?
Un tas mémorisé dans un tableau a une propriété intéressante:
Les noeuds qui ne sont pas des feuilles ont leur indice compris entre 1 et n//2 (Justifier)
Une feuille dans la liste est forcément bien placée, par contre l'élément d'indice n//2 est peut-être trop petit et il faut le faire descendre à sa place dans le tas max, on va implémenter une fonction tamiser(i) pour faire ce travail
Donc pour créer le tas max à partir de la liste il suffit de tamiser les éléments de l'indice n//2 à 1
Voici l'interface d'un Tas_max
def echanger(tab,i,j):
temp = tab[i]
tab[i] = tab[j]
tab[j] = temp
class Tas_max:
"""
un tas max T de taille n
vérifie pour 1 <= i <= n T[parent(i)] >= T[i]
On implémente un Tas dans une liste
fils_gauche(i) = 2*i et fils_droit(i) = 2*i + 1
parent(i) = i//2
On peut construire un Tas max soit en ajoutant élément par élément
à partir d'un tas vide:
->inserer(val)
on peut aussi construire un tas max directement à partir d'un tableau de taille n:
->cree_tas_max(tableau)
"""
def __init__(self,n):
"""
n = 0 si on cree un tas max vide
sinon n est la taille du tableau
à partir duquel on crée le tas max
"""
self.taille = n
self.tab = [n]
def inserer(self,val):
self.taille += 1
self.tab.append(val)
self.percoler(self.taille)
def tamiser(self,i):
"""
la valeur du sommet i est strictement plus petite
que l'un de ses enfants
On fait descendre cette valeur dans l'arbre jusqu'à ce
qu'elle trouve sa place
complexité logarithmique
"""
pere = i
#tant que le fils gauche existe
while 2*pere <= self.taille:
max_fils = 2*pere
#on conserve l'indice du plus grand des deux
#fils gauche et droit
if max_fils < self.taille \
and self.tab[max_fils] < self.tab[max_fils+1]:
max_fils += 1
#si le noeud pere est bien placé
#on sort de la boucle
if self.tab[pere] >= self.tab[max_fils]:
break
#on échange le père et le plus grand des deux fils
echanger(self.tab, pere, max_fils)
#on continue à faire descendre la valeur
#en tamisant en i = j
pere = max_fils
def percoler(self,i):
"""
La valeur du sommet i est strictement plus grande que celle de son parent
On fait monter cette valeur dans l'arbre jusqu'à ce qu'elle retrouve
sa place
"""
enfant = i
while enfant > 1 and self.tab[enfant] >self.tab[enfant//2]:
echanger(self.tab,enfant,enfant//2)
enfant //= 2
def maximum(self):
return self.tab[1]
def cree_tas_max(self,tableau):
"""
cree un tas max de n éléments à partir d'un tableau de n éléments
Propriété : les feuilles d'un arbre binaire complété sont indexés par
E(n/2) + 1, E(n/2) + 2,...,n
Autrement dit ça ne sert à rien de tamiser les feuilles
On tamise les noeuds qui ne sont pas des feuilles dans l'ordre inverse
de E(n/2) jqà la racine
complexité linéaire
"""
for i in range(self.taille):
self.tab.append(tableau[i])
for i in range(self.taille//2,0,-1):
self.tamiser(i)
def elimine_racine(self):
"""
on échange la racine et la dernière valeur du tas
on tamise la nouvelle racine
on retourne la dernière valeur
on enlève de la liste la dernière valeur
complexité logarithmique
"""
echanger(self.tab,1,self.taille)
self.tamiser(1)
self.taille -= 1
return self.tab.pop()
def tri_tas(self):
"""
à partir d'un Tas max on trie dans l'ordre croissant le Tas max
idée:
échange le maximum (la racine) et le dernier élément
Tamise la racine
échange la racine avec l'avant dernier etc..
"""
pass
def __str__(self):
pass
Un processeur n'est disponible que pour un processus (programme en cours d'exécution)
Pendant ce temps là les autres processus sont en attente dans une file de priorités max géré par l'ordonnanceur
A chaque processus en attente est associée une clé de telle sorte que plus la clé est grande plus le processus sera prioritaire pour sortir de la file
Lorsque le processus en cours d'exécution est interrompu, soit parce qu'il a terminé son travail, soit parce qu'il est mis dans la file, l'ordonnanceur sélectionne la tâche de plus forte priorité parmi les processus en attente pour remplacer celui qui a été interrompu
On retrouve aussi les files de priorité max dans les routeurs pour gérer l'écoulement des paquets
Voici l'interface d'une file de priorités max contenant des objets ayant un attribut cle
inserer(f,x)
insère l'objet x dans la file de priorités max
max(f)
retourne l'élément de la file ayant la clé maximale
extraire_max(f)
retourne et supprime l'élément de la file ayant la clé maximale
augmenter_cle(f,x,k)
augmente la valeur de la clé de x à condition que celle ci soit supérieure ou égale à la valeur actuelle de la clé de x
class Tache:
def __init__(self,nom,cle,pos):
"""
une tache domestique a :
-un nom par exemple : "faire le repas","laver la vaisselle", etc..
-une clé : un entier de 0 à 10 plus le nombre est élévé plus la tache est
prioritaire
-une position : les objets tache sont insérés dans une file de priorité max
et vont changer de position dans le tableau implémentant la file, aussi il
faut conserver pour chaque objet sa position
"""
self.nom = nom
self.cle = cle
#pos est un entier >= 1, est l'indice du tableau implémentant la file
#de priorités max
#une tache change de position au fur et à mesure des insertions
#modifications et suppression dans la file
self.pos = pos
class File_max:
"""
on adapte le tas max vu précédemment à des objets Tache
on classe suivant la cle de l'objet tache
"""
def __init__(self,n):
self.taille = n
self.tab = [n]
def inserer(self,tache):
self.taille += 1
self.tab.append(tache)
tache.pos = self.taille
self.percoler(self.taille)
def tamiser(self,i):
"""
la valeur du sommet i est strictement plus petite
que l'un de ses enfants
On fait descendre cette valeur dans l'arbre jusqu'à ce
qu'elle trouve sa place
complexité logarithmique
"""
pass
def percoler(self,i):
"""
La valeur du sommet i est strictement plus grande que celle de son parent
On fait monter cette valeur dans l'arbre jusqu'à ce qu'elle retrouve
sa place
"""
pass
def maximum(self):
return self.tab[1].nom
def cree_tas_max(self,tableau):
"""
cree un tas max de n éléments à partir d'un tableau de n éléments
Propriété : les feuilles d'un arbre binaire complété sont indexés par
E(n/2) + 1, E(n/2) + 2,...,n
Autrement dit ça ne sert à rien de tamiser les feuilles
On tamise les noeuds qui ne sont pas des feuilles dans l'ordre inverse
de E(n/2) jqà la racine
complexité linéaire
"""
for i in range(self.taille):
self.tab.append(tableau[i])
for i in range(self.taille//2,0,-1):
self.tamiser(i)
def elimine_racine(self):
"""
retourne la racine en enlevant cette valeur du tas
on rétablit la structure de tas max
complexité logarithmique
"""
pass
def augmenter_cle(self,nom,cle2):
i = dictionnaire[nom].pos
if cle2 < self.tab[i].cle:
raise ValueError("la nouvelle clé est inférieure à l'ancienne")
else:
self.tab[i].cle = cle2
self.percoler(i)
def __str__(self):
ch =''
for i in range(1,len(self.tab)):
ch = ch + str(self.tab[i].nom)+" "
return ch
t1 = Tache("Repas",2,1)
t2 = Tache("Vaisselle",7,2)
t3 = Tache("Lessive",5,3)
t4 = Tache("Sol",1,4)
t5 = Tache("Courses",6,5)
liste_taches = [t1,t2,t3,t4,t5]
dictionnaire = {"Repas":t1,"Vaisselle":t2, "Lessive":t3,"Sol":t4, "Courses":t5 }
F = File_max(5)
F.cree_tas_max(liste_taches)
print(F)
print(F.maximum())
print(F)
print(F.elimine_racine())
print(F)
F.augmenter_cle("Sol",4)
print(F)