AVL Strings

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


Exercise submitting


Select your language