Finde den k-kleinsten Wert in einem BST
Angenommen, Sie beginnen mit einem leeren Binary Search Tree (BST) ohne Knoten. Sie sollen zwei Arten von Anfragen bearbeiten:
insert x– fügt den Wertxin den BST ein
smallest k– gibt das k-kleinste Element im BST aus
Gegeben sind
q Anfragen. Sie sollen ein Programm schreiben, um diese Anfragen auszuführen.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne Zahl
q (1 ≤ q ≤ 1000).Die nächsten
q Zeilen enthalten die Anfragen. Für alle insert-Anfragen übersteigt der Wert von x nicht den Betrag von . Für alle smallest-Anfragen bleibt der Wert von k innerhalb der aktuellen Größe des Baums.Ausgabe
Für jede
smallest-Anfrage soll das k-kleinste Element im Binary Search Tree ausgegeben werden.Beispiele
Eingabe | Ausgabe |
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