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

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

Տրված է դատարկ Բինար փնտրման ծառ (Binary Search Tree - BST), որտեղ դեռևս ոչ մի հանգույց չկա, և անհրաժեշտ է իրականացնել երկու տեսակի հարցումներ.

  1. insert x – մտցնել արժեքը x BST-ի մեջ

  2. 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