Université Bordeaux 1

Licence Semestre 3  - Algorithmes et structures de données 1

Dernière mise à jour effectuée le 23 Juin 2014


Arbre 2-3 et B Arbres


  1. 2-3 Arbres
  2. Définition 10.1.Soit k un entier. On appelle k-noeud un noeud qui a k fils.
    Définition 10.2.Un arbre 2-3 est un arbre équilibré éventuellement vide tel que tout noeud à 2 ou 3 fils et vérifiant :
    • la valeur des clés est contenue dans les feuilles
    • un 2-noeud contient la valeur r
      • le fils gauche donne accès à des valeurs inférieures ou égales à r
      • le fils droit à des valeurs supérieures strictement à r
    • un 3-noeud contient deux valeurs r et s,
      • le fils gauche donne accès à des valeurs inférieures ou égales à r
      • le fils du milieu donne accès à des valeurs dans l'intervalle ]r,s]
      • le fils droit à des valeurs supérieures strictement à s

    Insertion

    L'insertion se fait sur une feuille de l'arbre. Un arbre 2-3 s'étire donc en hauteur par la racine.

    Suppression

    C'est une feuille de l'arbre que l'on supprime. Elle a un père p

  3. (a-b)-arbres
  4. Définition 10.3.Un (a,b)- arbre est un arbre étiquetté qui vérifie :
    • La racine est une feuille ou possède au moins 2 fils.
    • Tout noeud interne possède entre a et b fils.
    • Toutes les feuilles sont au même niveau
    De plus
    • Les noeuds internes sont de la forme (a0, k1, a1, k2,..., kb-1, ab-1) avec ai pointeur vers un sous arbre et ki sont des valeurs,
    • k1 < k2 <... < kb
    • les valeurs des feuilles du sous arbre pointé par ai-1 sont inférieures ou égales à ki,
    • les valeurs des feuilles du sous arbre pointé par ai+1 sont supérieures à ki,
    Les 2-3 arbres sont des cas particuliers de a-b arbres. Le plus souvent on choisit b=2a-1. On parle alors de B-arbres. Une variante consiste a autoriser les clés dans les noeuds internes.
    (voir des exemples)

  5. Structure de données et primitives
  6. Les B-arbres sont des containeurs. Dans les B-arbres, il est important de garder des acccès rapides aux fils et de remonter aisément dans l'arbre. On utilise la structure suivante.
    sommet=^cellule;
    celluleUnitaire=structure
            clé:objet;
            fils:sommet;
    finstructure
    
    cellule=structure
              premierFils:sommet;
              autreFils:tableau[a..b] de celluleUnitaire
              frere:sommet;
              pere:sommet;
    finstructure;