#include <string>

class Diccionario {

   struct Nodo {
      string clave;
      int    dato;
      Nodo * izquierdo;
      Nodo * derecho;
      Nodo(const string &, int);
   };

   Nodo * raiz;
   int laTalla;

   void   insertar(const string &, int, Nodo * &);
   void   eliminar(const string &, Nodo * &);
   int  & buscar(const string &, Nodo *) const;
   Nodo * minimoEnSubarbol(Nodo *) const;
   void   mostrarOrdenados(Nodo *) const;
   void   vaciar(Nodo *);

 public:

   Diccionario();                       // O(1)
   void  insertar(const string &, int); // O(n); convirtiendo arbol en AVL seria O(log n)
   void  eliminar(const string &);      // O(n); convirtiendo arbol en AVL seria O(log n)
   int & buscar(const string &) const;  // O(n); convirtiendo arbol en AVL seria O(log n)
   void  mostrarOrdenados() const;      // O(n)
   int   talla() const;                 // O(1)
   void  vaciar();                      // O(n)

};