辅导Pikachu留学生、讲解AVL Tree、讲解Pikachu设计

Problem Description

Pikachu have many cards with different numbers and two containers A and B.

Pikachu asks Eevee to play an interesting card game. Before the game starts,

all the cards are in container A. In each round of the game, Pikachu can

choose to move a card from container A to container B or asks Eevee to

remove a card of a specific number from container B. When more and more

cards are moved to container B by Pikachu, Eevee feel difficult to remove a

card quickly. Now, you should implement an AVL Tree to help Eevee to solve

the problem.

Input

The first line of the input contains a positive integer n. Then n lines of

operations follow. If Pikachu choose to move a card with an integer d from

container A to container B, there will be a line written as "add d". We assume

that all the added integers are different. If Pikachu asks Eevee to remove a

card with a specific integer d from container B, there will be a line written as

"del d". The input has at most 50000 “add” or “del” operations.

Output

For each “del” operation, if the removed card of integer d is not in container B,

You should output “No card d”. After all operations have been processed, you

also need to output the AVL Tree from left to right, layer by layer as one line

(a kind of BFS traversal of the tree). You need to print a whitespace between

each element in the output.

Hint: To ensure the same tree structure, when you remove the node which

have two children, you should choose the successor node from right subtree

to replace it.

Language Library Requirements

C++ libraries for string manipulation and input/output streams are allowed. A

conservative list would be

<iostream>

<ostream>

<string>

<cstdlib>

<cstdio>

Copy

C++ libraries for containers and algorithms, including

<array>

<list>

<map>

<queue>

<set>

<stack>

<vector>

<algorithm>

<tuple>

Copy

are NOT allowed.

Sample

Input

7

add 4

add 5

add 3

del 1

add 2

add 1

del 2

Copy

Output

No card 1

4 3 5 1