Thao tác trên cây tìm kiếm nhị phân

Submit solution
Points: 4
Time limit: 1.0s
Memory limit: 977M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Tichpx dạy về Cấu trúc dữ liệu cây tìm kiếm nhị phân quản lý ở mỗi nút là một số nguyên gồm các thao tác

Binary Tree Search

  1. Thao tác bổ sung một giá trị : Nếu trong cây chưa có thì bổ sung bằng cách duyệt từ gốc nếu nhỏ hơn nút đang xét thì bổ sung sang trái, nếu lớn hơn thì bổ sung sang phải cứ như thế đến nút trống thì bổ sung vào
  2. Thao tác loại bỏ một giá trị: Nếu có trong cây thì loại bỏ bằng cách nếu có cây con trái tại nút muốn loại bỏ thì đưa Max cây con trái lên vị trí loại bỏ và sau đó lại bỏ Max cây con trái, nếu không có cây con trái mà có cây con phải thì tìm Min của cây con phải đưa lên và loại bỏ Min của cây con phải. Nếu không có cả 2 cây con thì loại bỏ luôn nút đang chứa giá trị loại bỏ.
  3. Thao tác truy vấn 1 giá trị: Nếu không có trong cây thì in ra \(-1\) ngược lại in đường đi qua những nút từ vị trí truy vấn ngược về gốc.

Do mới học về Cây tìm kiếm nhị phân nên cài đặt các thao tác khá khó khăn đối với học trò của Tichpx bạn hãy lập trình giúp các học trò của Tichpx nhé.

Input

Dòng đầu là số nguyên dương n \((1<=n<=10^4)\) là số các thao tác đối với cây Tìm kiếm nhị phân ban đầu cây Rỗng thực hiện lần lượt n thao tác này.

n dòng tiếp theo mỗi dòng gồm 2 cặp số u và v trong đó u nhận các giá trị \(\{1,-1, 0\}\) tương ứng với các thao tác 1 là bổ sung v vào cây, -1 loại bỏ giá trị v khỏi cây và 0 là truy vấn in ra đường đi từ v ngược về gốc \((1<=v<=10^4)\)

Output

Đối với mỗi truy vấn dạng 0, xuất ra màn hình đường đi từ giá trị v ngược về gốc cây trên một dòng

Ví dụ

Input

20
1 3
1 5
1 2
1 8
0 2
-1 3
1 7
0 8
1 6
0 6
-1 8
0 6
1 9
0 9
1 3
0 3
-1 5
0 6
-1 9
0 9

Output

2 3 
8 5 2 
6 7 8 5 2 
6 7 5 2 
9 7 5 2 
3 5 2 
6 7 3 2 
-1
tichpx

Comments


  • 1
    TICHPX  commented on May 25, 2022, 1:46 p.m.

    Chú ý thao tác xóa, nếu không có cây con trái thì nó không bằng cây con phải luôn nhé và tương tự cho cây con phải vẫn phải thực hiện đúng quy trình


  • 1
    TICHPX  commented on Nov. 30, 2019, 2:03 p.m.

    Bài này có vẻ sai test cần kiểm tra lại


    • 1
      TICHPX  commented on May 25, 2022, 1:46 p.m.

      Thầy đã kiểm tra lại test vẫn đúng