TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

維護一棵節點值互異的二元搜尋樹(BST),並處理多種操作。

操作定義如下:

  • 0:輸出 preorder(根、左、右)。
  • 1:輸出 inorder(左、根、右)。
  • 2:輸出 postorder(左、右、根)。
  • 3 x:查詢是否存在 x,存在輸出 Yes,否則輸出 No
  • 4:輸出最小值;空樹輸出 none
  • 5:輸出最大值;空樹輸出 none
  • 6 x:插入 x,保證 x 目前不在樹中。
  • 7 x:刪除 x,保證 x 目前在樹中。
  • 8 x:輸出 x 的 successor,也就是樹中嚴格大於 x 的最小值。若 x 不在樹中或沒有 successor,輸出 none

Input Format

第一行有兩個整數 n q

第二行有 n 個互異整數,依序插入 BST。若 n = 0,此行為空行。

接下來有 q 行,每行是一個操作。

Output Format

遍歷、查詢與 successor 操作各輸出一行結果;插入與刪除不輸出。

遍歷元素之間以一個空白分隔,不要輸出行尾空白。若樹為空,遍歷輸出空行。

Sample Input 1

7 14
4 2 1 3 6 5 7
0
1
2
3 5
3 9
4
5
8 4
8 7
6 8
7 6
1
8 7
8 6

Sample Output 1

4 2 1 3 6 5 7
1 2 3 4 5 6 7
1 3 2 5 7 6 4
Yes
No
1
7
5
none
1 2 3 4 5 7 8
8
none

Hints

  • 0 <= n <= 2000
  • 1 <= q <= 2000
  • 節點值皆為 32-bit signed integer。
  • 樹中所有節點值皆互不相同。

Problem Source

tioj/problem/bst-all-operations

Subtasks

No. Testdata Range Score
1 0~2 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1