Planche : 1


Ensembles

Planche : 2


Réalisation des ensembles avec les listes

On peut représenter le ensembles par des listes.

Il suffit de maintenir la condition :

Les éléments d’un ensemble sont deux à deux distincts.

Il faut donc pouvoir déterminer l’égalité de deux éléments.

Dans la suite, nos éléments sont des int, mais cela pourrait facilement être des objets quelconques (par redéfinition de la méthode equals des Object).


Planche : 3


La classe des listes (d’entiers)

Air connu…

class List {
  int val ;
  List next ;

  List (int valList next) {
    this.val = val ; this.next = next ;
  }
}

Planche : 4


Opérations élémentaires

Planche : 5


Opération ensembliste : union

Planche : 6


Bilan des coût

Quel est alors le coût asymptotique dans le cas le pire :


Planche : 7


Une idée

Normaliser les listes : représenter un ensemble par la liste triées (ordre croissant) de ses éléments.

Appartenance

On peut utiliser l’ancienne méthode mem où une méthode un peu améliorée.

static boolean mem(int xList p) {
  if (p == null || x < p.val) {
    return false ;
  } else {
    return p.val == x || mem(xp.next) ;
  }
}

Planche : 8


Ajout et union



Bilan des coûts
 memaddunion
ListeO(n)O(n)O(n2)
Liste triéeO(n)O(n)O(n)



Remarquer L’implémentation « liste triée » favorise l’opération ensembliste, mais n’améliore pas les autres opérations.


Planche : 9


Représenter les ensembles avec les arbres

On définit les arbres binaires de recherche :


Planche : 10


Un exemple d’arbre binaire de recherche

Planche : 11


Un contre-exemple d’arbre binaire de recherche

Planche : 12


Classe Tree des arbres binaires de recherche
class Tree {
  int key ;
  Tree leftright ;

  Tree (Tree leftint keyTree right) {
    this.left = left ; this.right = right ;
    this.key = key ;
  }

  Tree (int key) {
    this.key = key ; left = right = null ;
  }
}

Planche : 13


Test d’appartenance dans un ABR

C’est simple si on pense récursivement.

static boolean mem(int xTree t) {
  if (t == null) {
    return false ;
  } else { 
    if (x < t.key) {
      return mem(xt.keft) ; // Chercher à gauche
    } else if (x > t.key) {
      return mem(xt.right) ; // Chercher à droite
    } else { // x == t.key
      return true ; // Trouvé ici
    }
  }
}

Planche : 14


Test d’appartenance dans un ABR II

Finalement assez simple à programmer itérativement, penser que l’on suit un chemin dans un arbre.

static boolean mem(int xTree t) {
  while (t != null) {
    if (x < t.key) {
      t = t.left ;
    } else if (x > t.key) {
      t = t.right ;
    } else { // x == t.key
      return true ;
    }
  }
  return false ;
}

Planche : 15


Ajouter un élément : insertion dans un ABR
static Tree add(int xTree t) {
  if (t == null) {
    return new Tree(x) ;
  } else {
    if (x < t.key) {
      return new Tree (add(xt.left), t.keyt.right) ;
// ajouter à gauche 
    } else if (v > t.key) {
      return new Tree (t.leftt.keyadd(xt.right)) ;
// ajouter à droite 
    } else { // v == t.key, déjà là
      return t ;
    }
  }
}

Programmation itérative possible, mais trop complexe.


Planche : 16


Coût des deux opérations élémentaires

Il est facile de voir que le coût de mem et add, est en O(h) où h est la hauteur de l’ABR.

Mais on veut borner le coût fonction de n cardinal de l’ensemble…

Il faut donc exprimer la hauteur h en fonction du cardinal n.


Planche : 17


Un arbre (très) équilibré
Un arbre à peu près équilibré


Planche : 18


Un arbre (très) déséquilibré

Planche : 19


Hauteur minimale d’un arbre binaire

Ou nombre maximal de sommets pour une hauteur donnée : arbre binaire complet

