Trie primer fill-següent germà. Elimina clau. T36457

Donada la classe $dicc$ que permet gestionar diccionaris on només hi guardem claus úniques usant tries implementats amb la tècnica d’arbres generals amb punters a primer fill i següent germà, cal implementar aquest mètode:

  void elimina(const string &k);
  // Pre: True
  // Post: S'ha eliminat la clau k del diccionari. Si no hi era, no fa res.

Les claus són del tipus string i els símbols utilitzats per construir el trie són els chars de les claus. S’ha usat el char especial ’#’ per indicar la fi de la clau.

Cal enviar a jutge.org la següent especificació de la classe $dicc$ i la implementació del mètode dins del mateix fitxer. La resta de mètodes públics i privats ja estan implementats.

#include <iostream>
using namespace std;
typedef unsigned int nat;

class dicc {
  // Diccionari implementat amb un Trie primer fill-següent germà.
  // Els germans estan ordenats de menor a major.
  public:
    // Constructora per defecte. Crea un diccionari buit.
    dicc();

    // Destructora
    ~dicc();

    void insereix(const string &k);
    // Pre: True
    // Post: Insereix la clau k en el diccionari. Si ja hi era, no fa res.

    void print(ostream &os) const;
    // Pre: True
    // Post: Imprimeix tot el contingut del Trie pel canal de sortida os
    //       Horitzontalment s'imprimeix el següent germà de cada node
    //       Verticalment s'imprimeix el primer fill de cada node

    void elimina(const string &k);
    // Pre: True
    // Post: S'ha eliminat la clau k del diccionari. Si no hi era, no fa res.

  private:
    struct node {
      char _c;   // Símbol posició i-èssima de la clau
      node* _pf; // Primer fill, apunta a símbols de la següent posició
      node* _sg; // Següent germà, apunta a símbols de la mateixa posició
      node(const char &c, node* pf = nullptr, node* sg = nullptr);
    };
    node* _arrel;

    static void esborra_nodes(node* t);
    static node* insereix(node *t, nat i, const string &k);
    static void print(node* t, ostream &os, string prefix);

    // Aquí va l'especificació dels mètodes privats addicionals
};

// Aquí va la implementació del mètode públic elimina i privats addicionals

Degut a que jutge.org només permet l’enviament d’un fitxer amb la solució del problema, en el mateix fitxer hi ha d’haver l’especificació de la classe i la implementació del mètode $elimina$ (el que normalment estarien separats en els fitxers $.hpp$ i $.cpp$).

Per testejar la classe disposes d’un programa principal que insereix claus en el trie, mostra el contingut del trie, després elimina una o més claus i torna a mostrar el contingut del trie.

Entrada

L’entrada conté una llista de strings separats per canvis de línia: són les claus que tindrà el diccionari. Després conté una línea amb guions ("———-") i una segona llista de strings separats per canvis de línia: són les claus que s’eliminaran del diccionari.

Sortida

Mostra el contingut del trie abans i després d’eliminar les claus del trie. Les dues visualitzacions del trie estan separades per una línea amb guions ("———-").

Observació

Només cal enviar la classe requerida i la implementació del mètode $elimina$. Pots ampliar la classe amb mètodes privats. Al principi de cada mètode implementat, dins d’un comentari, cal indicar el cost temporal en funció de $n$ (nombre de claus del diccionari), $s$ (nombre de símbols de l’alfabet) i/o $l$ (nombre mig de símbols que té una clau). Segueix estrictament la definició de la classe de l’enunciat.