Ալգորիթմներ և Տվյալների Կառուցվածքներ

Գտնել k-րդ ամենափոքր արժեքը BST-ում

Տրված է դատարկ Բինար փնտրման ծառ (Binary Search Tree - BST), որտեղ դեռևս ոչ մի հանգույց չկա, և անհրաժեշտ է իրականացնել երկու տեսակի հարցումներ.
  1. insert x – մտցնել արժեքը x BST-ի մեջ
  1. smallest k – տպել BST-ում առկա k-րդ ամենափոքր տարրը
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով q հարցում, պետք է կատարի վերը նշված գործողությունները:

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ q (1 ≤ q ≤ 1000):
Հաջորդ q տողերում տեղակայված են հարցումները: Բոլոր insert հարցումների դեպքում x-ի արժեքը չի գերազանցում 10^9-ը (ըստ բացարձակ արժեքի): Բոլոր smallest հարցումների դեպքում k-ի արժեքը չի գերազանցում ծառի ընթացիկ չափը:

Ելք

Յուրաքանչյուր smallest հարցման համար ծրագիրը պետք է տպի BST-ի k-րդ ամենափոքր տարրը:

Օրինակներ

Մուտք
Ելք
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

To check your solution you need to sign in
Sign in to continue