n ≤  2h+1 − 1,   h ≥ log2(n+1)−1

Planche : 20


Hauteur maximale d’un arbre binaire

Ou nombre minimal de sommets pour une hauteur donnée : arbre dégénéré en liste.

h = n

Planche : 21


Complexité en moyenne

Sur un univers E qui regroupe des événements e de probabilité P(e), soit une fonction X(e).

L’espérance (moyenne) de X est définie par :

E(X) = 
 
e ∈ E
 Prob(e) · X(e)

Par exemple :


Planche : 22


Appartenance dans les listes, coût en moyenne

Planche : 23


Deux résultats en moyenne, sur les ABR

Pour n tendant vers +∞…

Le second résultat nous permet plus ou moins de considérer qu’un arbre pris au hasard est de hauteur log(n). Mais…


Planche : 24


Les arbres AVL

Les arbres AVL (Adelson-Velinsky-Landis) sont des arbres binaires plus :



Une conséquence importante :


Planche : 25


Diversion : explication rapide des bornes

Planche : 26


Arbre équilibré de hauteur maximale

Les équations définissant le nombre de sommets de l’arbre de taille minimale pour h donné, sont donc.

F(0) = 0,   F(1) = 1,   F(h+2) = 1 + F(h+1) + F(h)

Posons G(h) = F(h) + 1, il vient :

G(0) = 1,   G(1) = 2,   G(h+2) = G(h+1) + G(h)

On trouve :

G(h) = 
5−
5
2
Φh + 
5
−3
2
Φh,   avec Φ = 
1+
5
2

Au final la hauteur maximale d’un AVL est de l’ordre de logΦ(n), donc de l’ordre de log2(n).


Planche : 27


La vraie question des AVL : l’équilibre

Soit un AVL,

On ajoute l’élément 5
Déséquilibre (à droite).
  On rétablit l’équilibre.

Planche : 28


Comment garantir l’équilibre ?

Supposons écrite une méthode balance(AVL leftint keyAVL right) qui renvoie un arbre équilibré.

Alors c’est facile, (comme pour les ABR normaux).

static AVL add(int xAVL t) {
  if (t == null) {
    return new AVL(x) ;
  } else {
    if (x < t.key) {
      return balance(add(xt.left), t.keyt.right) ;
    } else if (v > t.key) {
      return balance(t.leftt.keyadd(xt.right)) ;
    } else {
      return t ;
    }
  }
}

Planche : 29


Classe des AVL
class AVL {
  int key ;
  private int h ; // Champ hauteur (pour éviter le recalcul)
  AVL leftright ;

  static int hauteur(AVL t) {
    if (t == null) { return 0 ; }
    else { return t.h ; }
  }

  AVL (AVL leftint keyAVL right) {
    this.left = left ; this.right = right ; this.key = key ;
    this.h = Math.max(hauteur(left), hauteur(right)) + 1 ;
  }
  AVL (int key) {this.key = key ; left = right = null ; h = 1 ;}
}

Il reste à écrire balance.


Planche : 30


Écrivons balance

balance prend deux arbres left et right en argument, avec (par construction)

−2 ≤ hauteur(left) − hauteur(right) ≤ 2

On suppose un déséquilibre, c’est à dire par ex.

hauteur(left) = hauteur(right) + 2

C’est à dire :


Planche : 31


Analysons un peu encore

Notons L (arbre de gauche), k (clé) et R les arguments de balance.


Planche : 32


Premier cas

Supposons donc h(LL)= δ+1 (eth(LR)= δ ou h(LR)= δ+1).


Alors, l’arbre suivant est équilibré :

De hauteur δ+2 ou δ+3.


Planche : 33


Second cas

Ce cas (δ = h(LL) < h(LR) = δ+1) entraîne LR non-vide.

Alors, l’arbre suivant est équilibré

De hauteur δ+2.


Planche : 34


Une remarque

Tout d’abord, un résultat, si h(L) = h(R)+2, nous savons produire un AVL équivalent à l’ABR déséquibré (L,x,R), et ceci en temps constant.

