Փնտրման Բինար ծառի (BST) վրա հարցումների կատարում
Ունենք մեկդيان դատարկ Փնտրման Բինար ծառ (BST), որտեղ չկան որևէ գագաթներ (nodes): Պետք է իրականացվեն հետևյալ տիպի 3 հարցումներ (queries).
insert x- ավելացնելxարժեքը BST-ումsearch x- ստուգել, թե արդյոքxարժեքը կա BST-ումprint- տպել BST-ի արժեքները միջին շրջայցով (in-order traversal)
Տրված է q հարցում: Ձեզ խնդրում են գրել ծրագիր, որը պետք է կատարի նշված հարցումները:
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ q (1 ≤ q ≤ 1000):
Հաջորդ q տողերը պարունակում են հարցումներ: Բոլոր insert և search հարցումների դեպքում x-ի արժեքը չի գերազանցում -ը հասկանալով բևեռային գումարով (absolute value):
Ելք
Յուրաքանչյուր search հարցման դեպքում, եթե BST-ում առկա է համապատասխան արժեքը, ծրագիրը պետք է տպի Yes, հակառակ դեպքում — No (յուրաքանչյուրն առանձին տողում):
Յուրաքանչյուր print հարցման դեպքում, ծրագիրը պետք է տպի BST-ի միջին շրջայցը, որտեղ արժեքները բաժանված են բացատով:
Օրինակներ
Input | Output |
|---|---|
6 insert 2 insert 1 search 3 insert 0 print search 1 | No 0 1 2 Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB