Arbre binaire de recherche

Classe ABR


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

Equilibre d'un ABR

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

Tas

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

File de priorité

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