Dans le cas de l’ajout, la hauteur finale de l’AVL est toujours δ+2, car le cas h(LL) = h(LR) = δ+2 ne peut pas se produire (sinon, l’arbre avant ajout serait déséquibré).

Cette hauteur est égale à celle de l’arbre avant ajout

On en déduit que l’équilibrage se produit au plus une fois lors d’un ajout.


Planche : 35


Dans un souci de complétude
  static AVL balance(AVL leftint valAVL right) {
    int hl = hauteur(left), hr = hauteur(right);

    if (hl > hr + 1) { // => left != null
      if (hauteur(left.left) >= hauteur(left.right))
        return
          new AVL(left.left,left.key,new AVL (left.right,val,right));
      else // => left.right != null
        return
          new AVL(new AVL (left.left,left.key,left.right.left),
                        left.right.key,
                        new AVL (left.right.right,val,right));
    } else if (hr > hl + 1) { // Même chose en symétrique
      …
    } else
      return new AVL (left,val,right);
  }

Planche : 36


Conclusion temporaire

Le minimum à savoir.


Planche : 37


Dans le même ordre d’idée

Les arbres equilibrés permettent une implémentation efficace des associations (amphi 04), cette fois persistantes.


Planche : 38


Les ABR de la bibliothèque

De façon surprenante, les TreeSet de Java, sont des ensembles impératifs (non-persistants), dommage.


Planche : 39


Complément : enlever un élément

Prenons le cas des ABR, on trouve les premiers cas par induction.

