레드 블랙 트리(RBT)를 구현해야 한다. 다음은 레드 블랙 트리를 구현하기 위한 인터페이스 양식이다.

//자유롭게 수정해도 된다.
const int RED = 0;
const int BLACK = 1;

class cRedBlackTree;

class cNode{
friend class cRedBlackTree;
public:
cNode();
cNode(int t){key = t; left = right = 0; color = RED;}
private:
cNode* left;
cNode* right;
int key;
int color;
};

class cRedBlackTree{
public:
cRedBlackTree();
~cRedBlackTree();
void treeInsert(int d);
void treeDelete(int d);
void treePrint();
private:
cNode* root;
cNode* nil;

        //public에 있는 멤버 함수를 위해 자유롭게 구현한다.
};

• treeInsert(int d) : d를 트리에 삽입한다. 레드 블랙 트리 조건을 위배해서는 안 된다.
• treeDelete(int d) : 트리에서 d를 삭제한다. 삭제 후에도 트리는 레드 블랙 트리 조건을 충족해야 한다.
• treePrint() : 다음과 같은 방식으로 트리의 모든 원소를 출력한다. (전위 탐색)
  1. 한 줄에 하나의 노드만 출력한다. 이때 노드의 색상을 출력하고 빈칸 하나를 들인 다음에 노드의 값을 출력한다. 색상은 빨간색이면 RED, 검정색이면 BLACK으로 출력한다. ex) RED 1
  2. 자식 노드는 부모 노드보다 공백 4개만큼 들여서 출력한다.

위 양식의 구현과 입력을 처리하는 main 함수를 하나의 파일로 작성하여 제출한다.

입력

첫 줄에는 작업 명령에 대한 라인수 n이 들어온다.

다음 n 줄에는 다음 작업 명령이 들어온다.

• I x : x를 RBT에 삽입한다.
• D x : x를 RBT에서 삭제한다.

출력

작업 명령이 끝난 후에 트리를 조건에 맞게 출력한다.

예제 입력 1

10
I 10
I 9
D 10
I 8
I 7
I 6
D 7
I 5
I 4
D 4

예제 출력 1

BLACK 8
    BLACK 5
        RED 6
    BLACK 9

예제 입력 2

10
I 10
I 4
I 3
I 6
I 2
I 1
I 9
I 8
I 7
D 3

예제 출력 2

BLACK 4
    BLACK 2
        RED 1
    RED 9
        BLACK 7
            RED 6
            RED 8
        BLACK 10