8619: ALDS1_8_C : Binary Search Tree III
[Creator : ]
Description
Write a program which performs the following operations to a binary search tree T by adding delete operation to B: Binary Search Tree II.
- insert k: Insert a node containing k as key into T.
- find k: Report whether T has a node containing k.
- delete k: Delete a node containing k.
- print: Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.
- If z has no children, we modify its parent z.p to replace z with NIL as its child (delete z).
-
If z has only a single child, we "splice out" z by making a new li
nk between its child and its parent. - If z has two children, we splice out z's successor y and replace z's key with y's key.
Input
In the first line, the number of operations m is given.
In the following m lines, operations represented by insert k, find k, delete k or print are given.
In the following m lines, operations represented by insert k, find k, delete k or print are given.
Output
For each find k operation, print "yes" if T has a node containing k, "no" if not.
In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key
In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key
Constraints
The number of operations ≤500,000
The number of print operations ≤10
−2,000,000,000≤key≤2,000,000,000
The height of the binary tree does not exceed 100 if you employ the above pseudo code.
The keys in the binary search tree are all different.
The number of print operations ≤10
−2,000,000,000≤key≤2,000,000,000
The height of the binary tree does not exceed 100 if you employ the above pseudo code.
The keys in the binary search tree are all different.
Sample 1 Input
18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print
Sample 1 Output
yes
yes
yes
no
no
no
yes
yes
1 2 3 7 8 22
8 2 1 3 7 22
1 2 8 22
8 2 1 22