static Tree remove(Tree tint v) {
  if (t == null) {
    return null ;
  } else if (v < t.key) {
    return new Tree (remove(t.leftv), t.keyt.right) ;
  } else if (v > t.key) {
    return new Tree (t.leftt.keyremove(t.rightv)) ;
  } else if (t.right == null) {
    return t.left ;
  } else {// Ici v == t.val, t.right != null
    …

Le dernier cas n’est pas immédiat : il faut mélanger t.left et t.right en un seul ABR.


Planche : 40


Exemple : enlever la racine

L’idée, remplacer la racine par le minimun du sous-arbre droit.


Planche : 41


Trouver/enlever le minimum

Planche : 42


Remplacer la racine

Voci le code manquant de remove.

static Tree remove(Tree tint v) {
  …
  } else { // Ici v == t.val, t.right != null
    int min = getMin(t.right) ;
    return new Tree(t.leftminremoveMin(t.right)) ;
  }
}

Et les AVL ? Remplacer, dans remove et removeMin, tous les appels du constructeur new Tree(ℓ, vr) par des appels de méthode balance(ℓ, vr).

Correction ? Le déséquilibre entre ℓ et r est limité à 2 au plus.


Planche : 43


Opération ensemblistes

Réaliser par exemple l’union de deux deux ensembres représentés par les ABR equilibrés T1 et T2.

Une première méthode simple :

Parcourir l’arbre T1 pour ajouter ses éléments à T2 (avec la méthode add).

Coût (T1 et T2 possédant n éléments) :O(n logn) (n fois add dans un arbre de taille au plus 2n)


Planche : 44


Une autre méthode (pour les ABR)

Union de T1 et T2

Remarquer


Planche : 45


Programmation de union

Suit directement l’algorithme.

static Tree union(Tree t1Tree t2) {
  if (t1 == nullreturn t2 ;
  else if (t2 == nullreturn t1 ;
  else {
    Tree l1 = t1.leftr1 = t1.right ;
    int x = t1.key ;
    Tree l2 = splitLt(xt2), r2 = splitGt(xt2) ;
    return new Tree (union(l1l2), xunion(r1r2)) ;
  }
}

Planche : 46


Programmation de splitLt

Renvoie l’ensemble des éléments de t qui sont < à x.

static Tree splitLt(int xTree t) {
  if (t == nullreturn null ;
  else {
    if (t.key < x) { // Ici t.left < x
      return new Tree(t.leftt.keysplitLt(xt.right))
    } else if (t.key > x) {
      // Cas symétrique
    } else { // t.key == x
      return t.left ;
    }
  }
}

Planche : 47


Coût, (approche heuristique)

Supposons les arbres équilibrés.

Le coût d’un appel à union est dominé par celui des appels à splitLt et splitGt, qui sont proportionels à la hauteur de t2.

U(n) ∼ log(n) + 2 U(n/2)

En posant n = 2p,

U(2p) ∼ p + 2 U(2p−1).

Soit à peu près,

U(2p) ∼ p + 2(p−1) + 4(p−2) + ⋯ 2p ∼ 2p+2.

Planche : 48


Un cas particulier

On peut utiliser un arbre AVL, mais il existe une solution plus simple.


Planche : 49


Les arbres (binaires) quasi-complets


Planche : 50


Exemples et contre-exemples

Oui

Noter : un des sommets de l’avant-dernier étage n’a qu’un fils.


Non, le troisième étage est incomplet.

Non, le dernier étage n’est pas « tassé ».

Planche : 51


Arbres quasi-complets et tableaux

Planche : 52


Arbres quasi-complets et tableaux

En fait les arbres quasi-complets sont exactement les arbres représentables ainsi dans un tableau :


Planche : 53


Bout de preuve

On numérote les sommets d’un arbre quasi-complet selon un parcours en largeur d’abord :

Reste à montrer qu’il y a i−1 sommets entre un sommet d’indice i et son fils gauche (si il existe). Et en effet, il y a :

Soit en tout i−1 sommets.


Planche : 54


Bout de philosophie

Planche : 55


Le heap (tas)

Un tas est un arbre quasi-complet et :

C’est un tas-max, il y aussi évidemment des tas-min.


Planche : 56


Contre-exemple

La propriété de heap est invalidée par le sommet de clé 13.


Planche : 57


Le heap (tas)

Un tas est un arbre quasi-complet et :

C’est un tas-max, il y aussi évidemment des tas-min.


Planche : 58


Contre-exemple

La propriété de heap est invalidée par le sommet de clé 13.


Planche : 59


Classe Heap

Les tas (d’entiers) : encapsulage du tableau.

class Heap {
  private int [] t ; // Tableau des sommets
  private int n ;     // Nombre de sommets

  Heap(int sz) {
    t = new int [sz+1] ;
    n = 0 ;
  }
  …
}

Planche : 60


Ajouter un élément dans un heap.

Planche : 61


Invalidation de la propriété de heap

La position d’indice n+1 dans le tableau est la feuille « suivante ».

(Ajout de 13.)


Planche : 62


Restaurer la propriété de heap

Faire « remonter » le sommet invalidant.


Planche : 63


Faire « remonter » un sommet
void add(int x) {
  n++ ;
  int i = n ;
  // Tant que i dans l'arbre et heap invalidé, 
  while (i > 1 && t[i/2] < x) { // NB: division euclidienne
    t[i] = t[i/2] ; // Libérer la case i/2
    i = i/2 ;
  }
  t[i] = x ;
}

Noter Plutôt que d’échanger les cases, on fait remonter un trou.


Planche : 64


Extraire le maximum

Donc,


Planche : 65


Restaurer le heap II

Faire « descendre » le sommet invalidant.


Planche : 66


Le tas-outil

Les tas sont un outil efficace pour extraire des maxima (minima), à la volée.

Il sont souvent une brique d’algorithmes plus complexes (parcours de graphes, recherche de solutions optimales diverses).

Mais attention, les tas ne sont pas une bonne implémentation générale des ensembles (ou des multi-ensembles).


Planche : 67


Exemple de tas-outil

Par exemple : on trie facilement n éléments avec un tas :

Soit encore un tri en nlog(n).


Planche : 68


Performance de heapsort

Temps d’exécution de heapsort H et du tri de la bibliothèque S (java.util.Arrays.sort).


Ce document a été traduit de LATEX par HEVEA