Trie

• Las claves deben tener un alfabeto acotado de caracteres
• Búsqueda, inserción, borrado en $O(|k|)$.
• Árbol $k$-ario
• Significado almacenado en los nodos
• Partes de la clave en aristas

Interfaz

• $\texttt{definido} : \text{dicc}(K, S) \to \text{bool}$
• $\texttt{obtener} : \text{dicc}(K, S) ~d\times K~k \to S \qquad \{definido(d, k)\}$
• $\texttt{definir} : \text{dicc}(K, S) \times K \times S\to S$

Invariante de representación

• No llego por dos claves al mismo nodo
• Los nodos tienen un sólo padre
• No hay ciclos
• No nay nodos inútiles. Es decir, los nodos o bien tienen significado o bien tienen hijos

Implementación

#ifndef STRING_MAP_H
#define STRING_MAP_H

template <class T>
class string_map {
	public:
		string_map();
		string_map(const string_map<T>& d);
		string_map& operator=(const string_map<T>& d);
		T& operator[](const string &key);
		int count(const string &key) const;
		T& at(const string &key);
		void erase(const strin &key);
		int size() const;
		bool empty() const;
	private:
		struct Nodo{
			vector<Nodo*> siguientes;
			T* definicion;
			Nodo() : siguientes(256, nullptr),
							 definicion(nullptr) {}
			Nodo(T* def) : siguientes(256, nullptr),
										 definicion(def) {}
		};
		Nodo* raiz;
		int size;
};

#endif //STRING_MAP_H