Inserir i comptar claus repetides en un BST X90310

Donada la classe $dicc$ que permet gestionar diccionaris usant arbres binaris de cerca (BST) on les claus poden estar repetides, cal implementar els mètodes

    void insereix(const Clau &k);
    // Pre: Cert
    // Post: Insereix la clau k en el diccionari.

    nat quantes(const Clau &k) const;
    // Pre: Cert
    // Post: Retorna el nombre de claus iguals a k

Les claus són del tipus $Clau$ que admet una relació d’ordre total, és a dir, tenim una operació de comparació $<$ entre claus.

Cal enviar a jutge.org la següent especificació de la classe $dicc$ i la implementació dels mètodes 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;

template <typename Clau>
class dicc {
  // Diccionari implementat en un BST on les claus poden estar repetides.

  public:
    // Constructora per defecte. Crea un diccionari buit.
    dicc();

    // Destructora
    ~dicc();

    // Imprimeix el contingut del diccionari: Nombre d'elements i
    // totes les claus de més petita a més gran separades per un espai
    void print() const;

    void insereix(const Clau &k);
    // Pre: Cert
    // Post: Insereix la clau k en el diccionari.

    nat quantes(const Clau &k) const;
    // Pre: Cert
    // Post: Retorna el nombre de claus iguals a k

  private:
    struct node {
      Clau _k;      // Clau
      node* _esq;   // fill esquerre
      node* _dret;  // fill dret
    };
    node *_arrel;
    nat _n;       // Nombre d'elements del diccionari

    // Elimina els nodes del subarbre apuntat per p
    static void esborra_nodes(node* p);
    // Imprimeix ordenades les claus del subarbre apuntat per p
    static void print(node* p);

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

// Aquí va la implementació dels mètodes públics i dels mètodes 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ó dels mètodes $insereix$ i $quantes$ (el que normalment estarien separats en els fitxers $.hpp$ i $.cpp$).

Per testejar la classe disposes d’un programa principal que processa blocs que contenen un diccionari amb claus enteres seguit de comandes per comptar quantes claus són iguals a una donada.

Entrada

L’entrada conté varis blocs separats per línies amb 10 guions (———-). Cada bloc consisteix en una línia que conté una seqüències d’enters, són els elements que tindrà originalment el diccionari. A continuació segueixen vàries comandes, una per línea, amb el següent format (clau és un enter):

• quantes clau

Sortida

Per a cada línia d’entrada, escriu una línia amb el resultat:

• Si la línia és un diccionari, mostra el nombre de claus del diccionari i totes les claus de més petita a més gran separades per un espai.

• Si la línia és una comanda, mostra la comanda, el separador ": " i el resultat.

• Si la línia és el separador de blocs format per 10 guions, mostra els mateixos 10 guions.

Observació

Només cal enviar la classe requerida i la implementació dels mètodes $insereix$ i $quantes$. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Els mètodes $insereix$ i $quantes$ almenys han de tenir cost logarítmic (en el cas mig) per superar els jocs de prova privats.