9 . BST Insert and Delete

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

維護一棵節點值互異的二元搜尋樹（BST），並處理插入、刪除與中序遍歷操作。

操作定義如下：

  • 1：輸出 inorder（左、根、右）。
  • 6 x：插入 x，保證 x 目前不在樹中。
  • 7 x：刪除 x，保證 x 目前在樹中。

刪除有兩個子節點的節點時，可以用右子樹的最小值取代它。

Input Format

第一行有兩個整數 n q。

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

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

Output Format

每個 1 操作輸出一行中序遍歷。元素之間以一個空白分隔，不要輸出行尾空白。若樹為空，輸出空行。

Sample Input 1

7 8
4 2 1 3 6 5 7
1
7 1
7 6
1
6 8
7 4
1
7 2

Sample Output 1

1 2 3 4 5 6 7
2 3 4 5 7
2 3 5 7 8

Hints

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

Problem Source

tioj/problem/bst-insert-delete

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
Submit
Back to Top