Université de Sherbrooke, Structures de données (SDO)

int main() {
   enum { N = 10'000 };
   int tab[N * N]{}; // initialisé avec des zéros... oups!
}

int main() {
   enum { N = 10'000 };
   int * tab = new int[N * N]{}; // initialisé avec des zéros...
   // ICI : ... le programme s'exécute et il se passe "des choses" ...
   delete [] tab;
}

int main() {
   enum { N = 10'000 };
   int * tab = new int[N * N]{}; // initialisé avec des zéros
   // remplir le tableau avec des valeurs impaires
   // question : que pensez-vous de ce code?
   for (int i = 0; i != N * N; ++i)
      tab[i] = 2 * i + 1;
   // ...
   delete []tab;
}

int generer_impair(int n) {
   return 2 * n + 1;
}
int main() {
   enum { N = 10'000 };
   int * tab = new int[N * N]{}; // initialisé avec des zéros
   // question : que pensez-vous de ce code?
   for (int i = 0; i != N * N; ++i)
      tab[i] = generer_impair(i);
   // ...
   delete []tab;
}

int generer_impair(int n) {
   return 2 * n + 1;
}
int main() {
   enum { N = 10'000 };
   int * tab = new int[N * N]{}; // initialisé avec des zéros
   // question : que pensez-vous de ce code?
   int i = 0; // le i est un artéfact du code pour générer des impairs, et n'est
              // pas essentiel au propos ici
   for (int *p = tab; p != tab + N * N; ++p)
      *p = generer_impair(i++);
   // ...
   delete []tab;
}

int generer_impair(int n) {
   return 2 * n + 1;
}
void remplir(debut, fin, f) {
   int n = 0;
   for (; debut != fin; ++debut)
      *debut = f(n++);
}
int main() {
   enum { N = 10'000 };
   int * tab = new int[N * N]{}; // initialisé avec des zéros
   // question : que pensez-vous de ce code?
   remplir(tab, tab + N, generer_impair);
   // ...
   delete []tab;
}

int generer_impair(int n) {
   return 2 * n + 1;
}
template <class It, class F> // It pour itérateur, F pour fonction
   void remplir(debut, fin, f) {
      int n = 0;
      for (; debut != fin; ++debut)
         *debut = f(n++);
   }
int main() {
   enum { N = 10'000 };
   int * tab = new int[N * N]{}; // initialisé avec des zéros
   // question : que pensez-vous de ce code?
   remplir(tab, tab + N, generer_impair);
   // ...
   delete []tab;
}

#include <cstddef> // std::size_t
#include <utility> // std::swap

template <class T>
   class deque {
      T **debut{};
      size_t nelems{}, cap{}, zero{};
      // ...

      // ...
      bool full() const {
         return size() == capacity();
      }
   public:
      std::size_t size() const {
         return nelems;
      }
      std::size_t capacity() const {
         return cap;
      }
      bool empty() const {
         return !size();
      }
      // ...

      // ...
      class iterator {
         std::size_t cur;
         deque &source;
      public:
         iterator(deque &source, std::size_t pos)
            : source{ source }, cur{ pos } {
         }
         iterator &operator++() {
            ++cur;
            return *this;
         }
         iterator operator++(int) {
            auto temp = *this;
            operator++();
            return temp;
         }
         T &operator*() {
            return source[cur];
         }
         const T &operator*() const {
            return source[cur];
         }
         bool operator==(const iterator &autre) const {
            return cur == autre.cur;
         }
         bool operator!=(const iterator &autre) const {
            return !(*this == autre);
         }
      };
      // ...

      // ...
      class const_iterator {
         std::size_t cur;
         const deque &source;
      public:
         const_iterator(const deque &source, std::size_t pos)
            : source{ source }, cur{ pos } {
         }
         const_iterator &operator++() {
            ++cur;
            return *this;
         }
         const_iterator operator++(int) {
            auto temp = *this;
            operator++();
            return temp;
         }
         const T &operator*() const {
            return source[cur];
         }
         bool operator==(const iterator &autre) const {
            return cur == autre.cur;
         }
         bool operator!=(const iterator &autre) const {
            return !(*this == autre);
         }
      };
      // ...

      // ...
      iterator begin() {
         return { *this, 0 };
      }
      iterator end() {
         return { *this, size() };
      }
      const_iterator begin() const {
         return { *this, 0 };
      }
      const_iterator end() const {
         return { *this, size() };
      }
      // ...

      // ...
      deque() = default;
      deque(std::size_t dim)
         : nelems{ dim }, cap{ dim }, zero{} {
         if (dim > 0)
            debut = new T *[capacity];
         else
            debut = nullptr;
         for (std::size_t i = 0; i < size(); ++i)
            debut[i] = new T{};
      }
      // ...

      // ...
      ~deque() {
         clear();
      }
      // ...

      // ...
      deque(const deque &autre) : deque{ autre.size() } {
         for (std::size_t i = 0; i != size(); ++i)
            *debut[i] = *autre.debut[(i + autre.zero) % autre.cap];
      }
      // ...

      // ...
      void swap(deque &autre) {
         using std::swap;
         swap(debut, autre.debut);
         swap(cap, autre.cap);
         swap(nelems, autre.nelems);
         swap(zero, autre.zero);
      }
      deque &operator=(const deque &autre) {
         deque{ autre }.swap(*this);
         return *this;
      }
      // ...

      // ...
      void resize(std::size_t nouv_nelems) {
         // ...
      }
      // ...

      // ...
      void reserve(std::size_t nouv_cap) {
         // ...
      }
      // ...

      // ...
      void clear() {
         for (std::size_t i = 0; i != size(); ++i)
            delete debut[(i + zero) % capacity()];
         delete[] debut;
         debut = nullptr;
         zero = 0;
         cap = nelems = 0;
      }
      // ...

      // ...
      T &operator[](std::size_t n) {
         return *debut[(n + zero) % capacity()];
      }
      const T &operator[](std::size_t n) const {
         return *debut[(n + zero) % capacity()];
      }
      // ...

      // ...
      void push_back(const T &val) {
         // ...
      }
      void pop_back() {
         // ...
      }
      void push_front(const T &val) {
         // ...
      }
      void pop_front() {
         // ...
      }
   };
   // ...

// ...
#include <string>
#include <iostream>

int main() {
   using namespace std;
   deque<int> v;
   for (int i : { 2, 3, 5, 7, 11 })
      v.push_back(i);
   for (int n : v)
      cout << n << ' ';
   cout << endl;
   while (!v.empty()) {
      v.pop_front();
      for (int n : v)
         cout << n << ' ';
      cout << endl;
   }
}

template <class T, int N>
   class file_circulaire {
      static_assert(N > 1); // bof
      using buf_type = std::array<T,N>;
      buf_type buf {};
      int ins_pt = 0;
      int ext_pt = 0;
      static int next(int n) {
         return ++n, n == N ? 0 : n;
      }
      static int prev(int n) {
         return n == 0 ? N - 1 : n - 1;
      }
      bool full() const noexcept {
         return next(ins_pt) == ext_pt;
      }
      bool empty() const noexcept {
         return ins_pt == ext_pt;
      }
   public:
      void push(const T &obj) {
         if (full()) throw file_pleine{};
         buf[ins_pt] = obj;
         ins_pt = next(ins_pt);
      }
      void pop() {
         if (empty()) throw file_vide{};
         ext_pt = next(ext_pt);
      }
      T top() {
         if (empty()) throw file_vide{};
         return buf[ext_pt];
      }
      bool try_push(const T &obj) {
         if (full()) return false;
         buf[ins_pt] = obj;
         ins_pt = next(ins_pt);
         return true;
      }
      bool try_pop(T &obj) {
         if (empty()) return false;
         obj = buf[ext_pt];
         ext_pt = next(ext_pt);
         return true;
      }
   };

template <class T, int N>
   class file_circulaire {
      static_assert(N > 1); // bof
      T(&buf)[N];
      int ins_pt = 0;
      int ext_pt = 0;
      static int next(int n) {
         return ++n, n == N ? 0 : n;
      }
      static int prev(int n) {
         return n == 0 ? N - 1 : n - 1;
      }
      bool full() const noexcept {
         return next(ins_pt) == ext_pt;
      }
      bool empty() const noexcept {
         return ins_pt == ext_pt;
      }
   public:
      file_circulaire(T (&buf)[N]) : buf{ buf } {
      }
      void push(const T &obj) {
         if (full()) throw file_pleine{};
         buf[ins_pt] = obj;
         ins_pt = next(ins_pt);
      }
      void pop() {
         if (empty()) throw file_vide{};
         ext_pt = next(ext_pt);
      }
      T top() {
         if (empty()) throw file_vide{};
         return buf[ext_pt];
      }
      bool try_push(const T &obj) {
         if (full()) return false;
         buf[ins_pt] = obj;
         ins_pt = next(ins_pt);
         return true;
      }
      bool try_pop(T &obj) {
         if (empty()) return false;
         obj = buf[ext_pt];
         ext_pt = next(ext_pt);
         return true;
      }
   };

#include <iostream>

int main() {
   using namespace std;
   arbre<char> a;
   a.creer_racine('A')
      .ajouter_enfant('B')
         .ajouter_enfant('E')
            .ajouter_enfant('J')
               .ajouter_enfant('L');
   a.get_racine().enfant('B').ajouter_enfant('F');
   a.get_racine().ajouter_enfant('C');
   a.get_racine().ajouter_enfant('D')
      .ajouter_enfant('G');
   a.get_racine().enfant('D')
      .ajouter_enfant('H');
   a.get_racine().enfant('D')
      .ajouter_enfant('I')
         .ajouter_enfant('K');
   // visite inordre de a devrait afficher   : LJEBFACGDHKI
   // visite preordre de a devrait afficher  : ABEJLFCDGHIK
   // visite postordre de a devrait afficher : LJEFBCGHKIDA
}

xxx

#include <utility>
#include <string>

//
// Ce qui caractérise un arbre binaire de recherche, c'est
// l'ordre des valeurs des noeuds. Dans un tel arbre, tous
// les noeuds du sous arbre de gauche sont inférieurs à la
// racine, et tous ceux du sous arbre de droite sont
// supérieurs à la racine
// 
// Un arbre AVL est un arbre binaire de recherche tel que
// la différence entre les hauteurs des sous-arbres est au
// plus 1 (ceci évite des cas dégénérés qui ralentiraient
// la recherche en déséquilibrant l'arbre)
//
template <class T>
class avl_tree {
   struct node {
      T valeur;
      node *parent = nullptr; // ICI
      node *gauche = nullptr;
      node *droite = nullptr;
      node(const T &valeur) : valeur{ valeur } {
      }
      bool est_feuille() const noexcept {
         return nb_enfants() == 0;
      }
      int nb_enfants() const noexcept {
         return static_cast<int>(gauche != nullptr) +
            static_cast<int>(droite != nullptr);
      }
   };
   node *racine = nullptr;
public:
   bool empty() const noexcept {
      return !racine;
   }
   avl_tree() = default;
   // fonctions spéciales (copie supprimée pour simplifier le propos)
   avl_tree(const avl_tree &) = delete;
   avl_tree &operator=(const avl_tree &) = delete;
   ~avl_tree() {
      while (!empty())
         supprimer(racine->valeur);
   }
   bool contient(const T &valeur) const {
      if (empty()) return false;
      return contient(racine, valeur);
   }

   void balancer(node *p) {
      if (!p) return;
      if (int balance = hauteur(p->gauche) - hauteur(p->droite);
         balance == -2) {
         // débalancement à droite
         if (int balance_droite = hauteur(p->droite->droite) - hauteur(p->droite->gauche);
            balance_droite == -1) { // rotation droite-gauche
            rotation_droite(p->droite);
         }
         rotation_gauche(p);
      } else if (balance == 2) {
         // débalancement à gauche
         if (int balance_gauche = hauteur(p->gauche->droite) - hauteur(p->gauche->gauche);
            balance_gauche == 1) {		// Cas de rotation gauche-droite.
            rotation_gauche(p->gauche);
         }
         rotation_droite(p);
      }
      balancer(p->parent);
   }

   void rotation_gauche(node *p) {
      if (!p) return;
      node *droite = p->droite;
      // attacher le parent de p à son enfant de droite
      if (p->parent) {
         if (p->parent->droite == p)
            p->parent->droite = droite;
         else
            p->parent->gauche = droite;
      }
      droite->parent = p->parent;

      // lier p et le sous-arbre gauche de l'enfant de droite
      if (droite->gauche)
         droite->gauche->parent = p;
      p->droite = droite->gauche;

      // placer droite au sommet de ce sous-arbre
      p->parent = droite;
      droite->gauche = p;
      if (p == racine)
         racine = droite;
   }

   void rotation_droite(node *p) {
      if (!p) return;

      node *gauche = p->gauche;
      // attacher le parent de p à son enfant de gauche
      if (p->parent) {
         if (p->parent->gauche == p)
            p->parent->gauche = gauche;
         else
            p->parent->droite = gauche;
      }
      gauche->parent = p->parent;

      // lier p et le sous-arbre droite de l'enfant de gauche
      if (gauche->droite)
         gauche->droite->parent = p;
      p->gauche = gauche->droite;

      // placer gauche au sommet de ce sous-arbre
      p->parent = gauche;
      gauche->droite = p;
      if (p == racine)
         racine = gauche;
   }

   bool ajouter(const T &valeur) {
      node *p = racine,
         *q = nullptr;
      while (p) {
         q = p;
         if (valeur < p->valeur)
            p = p->gauche;
         else
            p = p->droite;
      }
      node *r = new node{ valeur };
      if (!q)
         racine = r;
      else {
         if (valeur < q->valeur)
            q->gauche = r;
         else
            q->droite = r;
         r->parent = q; // ICI
      }
      balancer(trouver(r->parent, valeur)); // ICI
      return true;
   }
private:
   bool contient(node *p, const T &valeur) const {
      if (!p) return false;
      if (valeur == p->valeur) return true;
      if (valeur < p->valeur)
         return p->gauche ? contient(p->gauche, valeur) : false;
      return p->droite ? contient(p->droite, valeur) : false;
   }
   node *trouver(node *p, const T &valeur) const {
      if (!p || valeur == p->valeur) return p;
      if (valeur < p->valeur)
         return trouver(p->gauche, valeur);
      return trouver(p->droite, valeur);
   }
public:
   template <class F>
   void visiter_preordre(F fct) { // depth-first
      visiter_preordre(fct, racine, std::string{});
   }
private:
   template <class F>
   void visiter_preordre(F fct, node *p, const std::string &prefixe) { // depth-first
      using namespace std;
      fct.entrer();
      if (!p) return;
      fct(p->valeur, prefixe + "[" + to_string(hauteur(p->gauche) - hauteur(p->droite)) + "] : "s);
      visiter_preordre(fct, p->gauche, "g"s);
      visiter_preordre(fct, p->droite, "d"s);
      fct.sortir();
   }
public:
   void supprimer(const T &valeur) {
      if (empty()) return;
      supprimer(racine, valeur);
   }
private:
   // précondition : p != nullptr
   bool supprimer_gauche(node * &p, const T &valeur) {
      supprimer(p->gauche, valeur);
      if(p)
         balancer(p);
      return true;
   }
   // précondition : p != nullptr
   bool supprimer_droite(node * &p, const T &valeur) {
      supprimer(p->droite, valeur);
      if (p)
         balancer(p);
      return true;
   }
   bool supprimer(node *&p, const T &valeur) {
      if (!p)
         return false;
      if (valeur < p->valeur)
         return supprimer_gauche(p, valeur);
      if (p->valeur < valeur)
         return supprimer_droite(p, valeur);
      if (p->gauche) {
         p->valeur = trouver_maximal(p->gauche)->valeur;
         return supprimer_gauche(p, p->valeur);
      }
      node *victime = p;
      p = p->droite;
      if (p) p->parent = victime->parent;
      delete victime;
      return true;
   }
   node *trouver_minimal(node *p) {
      return !p ? p : p->gauche ? trouver_minimal(p->gauche) : p;
   }
   node *trouver_maximal(node *p) {
      return !p ? p : p->droite ? trouver_maximal(p->droite) : p;
   }
public:
   T minimum() const {
      if (empty()) throw 3;
      node *p = racine;
      for (; p->gauche; p = p->gauche)
         ;
      return p->valeur;
   }
   T maximum() const {
      if (empty()) throw 3;
      node *p = racine;
      for (; p->droite; p = p->droite)
         ;
      return p->valeur;
   }
   int hauteur() const {
      return hauteur(racine);
   }
private:
   int hauteur(node *p) const {
      if (!p) return 0;
      int hauteur_gauche = hauteur(p->gauche);
      int hauteur_droite = hauteur(p->droite);
      return 1 + (hauteur_gauche < hauteur_droite ?
         hauteur_droite : hauteur_gauche);
   }
   friend class iterator_naif;
   friend class iterator_raffine;
public:
   class iterator_naif {
      friend class avl_tree<T>;
      node *cur;
      avl_tree &src;
      iterator_naif(node *init, avl_tree &src)
         : cur{ init }, src{ src } {
      }
      iterator_naif(avl_tree &src)
         : cur{ nullptr }, src{ src } {
      }
      // ICI :
      // vos notes de cours, p.109
      // note : O(log n) par appel, donc O(n log n) pour un parcours
      //        complet... aussi long qu'un tri!
      node *suivant(node *p) {
         node *q = src.racine;
         node *sq = p->droite;
         if (sq)
            while (sq->gauche)
               sq = sq->gauche;
         else
            while (q != p)
               if (p->valeur < q->valeur)
                  q = (sq = q)->gauche;
               else
                  q = q->droite;
         return sq;
      }
   public:
      iterator_naif &operator++() {
         cur = suivant(cur);
         return *this;
      }
      iterator_naif operator++(int) {
         auto temp = *this;
         operator++();
         return temp;
      }
      bool operator==(const iterator_naif &autre) const {
         return cur == autre.cur;
      }
      bool operator!=(const iterator_naif &autre) const {
         return !(*this == autre);
      }
      T operator*() const { return cur->valeur; }
   };
   //
   // ICI
   //
   iterator_naif begin_naif() {
      return { trouver_minimal(racine), *this };
   }
   iterator_naif end_naif() {
      return { *this };
   }
   //
   // ICI
   //
   class iterator_raffine {
      friend class avl_tree<T>;
      node *cur;
      avl_tree &src;
      iterator_raffine(node *init, avl_tree &src)
         : cur{ init }, src{ src } {
      }
      iterator_raffine(avl_tree &src)
         : cur{ nullptr }, src{ src } {
      }
      // ICI :
      // vos notes de cours, p.110
      // note : O(1) amorti par appel, donc O(n) en moyenne pour
      //        un parcours complet... bien mieux!
      node *suivant(node *p) {
         node *sq;
         if (!p->droite)
            for (sq = p->parent;
               sq && sq->gauche != p;
               p = sq, sq = p->parent)
               ;
         else
            for (sq = p->droite; sq->gauche; sq = sq->gauche)
               ;
         return sq;
      }
   public:
      iterator_raffine &operator++() {
         cur = suivant(cur);
         return *this;
      }
      iterator_raffine operator++(int) {
         auto temp = *this;
         operator++();
         return temp;
      }
      bool operator==(const iterator_raffine &autre) const {
         return cur == autre.cur;
      }
      bool operator!=(const iterator_raffine &autre) const {
         return !(*this == autre);
      }
      T operator*() const { return cur->valeur; }
   };
   //
   // ICI
   //
   iterator_raffine begin_raffine() {
      return { trouver_minimal(racine), *this };
   }
   iterator_raffine end_raffine() {
      return { *this };
   }
};

#include <iostream>
#include <string>
using namespace std;

struct afficheur {
   int indent = -1;
   void entrer() {
      ++indent;
   }
   void sortir() {
      ++indent;
   }
   void operator()(int n) const {
      cout << string(2 * indent, ' ') << n << endl;
   }
};

struct afficheur_annote {
   int indent = -1;
   void entrer() {
      ++indent;
   }
   void sortir() {
      ++indent;
   }
   template <class T>
      void operator()(const T &val, const string &prefixe = {}) const {
         cout << string(2 * indent, ' ') << prefixe << val << endl;
      }
};

enum class operation { inserer, supprimer, quitter };
template <class T>
   void mise_a_jour(avl_tree<T> &avlt, const T &val, operation op) {
      if (op == operation::inserer)
         cout << "Insertion de " << val << '\n';
      else if (op == operation::supprimer)
         cout << "Suppression de " << val << '\n';
      else
         return;
      cout << "Avant :\n";
      avlt.visiter_preordre(afficheur_annote{});
      if (op == operation::inserer)
         avlt.ajouter(val);
      else if (op == operation::supprimer)
         avlt.supprimer(val);
      cout << "Apres :\n";
      avlt.visiter_preordre(afficheur_annote{});
      cout << string(70, '-') << '\n';
   }

#include <utility>

pair<operation, int> lire_choix() {
   auto est_valide = [](char c) {
      return c == 'a' || c == 's' || c == 'q';
   };
   cout << "Operation : [a]jouter, [s]upprimer, [q]uitter ? ";
   char c;
   while (cin.get(c) && !est_valide(c))
      ;
   if (c != 'q') {
      cout << "quelle valeur? ";
      if(int valeur; cin >> valeur)
         return c == 'a'? pair{ operation::inserer, valeur } :
                          pair{ operation::supprimer, valeur };
   }
   return { operation::quitter, 0 };
}


#include <vector>
#include <random>
#include <algorithm>

int main() {
   avl_tree<int> avl;
   int vals[]{ 25, 35, 30, 20, 15, 5, 28, 50, 45, 48, 43, 1, 3, 7, 2 };

   for (auto n : vals)
      mise_a_jour(avl, n, operation::inserer);

   // source d'entropie
   random_device rd;
   mt19937 prng{ rd() };
   vector<int> v{ begin(vals), end(vals) };
   shuffle(begin(v), end(v), prng);
   while (!v.empty()) { // O(n)
      mise_a_jour(avl, v.back(), operation::supprimer);
      v.pop_back(); // O(1)
   }

   //for (auto [choix, val] = lire_choix();
   //     choix != operation::quitter;
   //     tie(choix, val) = lire_choix()) {
   //   mise_a_jour(avl, val, choix);
   //}
   cout << '\n';
   if (!avl.empty()) {
      cout << "Noeud de valeur minimale : "
         << avl.minimum() << '\n';
      cout << "Noeud de valeur maximale : "
         << avl.maximum() << '\n';
   }
   cout << "hauteur : " << avl.hauteur() << endl;
   //
   // ICI
   //
   cout << "Parcours sequentiel (naif) :\n\t";
   for (auto p = avl.begin_naif(); p != avl.end_naif(); ++p)
      cout << *p << ' ';
   cout << '\n';
   cout << "Parcours sequentiel (raffine) :\n\t";
   for (auto p = avl.begin_raffine(); p != avl.end_raffine(); ++p)
      cout << *p << ' ';
   cout << '\n';
}

#include <utility>
#include <string>

#include <iostream>

//
// Ce qui caractérise un arbre binaire de recherche, c'est
// l'ordre des valeurs des noeuds. Dans un tel arbre, tous
// les noeuds du sous arbre de gauche sont inférieurs à la
// racine, et tous ceux du sous arbre de droite sont
// supérieurs à la racine
// 
// Un arbre AVL est un arbre binaire de recherche tel que
// la différence entre les hauteurs des sous-arbres est au
// plus 1 (ceci évite des cas dégénérés qui ralentiraient
// la recherche en déséquilibrant l'arbre)
//
// Un arbre équilibré en poids est comme un arbre AVL, à ceci
// près qu'on ne rebalance un sous-arbre que si le débalancement
// entre ses branches de gauche et de droite dépasse un certain
// seuil (p.ex.: 3 ou 2.15). Avec un facteur de 3, par exemple,
// il faut que le nombre de noeuds d'un des deux sous-arbres
// soit au moins trois fois le nombre de noeuds de l'autre avant
// de procéder
//
template <class T>
class arbre_equil_poids {
   struct node {
      T valeur;
      int poids = 1; // ICI
      node *parent = nullptr;
      node *gauche = nullptr;
      node *droite = nullptr;
      node(const T &valeur) : valeur{ valeur } {
      }
      bool est_feuille() const noexcept {
         return nb_enfants() == 0;
      }
      int nb_enfants() const noexcept {
         return static_cast<int>(gauche != nullptr) +
                static_cast<int>(droite != nullptr);
      }
   };
   node *racine = nullptr;
   double facteur_desequilibre = 3.0; // gamma
   // ICI
   int calculer_poids(node *p) {
      return !p ? 0 : 1 + calculer_poids(p->gauche) + calculer_poids(p->droite);
   }
public:
   bool empty() const noexcept {
      return !racine;
   }
   arbre_equil_poids() = default;
   // ICI : faudrait valider, évidemment, mais bon...
   arbre_equil_poids(double gamma) : facteur_desequilibre{ gamma } {
   }
   // fonctions spéciales (copie supprimée pour simplifier le propos)
   arbre_equil_poids(const arbre_equil_poids &) = delete;
   arbre_equil_poids &operator=(const arbre_equil_poids &) = delete;
   ~arbre_equil_poids() {
      while (!empty())
         supprimer(racine->valeur);
   }
   bool contient(const T &valeur) const {
      if (empty()) return false;
      return contient(racine, valeur);
   }

   enum class debalancement {
      aucun, gauche, droite
   };
   debalancement evaluer_debalancement(node *p) const {
      if (!p) return debalancement::aucun;
      // AVL
      //if (int balance = hauteur(p->gauche) - hauteur(p->droite);
      //   balance == -2)
      //   return debalancement::droite;
      //else if (balance == 2)
      //   return debalancement::gauche;

// patch temporaire
       // AVL
      if (int balance = hauteur(p->gauche) - hauteur(p->droite); 
          std::abs(balance) < 2)
         return debalancement::aucun;

      // WBT
      const int poids_gauche = evaluer_poids(p->gauche),
                poids_droite = evaluer_poids(p->droite);
      if (poids_gauche * facteur_desequilibre < poids_droite) {
         std::cout << "Desequilibre vers la droite a partir de "
                   << p->valeur
                   << " (" << poids_gauche << " < "
                   << facteur_desequilibre << " * " << poids_droite << ")\n";
         return debalancement::droite;
      }
      if (poids_droite * facteur_desequilibre < poids_gauche) {
         std::cout << "Desequilibre vers la gauche a partir de "
                   << p->valeur
                   << " (" << poids_gauche << " vs " << poids_droite << ")\n";
         return debalancement::gauche;
      }
      return debalancement::aucun;
   }
   void balancer(node *p) {
      if (!p) return;
      // ICI
      node *parent = p->parent;

      // ICI
      if (debalancement balance = evaluer_debalancement(p);
          balance == debalancement::droite) {
         if (hauteur(p->droite->droite) < hauteur(p->droite->gauche)) {
            // rotation droite-gauche
            rotation_droite(p->droite);
         }
         rotation_gauche(p);
      } else if (balance == debalancement::gauche) {
         if (hauteur(p->gauche->droite) > hauteur(p->gauche->gauche)) {
            // rotation gauche-droite
            rotation_gauche(p->gauche);
         }
         rotation_droite(p);
      }
      // ICI
      balancer(p->parent);
   }

   // ICI : pour éviter la répétition des calculs
   int evaluer_poids(node *p) const {
      return p ? p->poids : 0;
   }

   void rotation_gauche(node *p) {
      if (!p) return;
      // ICI
      if (!p->droite && !p->gauche) return;

      node *droite = p->droite;
      // attacher le parent de p à son enfant de droite
      if (p->parent) {
         if (p->parent->droite == p)
            p->parent->droite = droite;
         else
            p->parent->gauche = droite;
      }
      droite->parent = p->parent;

      // lier p et le sous-arbre gauche de l'enfant de droite
      if (droite->gauche)
         droite->gauche->parent = p;
      p->droite = droite->gauche;

      // placer droite au sommet de ce sous-arbre
      p->parent = droite;
      droite->gauche = p;
      if (p == racine)
         racine = droite;

      // ICI : recalculer les poids des noeuds qui ont été
      // affectés par la rotation
      p->poids = 1 + evaluer_poids(p->gauche) + evaluer_poids(p->droite);
      droite->poids = 1 + evaluer_poids(droite->gauche) +
                          evaluer_poids(droite->droite);
      if (node * parent = droite->parent; parent)
         parent->poids = 1 + evaluer_poids(parent->gauche) +
                             evaluer_poids(parent->droite);
   }

   void rotation_droite(node *p) {
      if (!p) return;
      // ICI
      if (!p->droite && !p->gauche) return;

      node *gauche = p->gauche;
      // attacher le parent de p à son enfant de gauche
      if (p->parent) {
         if (p->parent->gauche == p)
            p->parent->gauche = gauche;
         else
            p->parent->droite = gauche;
      }
      gauche->parent = p->parent;

      // lier p et le sous-arbre droite de l'enfant de gauche
      if (gauche->droite)
         gauche->droite->parent = p;
      p->gauche = gauche->droite;

      // placer gauche au sommet de ce sous-arbre
      p->parent = gauche;
      gauche->droite = p;
      if (p == racine)
         racine = gauche;
      // ICI : recalculer les poids des noeuds qui ont été
      // affectés par la rotation
      p->poids = 1 + evaluer_poids(p->gauche) + evaluer_poids(p->droite);
      gauche->poids = 1 + evaluer_poids(gauche->gauche) +
                          evaluer_poids(gauche->droite);
      if(node * parent = gauche->parent; parent)
         parent->poids = 1 + evaluer_poids(parent->gauche) +
                             evaluer_poids(parent->droite);
   }

   bool ajouter(const T &valeur) {
      node *p = racine,
         *q = nullptr;
      while (p) {
         q = p;
         if (valeur < p->valeur)
            p = p->gauche;
         else
            p = p->droite;
      }
      node *r = new node{ valeur };
      if (!q)
         racine = r;
      else {
         if (valeur < q->valeur)
            q->gauche = r;
         else
            q->droite = r;
         for (auto par = q; par; par = par->parent) // ICI
            ++par->poids;
         r->parent = q;
      }
      balancer(trouver(r->parent, valeur)); // ICI
      return true;
   }
private:
   bool contient(node *p, const T &valeur) const {
      if (!p) return false;
      if (valeur == p->valeur) return true;
      if (valeur < p->valeur)
         return p->gauche ? contient(p->gauche, valeur) : false;
      return p->droite ? contient(p->droite, valeur) : false;
   }
   node *trouver(node *p, const T &valeur) const {
      if (!p || valeur == p->valeur) return p;
      if (valeur < p->valeur)
         return trouver(p->gauche, valeur);
      return trouver(p->droite, valeur);
   }
public:
   template <class F>
   void visiter_preordre(F fct) { // depth-first
      visiter_preordre(fct, racine, std::string{});
   }
private:
   template <class F>
   void visiter_preordre(F fct, node *p, const std::string &prefixe) { // depth-first
      using namespace std;
      fct.entrer();
      if (!p) return;
      fct(p->valeur, prefixe + "[h: "s +
                                 to_string(hauteur(p->gauche) - hauteur(p->droite)) +
                                "; poids: "s + to_string(p->poids) + "] : "s);
      visiter_preordre(fct, p->gauche, "g"s);
      visiter_preordre(fct, p->droite, "d"s);
      fct.sortir();
   }
public:
   void supprimer(const T &valeur) {
      if (empty()) return;
      supprimer(racine, valeur);
   }
private:
   // précondition : p != nullptr
   bool supprimer_gauche(node *&p, const T &valeur) {
      supprimer(p->gauche, valeur);
      if (p)
         balancer(p);
      return true;
   }
   // précondition : p != nullptr
   bool supprimer_droite(node *&p, const T &valeur) {
      supprimer(p->droite, valeur);
      if (p)
         balancer(p);
      return true;
   }
   bool supprimer(node *&p, const T &valeur) {
      if (!p)
         return false;
      if (valeur < p->valeur)
         return supprimer_gauche(p, valeur);
      if (p->valeur < valeur)
         return supprimer_droite(p, valeur);
      if (p->gauche) {
         p->valeur = trouver_maximal(p->gauche)->valeur;
         return supprimer_gauche(p, p->valeur);
      }
      // ICI : p va mourir...
      if (p) {
         // ICI
         for (node *par = p->parent; par; par = par->parent)
            --par->poids;
      }
      node *victime = p;
      p = p->droite;
      if (p && p->parent == victime)
         p->parent = victime->parent;
      delete victime;
      return true;
   }
   node *trouver_minimal(node *p) {
      return !p ? p : p->gauche ? trouver_minimal(p->gauche) : p;
   }
   node *trouver_maximal(node *p) {
      return !p ? p : p->droite ? trouver_maximal(p->droite) : p;
   }
public:
   T minimum() const {
      if (empty()) throw 3;
      node *p = racine;
      for (; p->gauche; p = p->gauche)
         ;
      return p->valeur;
   }
   T maximum() const {
      if (empty()) throw 3;
      node *p = racine;
      for (; p->droite; p = p->droite)
         ;
      return p->valeur;
   }
   int hauteur() const {
      return hauteur(racine);
   }
private:
   int hauteur(node *p) const {
      if (!p) return 0;
      int hauteur_gauche = hauteur(p->gauche);
      int hauteur_droite = hauteur(p->droite);
      return 1 + (hauteur_gauche < hauteur_droite ?
         hauteur_droite : hauteur_gauche);
   }
   friend class iterator_naif;
   friend class iterator_raffine;
public:
   class iterator_naif {
      friend class arbre_equil_poids<T>;
      node *cur;
      arbre_equil_poids &src;
      iterator_naif(node *init, arbre_equil_poids &src)
         : cur{ init }, src{ src } {
      }
      iterator_naif(arbre_equil_poids &src)
         : cur{ nullptr }, src{ src } {
      }
      // ICI :
      // vos notes de cours, p.109
      // note : O(log n) par appel, donc O(n log n) pour un parcours
      //        complet... aussi long qu'un tri!
      node *suivant(node *p) {
         node *q = src.racine;
         node *sq = p->droite;
         if (sq)
            while (sq->gauche)
               sq = sq->gauche;
         else
            while (q != p)
               if (p->valeur < q->valeur)
                  q = (sq = q)->gauche;
               else
                  q = q->droite;
         return sq;
      }
   public:
      iterator_naif &operator++() {
         cur = suivant(cur);
         return *this;
      }
      iterator_naif operator++(int) {
         auto temp = *this;
         operator++();
         return temp;
      }
      bool operator==(const iterator_naif &autre) const {
         return cur == autre.cur;
      }
      bool operator!=(const iterator_naif &autre) const {
         return !(*this == autre);
      }
      T operator*() const { return cur->valeur; }
   };
   //
   // ICI
   //
   iterator_naif begin_naif() {
      return { trouver_minimal(racine), *this };
   }
   iterator_naif end_naif() {
      return { *this };
   }
   //
   // ICI
   //
   class iterator_raffine {
      friend class arbre_equil_poids<T>;
      node *cur;
      arbre_equil_poids &src;
      iterator_raffine(node *init, arbre_equil_poids &src)
         : cur{ init }, src{ src } {
      }
      iterator_raffine(arbre_equil_poids &src)
         : cur{ nullptr }, src{ src } {
      }
      // ICI :
      // vos notes de cours, p.110
      // note : O(1) amorti par appel, donc O(n) en moyenne pour
      //        un parcours complet... bien mieux!
      node *suivant(node *p) {
         node *sq;
         if (!p->droite)
            for (sq = p->parent;
               sq && sq->gauche != p;
               p = sq, sq = p->parent)
               ;
         else
            for (sq = p->droite; sq->gauche; sq = sq->gauche)
               ;
         return sq;
      }
   public:
      iterator_raffine &operator++() {
         cur = suivant(cur);
         return *this;
      }
      iterator_raffine operator++(int) {
         auto temp = *this;
         operator++();
         return temp;
      }
      bool operator==(const iterator_raffine &autre) const {
         return cur == autre.cur;
      }
      bool operator!=(const iterator_raffine &autre) const {
         return !(*this == autre);
      }
      T operator*() const { return cur->valeur; }
   };
   //
   // ICI
   //
   iterator_raffine begin_raffine() {
      return { trouver_minimal(racine), *this };
   }
   iterator_raffine end_raffine() {
      return { *this };
   }
};

#include <iostream>
#include <string>
using namespace std;

struct afficheur {
   int indent = -1;
   void entrer() {
      ++indent;
   }
   void sortir() {
      ++indent;
   }
   void operator()(int n) const {
      std::cout << string(2 * indent, ' ') << n << std::endl;
   }
};

struct afficheur_annote {
   int indent = -1;
   void entrer() {
      ++indent;
   }
   void sortir() {
      ++indent;
   }
   template <class T>
   void operator()(const T &val, const string &prefixe = {}) const {
      cout << string(2 * indent, ' ') << prefixe << val << endl;
   }
};

enum class operation { inserer, supprimer, quitter };
template <class T>
void mise_a_jour(arbre_equil_poids<T> &avlt, const T &val, operation op) {
   if (op == operation::inserer)
      cout << "Insertion de " << val << '\n';
   else if (op == operation::supprimer)
      cout << "Suppression de " << val << '\n';
   else
      return;
   cout << "Avant :\n";
   avlt.visiter_preordre(afficheur_annote{});
   if (op == operation::inserer)
      avlt.ajouter(val);
   else if (op == operation::supprimer)
      avlt.supprimer(val);
   cout << "Apres :\n";
   avlt.visiter_preordre(afficheur_annote{});
   cout << string(70, '-') << '\n';
}

#include <utility>

pair<operation, int> lire_choix() {
   auto est_valide = [](char c) {
      return c == 'a' || c == 's' || c == 'q';
   };
   cout << "Operation : [a]jouter, [s]upprimer, [q]uitter ? ";
   char c;
   while (cin.get(c) && !est_valide(c))
      ;
   if (c != 'q') {
      cout << "quelle valeur? ";
      if (int valeur; cin >> valeur)
         return c == 'a' ? pair{ operation::inserer, valeur } :
         pair{ operation::supprimer, valeur };
   }
   return { operation::quitter, 0 };
}

#include <algorithm>
#include <random>
template <class It>
   vector<int> brasser(It debut, It fin) {
      mt19937 prng{ random_device{}() };
      vector<int> v(debut, fin);
      shuffle(v.begin(), v.end(), prng);
      return v;
   }

int main() {
   arbre_equil_poids<int> a_eq_p{ 3.0 };
   int vals[]{ 25, 35, 30, 20, 15, 5, 28, 50, 45, 48, 43, 1, 3, 7, 2 };

   //const string tirets = string(70, '-');
   //cout << tirets << '\n'
   //     << "Debut des insertions:\n"
   //     << tirets << '\n';
   //for (auto n : vals) {
   //   mise_a_jour(a_eq_p, n, operation::inserer);
   //}
   //cout << '\n';
   //cout << tirets << '\n'
   //   << "Quelques statistiques:\n"
   //   << tirets << '\n';
   //if (!a_eq_p.empty()) {
   //   cout << "Noeud de valeur minimale : "
   //      << a_eq_p.minimum() << '\n';
   //   cout << "Noeud de valeur maximale : "
   //      << a_eq_p.maximum() << '\n';
   //}
   //cout << "hauteur : " << a_eq_p.hauteur() << endl;
   //// ICI
   //cout << "Parcours sequentiel (naif) :\n\t";
   //for (auto p = a_eq_p.begin_naif(); p != a_eq_p.end_naif(); ++p)
   //   cout << *p << ' ';
   //cout << '\n';
   //cout << "Parcours sequentiel (raffine) :\n\t";
   //for (auto p = a_eq_p.begin_raffine(); p != a_eq_p.end_raffine(); ++p)
   //   cout << *p << ' ';
   //cout << '\n';
   //cout << tirets << '\n'
   //    << "Debut des suppressions (pseudoaleatoires):\n"
   //    << tirets << '\n';

   //for (auto n : brasser(begin(vals), end(vals))) {
   //   mise_a_jour(a_eq_p, n, operation::supprimer);
   //}


   for (auto [choix, val] = lire_choix();
        choix != operation::quitter;
        tie(choix, val) = lire_choix()) {
      mise_a_jour(a_eq_p, val, choix);
   }
}

xxx

#include <iostream>
#include <vector>
#include <initializer_list>
#include <algorithm>
#include <iterator>
#include <functional>
#include <utility>
#include <cassert>
using namespace std;

//
// implémentation "maison" d'un monceau de T, avec
// un std::vector<T> comme substrat
//
namespace maison {
   template <class T, class Comp = std::less<>>
   class monceau {
      std::vector<T> substrat;
      // Complexité : O(n log n)
      template <class It>
         monceau creer_monceau(It b, It e) {
            monceau m;
            // opportunité d'optimisation ici
            m.substrat.reserve(std::distance(b, e)); // O(1) ou O(n)
            for (; b != e; ++b)
               m.ajouter(*b);
            return m;
         }
   public:
      using size_type = typename std::vector<T>::size_type;
      auto begin() { return std::begin(substrat); }
      auto begin() const { return std::begin(substrat); }
      auto end() { return std::end(substrat); }
      auto end() const { return std::end(substrat); }
      bool empty() const {
         return std::empty(substrat);
      }
      size_type size() const {
         return std::size(substrat);
      }
      monceau() = default;
      // Complexité : O(n log n)
      monceau(std::initializer_list<T> src) {
         // opportunité d'optimisation ici
         substrat.reserve(src.size());
         for (auto val : src) {
            ajouter(val);
         }
      }
      // Complexité : O(n log n)
      template <class It>
         monceau(It debut, It fin) {
            // opportunité d'optimisation ici
            substrat.reserve(std::distance(debut, fin));
            for (; debut != fin; ++debut) {
               ajouter(*debut);
            }
         }
      // Complexité : O(log n)
      void ajouter(const T &val) {
         using std::swap;
         Comp comp;
         substrat.push_back(val); // O(1) amorti
         size_type pos = size() - 1;
         // O(log n)
         while (pos > 0 && static_cast<int>(parent(pos)) >= 0 &&
                comp(substrat[parent(pos)], substrat[pos])) {
            swap(substrat[parent(pos)], substrat[pos]);
            pos = parent(pos);
         }
      }
      // Complexité : 
      // précondition : !empty()
      T extraire() {
         assert(!empty());
         auto ret = substrat.front();
         if (size() > 1) {
            auto m = creer_monceau(begin() + 1, end()); // O(n log n)
            // opportunité d'optimisation ici
            substrat.swap(m.substrat); // O(1)
            //for (size_type i = 0; i != m.size(); ++i) // O(n)
            //   substrat[i] = m.substrat[i];
         } else {
            substrat.pop_back(); // à tester
         }
         return ret;
      }
      // Complexité : O(n) mais... dans des cas dégénérés
      bool contient(const T &val) const {
         return empty() ? false : contient_impl(val, 0);
      }
   private:
      // Complexité : O(n) mais... dans des cas dégénérés
      bool contient_impl(const T &val, size_type n) const {
         if (!(n < size()))
            return false;
         if (Comp comp;
             !comp(val, substrat[n]) && !comp(substrat[n], val)) {
            return true;
         }
         return contient_impl(val, gauche(n)) || contient_impl(val, droite(n));
      }

      // précondition : n != 0
      static size_type parent(size_type n) {
         assert(n != 0);
         return (n - 1) / 2;
      }
      static size_type gauche(size_type n) {
         return 2 * n + 1;
      }
      static size_type droite(size_type n) {
         return 2 * (n + 1);
      }
   };
}
//
// implémentation "standard" d'un monceau de T, avec
// un std::vector<T> comme substrat
//
namespace standard {
   template <class T, class Comp = std::less<>>
   class monceau {
      std::vector<T> substrat;
   public:
      using size_type = typename std::vector<T>::size_type;
      auto begin() { return std::begin(substrat); }
      auto begin() const { return std::begin(substrat); }
      auto end() { return std::end(substrat); }
      auto end() const { return std::end(substrat); }
      bool empty() const {
         return std::empty(substrat);
      }
      size_type size() const {
         return std::size(substrat);
      }
      monceau() = default;
      // Complexité : O(n log n)
      monceau(std::initializer_list<T> src) : substrat{ src } {
         std::make_heap(std::begin(substrat), std::end(substrat), Comp{});
      }
      // Complexité : O(n log n)
      template <class It>
         monceau(It debut, It fin) : substrat{ debut, fin } {
            std::make_heap(std::begin(substrat), std::end(substrat), Comp{});
         }
      // Complexité : O(log n)
      void ajouter(const T &val) {
         substrat.push_back(val); // O(1) amorti
         std::push_heap(std::begin(substrat), std::end(substrat), Comp{});
      }
      // Complexité : O(log n) 
      // précondition : !empty()
      T extraire() {
         assert(!empty());
         auto ret = substrat.front();
         // O(log n)
         std::pop_heap(std::begin(substrat), std::end(substrat), Comp{});
         substrat.pop_back();
         return ret;
      }
      // Complexité : O(n) dans le pire cas
      bool contient(const T &val) const {
         return empty()? false : contient_impl(val, 0);
      }
   private:
      // Complexité : O(n) dans le pire cas
      bool contient_impl(const T &val, size_type n) const {
         if (!(n < size()))
            return false;
         if (Comp comp;
            !comp(val, substrat[n]) && !comp(substrat[n], val)) {
            return true;
         }
         return contient_impl(val, gauche(n)) || contient_impl(val, droite(n));
      }

      // précondition : n != 0
      static size_type parent(size_type n) {
         assert(n != 0);
         return (n - 1) / 2;
      }
      static size_type gauche(size_type n) {
         return 2 * n + 1;
      }
      static size_type droite(size_type n) {
         return 2 * (n + 1);
      }
   };
}

#include <string>

template <class M, int N, class It>
   void test(It b, It e, const std::string &nom) {
      M m;
      cout << "Test avec " << nom << " :\n";
      for (; b != e; ++b) {
         m.ajouter(*b);
         for (auto n : m)
            cout << n << ' ';
         cout << '\n';
      }
      // -1 et N+1 ne doivent pas être trouvés
      for (int i = -1; i != N + 1; ++i)
         if (!m.contient(i)) {
            cout << "Element " << i << " introuvable\n";
         }
      cout << "Ordre d'apparition dans le substrat :\n";
      for (auto n : m)
         cout << n << ' ';
      cout << '\n';
      cout << "Ordre conceptuel dans le monceau :\n";
      while (!m.empty()) {
         cout << m.extraire() << ' ';
      }
      cout << '\n';
   }




//
// applications des monceaux
//

//
// application classique : file prioritaire
//
template <class T,
          template <class, class> class S = maison::monceau,
          class Comp = std::less<>>
   class file_prioritaire {
      S<T,Comp> substrat;
   public:
      file_prioritaire() = default;
      file_prioritaire(std::initializer_list<T> src)
         : substrat{ src } {
      }
      // API fragile ici
      T extraire() {
         return substrat.extraire();
      }
      bool empty() const {
         return substrat.empty();
      }
   };

//
// application classique : heap sort
//

//
// version naïve
//
template <class T>
   std::vector<T> trier(std::vector<T> v) {
      using maison::monceau;
      monceau<T, std::greater<>> m{ std::begin(v), std::end(v) };
      v.clear();
      while (!m.empty()) {
         v.push_back(m.extraire());
      }
      return v;
   }

//
// version "in place"
//
template <class T>
   std::vector<T> trier_sur_place(std::vector<T> v) {
      using namespace std;
      if (v.empty()) return v;
      make_heap( begin(v), end(v) );
      for(auto e = end(v); begin(v) != e; e = prev(e)) {
         pop_heap(begin(v), e);
      }
      return v;
   }

#include <random>

int main() {
   using namespace std;
   // using standard::monceau;
   using maison::monceau;
   monceau<int> m;
   // données sources
   enum { N = 10 };
   vector<int> v;
   for (int i = 0; i != N; ++i)
      v.push_back(i);
   shuffle(begin(v), end(v), mt19937{ random_device{}() });
   test<standard::monceau<int>, N>(begin(v), end(v), "standard::monceau");
   test<maison::monceau<int>, N>(begin(v), end(v), "maison::monceau");

   file_prioritaire<string, maison::monceau> file{
      "J'aime", "mon", "prof", "et", "il", "me", "le", "rend", "bien"
   };
   while (!file.empty()) {
      cout << file.extraire() << ' ';
   }
   cout << '\n';
   cout << "Avant le tri :\n\t";
   for (auto n : v) cout << n << ' ';
   cout << '\n';
   cout << "Apres le tri :\n\t";
   for (auto n : trier(v)) cout << n << ' ';
   cout << '\n';
   cout << "Avant le tri :\n\t";
   for (auto n : v) cout << n << ' ';
   cout << '\n';
   cout << "Apres le tri sur place :\n\t";
   for (auto n : trier_sur_place(v)) cout << n << ' ';
   cout << '\n';
}