트리의 각 노드가 갖는 자식노드의 수가 두 개 이하인(0, 1, 2중에 하나) 트리를 이진트리라고 한다.

이진트리에 아래와 같은 규칙으로 노드의 값이 저장된 트리를 이진 탐색 트리라고 한다.

어떤 노드에 저장된 수가 A라면,
그 노드의 왼쪽 서브트리에 속한 노드(들)에는 A보다 작은 수(들),
오른쪽 서브트리에 속한 노드(들)에는 A보다 큰 수(들)만 저장된다.

각 노드에 양의 정수 하나를 담고있는 이진 트리가 있을 때, 이 트리에 정수를 추가하는 문제를 생각해보자.

N개의 양의 정수가 주어진다. 주어진 모든 양의 정수는 서로 다르며 1~N 사이의 정수이다.
이제 주어진 첫 번째 수를 루트 노드로 놓고, 다른 나머지 수들을 순서대로 삽입하면서 이진 탐색 트리를 만들려고 한다.

다시 말해, 첫 번째 수를 제외한 모든 수에 대해서 insert(노드, 정수) 함수를 실행하는 것과 같다.

insert(노드, 정수) 함수는 아래와 같이 설명된다.

insert(노드 now, 정수 num):
    개수 cnt를 1 증가시킨다
    if num이 노드 now에 저장된 수보다 작다면 :
        if now의 왼쪽 자식이 없는 경우:
            num을 저장하는 새 노드를 만든 뒤, now의 왼쪽 자식으로 만든다.
        else :
            insert(now의 왼쪽 자식 노드, num)
    else :  // 노드 now에 저장된 수보다 num이 크다면
        if now의 오른쪽 자식이 없는 경우:
            num을 저장하는 새 노드를 만든 뒤, now의 오른쪽 자식으로 만든다.
        else :
            insert(now의 오른쪽 자식 노드, num)

새로운 수를 이진탐색트리에 추가할 때 마다 누적된 cnt값을 출력하는 프로그램을 작성하시오.

#3579 upload 99 done 9 how_to_reg 7

이진 탐색 트리(BST) timer 2s memory 128MB

#3579

이진 탐색 트리(BST) 2s 128MB