TDA Tableau Associatif (map)

Un tableau associatif (ou dictionnaire) est un type de données abstrait associant des clefs uniques à des valeurs.

C'est une généralisation de la notion de tableau à des indices de type arbitraire, pas nécessairement consécutifs

Les opérations usuellement fournies sont :

  • ajouter - associer une nouvelle valeur à une nouvelle clef
  • modifier - associer une nouvelle valeur à une ancienne clef
  • supprimer - supprimer une clef et la valeur associée
  • chercher - déterminer la valeur associée à une clef, si elle existe.

La mise en oeuvre de ce TDA peut se faire efficacement au moyen

  • d'arbres binaires de recherche
  • de tables de hachage (ASD2)

L'utilisation d'un ABR offre en plus le maintien trié des paires clef/valeur par ordre de clef croissante. Les opérations sur un ABR équilibré sont $\Theta( \log n )$ en moyenne et dans le pire des cas.

Les opérations sur une table de hachage ont une complexité moyenne $\Theta(1)$, mais $\Theta(n)$ dans le pire des cas.

Mise en oeuvre

Nous utilisons ici un arbre binaire de recherche dont les noeuds stockent des attributs clef et valeur en plus des liens vers les autres noeuds.

In [2]:
class Noeud:
    
    def __init__(self,clef,valeur):
        
        self.clef = clef
        self.valeur = valeur
        
        self.gauche = None
        self.droite = None

La fonction d'insertion sert à la fois à l'ajout et à la modification

In [3]:
def inserer(R,clef,valeur):
    
    if R == None: # ajouter une nouvelle clef
        R = Noeud(clef,valeur)  
        
    elif clef < R.clef: 
        R.gauche = inserer(R.gauche,clef,valeur)    
    elif clef > R.clef: 
        R.droite = inserer(R.droite,clef,valeur)
        
    else:  # modifier la valeur associée
        R.valeur = valeur  
        
    return R

La fonction de recherche retourne le noeud trouvé ou None

In [4]:
def chercher(R,clef):
    if R == None:      return None      
    elif clef < R.clef: return chercher(R.gauche,clef)    
    elif clef > R.clef: return chercher(R.droite,clef)
    else:              return R

Nous y ajoutons une fonction de création de l'arbre à partir d'une liste.

In [5]:
def creer_ABR(T):
    R = None
    for (clef,valeur) in T: 
        R = inserer(R,clef,valeur)
    return R

Ainsi qu'une fonction de parcours par ordre croissant

In [6]:
def to_string(R):
    s = ""
    if R:
        s += to_string(R.gauche)
        s += "{}: {} \n".format(R.clef,R.valeur)
        s += to_string(R.droite)
    return s

Ces fonctions suffisent à mettre en oeuvre un tableau associatif simple (sans suppression)

In [7]:
class TreeMap:
    
    def __init__(self,T = []):
        self.R = creer_ABR(T)
        
    def __setitem__(self,clef,valeur):
        self.R = inserer(self.R,clef,valeur)
        
    def __getitem__(self,clef):
        n = chercher(self.R,clef)
        if n: return n.valeur
        else: raise IndexError()
            
    def __str__(self):
        return to_string(self.R)
In [11]:
# Testons notre classe 

M = TreeMap()

# Ajouts 

M["Hello"] = 1
M["World"] = 2
M["and"] = 3
M["ASD"] = 4
M["students"] = 5


# Parcours croissant 

print(M)

ASD: 4 
Hello: 1 
World: 2 
and: 3 
students: 5
In [12]:
# Recherche 

print(M["Hello"])

1
In [13]:
# Modification
    
M["Hello"] = 42   

# Parcours croissant 

print(M)

ASD: 4 
Hello: 42 
World: 2 
and: 3 
students: 5

ASD1 Notebooks on GitHub.io

© Olivier Cuisenaire, 2018