Para este problema, se solicita implementar un árbol AVL de cadenas de caracteres que, además de tener las propiedades conocidas, nos permita guardar cadenas repetidas y poder conocer el número de veces que aparece cada una de estas cadenas. Se podrán realizar las siguientes operaciones: Insert(x), Find(x), FindMin(), FindMax(),Height(X), NumberNodes(X).
Entrada
La entrada comienza con un número \(Q\) que indica el número de operaciones. Cada una de las \(Q\) líneas traen la siguiente descripción:
Insert x: donde x es una cadena sin espacios no mayores a 20 caracteres de letras minúsculas (a-z).
Find x: Busca la cadena x en el árbol, esta operación debe imprimir el número de veces que ha sido insertada.
FindMin: Busca la cadena mínima en el árbol, esta operación debe imprimir el número de veces que ha sido insertada y a qué cadena corresponde.
FindMax: Busca la cadena máxima en el árbol, esta operación debe imprimir el número de veces que ha sido insertada y a qué cadena corresponde.
Height x: Busca la cadena en el árbol, esta operación debe imprimir la altura donde se encuentra el nodo correspondiente a la cadena.
NumberNodes X: Busca la cadena en el árbol, esta operación debe imprimir el número de descendentes del nodo X, 0 en caso de no existir dicha cadena.
Salida
El valor solicitado para cada operación, en el mismo órden en que se haya definido.
Restricciones
Insert(x): inserta una cadena x en el árbol AVL. Si la cadena ya existe, no se debe agregar nuevamente al árbol, sino que se debe guardar que ya existe 2 veces; si la misma cadena se agrega varias veces debe almacenar el número exacto de veces que aparece. Nota: Tenga en cuenta que la medida de comparación entre 2 cadenas para saber cuál es menor o mayor se debe hacer lexicográficamente.
Find(x): Se encarga de buscar la cadena x en el árbol. En caso que la cadena exista, se debe indicar el número de veces que ha sido insertada. En caso de no existir la cadena debe mostrar 0.
FindMin(): indica cuál es la cadena con menor orden lexicográfico y muestra el número de veces que ésta se ha insertado en el árbol, en caso de no existir debe devolver 0.
FindMax(): Busca la cadena con mayor orden lexicográfico y muestra el número de veces que ésta se ha insertado en el árbol, en caso de no existir debe devolver 0.
Height(x): Esta función debe mostrar cuál es la altura del nodo donde está almacenada la cadena x; -1 en caso de que no exista dicha cadena dentro del árbol. Nota: Tenga en cuenta que la altura de un nodo hoja es 0 y la altura de un determinado nodo es igual a la mayor altura de sus hijos + 1.
NumberNodes(X): Esta función debe mostrar el número de descendentes del nodo X incluyendo el nodo X. 0 en caso de no existir la cadena dentro del árbol.
Ejemplos
Entrada Ejemplo 1
13 Insert google Insert gmail Insert java Insert python Find gmail FindMin FindMax Height java Find yahoo Insert python FindMax NumberNodes google NumberNodes python
Salida Ejemplo 1
1 gmail 1 python 1 1 0 python 2 4 1