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

Փնտրման Բինար Ծառում (BST) առավելագույն հանգույց

Ենթադրենք, որ ունենք դատարկ Փնտրման Բինար Ծառ (BST), որի մեջ դեռևս որևէ հանգույց ներդրված չէ։ Ձեզ առաջարկվում է իրականացնել երեք տեսակ հարցում.

  1. insert x – տեղադրել արժեքը x BST-ում

  2. max – արտածել BST-ի մեջ առկա ամենամեծ արժեքը

  3. print – տպել BST-ի հանգույցները post-order traversal կարգով

Տրված են q հարցումներն (queries), և խնդրում ենք գրել ծրագիր, որը կկատարի վերը նշված գործողությունները։

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ q (1 ≤ q ≤ 1000)։

Հաջորդ q տողերում գտնվում են հարցումները։ Բոլոր insert հարցումների դեպքում x-ի բացարձակ արժեքը չի գերազանցում -ը։

Ելք

Յուրաքանչյուր max հարցման դեպքում ծրագիրը պետք է տպի BST-ում առկա առավելագույն արժեքը առանձին տողով։

Յուրաքանչյուր print հարցման դեպքում պետք է տպվի ծառի post-order traversal-ը, причем արժեքները պետք է բաժանվեն բացատով։

Օրինակ

Input

Մուտք

7 insert 2 insert 1 max insert 0 max insert 4 print

7 insert 2 insert 1 max insert 0 max insert 4 print

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