ძებნის ორობითი ხე

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


აამუშავეთ დაბალანსებული ორობითი ძებნის ხე.

 შესატანი მონაცემები:

 

 მონაცემები შეიცავს აღნიშნულ ხეზე მიმდინარე ოპერაციებს, (ოპერაციათა რაოდენობა არ აღემატება 100 000-ს).  თითოეული ხაზი უნდა შეიცავდეს მოცემული ფუნქციებიდან ერთს მაინც:

 

 ·         insert x - ამატებს x ელემენტს ორობითი ძებნის ხეზე. თუ x უკვე არსებობს, მაშინ პროგრამამ არაფერი მოიმოქმედოს.

 

 ·         delete x - შლის x ელემენტს ხიდან. თუ ხეზე არ არის x ელემენტი, პროგრამამ არაფერი მოიმოქმედოს.

 

 ·         exists x - თუ x ელემენტი ხეზე უკვე არსებობს, პროგრამამ დაბეჭდოს "true", სხვა შემთხვევაში კი - "false".

 

 გაითვალისწინეთ, რომ ყოველი შემავალი მთელი რიცხვი ნაკლებია 109-ზე.

 

გამოსატანი მონაცემები: პროგრამამ უნდა დაბეჭდოს ყველა ოპერაციის შედეგი exists ფუნქციიდან გამომდინარე,

 




მაგალითები

შესატანი მონაცემები
insert 2 insert 5 insert 3 exists 2 exists 4 delete 5 დაკოპირება
გამოსატანი მონაცემები
true false დაკოპირება