Trovare il k-esimo valore più piccolo in un BST
Si dispone di un albero di ricerca binaria (BST) inizialmente vuoto, senza alcun nodo. L’obiettivo è di eseguire due tipi di query:
insert x- inserisce il valorexnel BST.
smallest k- stampa il k-esimo valore più piccolo presente nel BST.
Dato un numero
q di query, bisogna scrivere un programma che le gestisca tutte.Input
La prima riga dell’input contiene un singolo numero
q (1 ≤ q ≤ 1000).Le successive
q righe contengono le query. Per tutte le query di tipo insert, il valore di x non supera in valore assoluto . Per ogni query di tipo smallest, il valore di k non supera la dimensione corrente dell’albero.Output
Per ogni query
smallest, il programma deve stampare il k-esimo valore più piccolo presente nel BST.Esempi
Input | Output |
8
insert 2
insert 1
smallest 1
smallest 2
insert 10
insert 20
smallest 3
smallest 2 | 1
2
10
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB