[JAVA] 재귀 - 이진 탐색 트리(Binary Search Tree)의 삽입 - (1)

1. 이진트리, 이진탐색트리란?

각 노드의 자식노드 수가 최대 2개까지만 존재하는 트리이다.

글로만 쓰면 이해가 안가므로, 그림 투척!

위의 트리는 맨 밑 노드(리프노드 - Leaf Node)를 제외한 모든 각 노드가 자식

노드를 2개씩 갖고있는데, 이런 트리를 완전트리 라고 한다.

완전트리가 아니더라도 자식노드가 2개 이하이면 이진트리이다. 아래 트리처럼!!

요런 모양을 편향트리? 왼쪽 경사 트리? 변질 트리? 등으로 부른다.

어쨌든, 이진트리에 대한 정의는 이정도이다.

그렇다면, 이진탐색트리(Binary Search Tree)는 무엇인가?

저 위의 그림들이 바로 이진탐색트리이다.

위에 있는 트리를 보면 숫자가 들어있다.

루트노드의 왼쪽 아래에는 루트보다 작은 숫자가, 

루트노드의 오른쪽 아래에는 루트보다 큰 숫자가 들어간다.

아래 노드들을 루트로 놓고 보면 왼쪽 자식엔 작은 수, 오른쪽엔 큰 수를 놓는게 반복됨을 볼 수 있다.

2. 이진탐색트리 삽입 알고리즘

문제 : 트리에 넣을 숫자들을 입력 받아 이진탐색트리를 만들어라.

위에서 이진탐색트리에 대한 정의를 설명한 것과 같이, 

숫자를 입력받고, 왼쪽엔 작은수, 오른쪽엔 큰 수를 넣는 것으로 흘러갈 것이다.

그런데 가만보면 왼쪽엔 작은수, 오른쪽엔 큰 수를 넣는 것   <= 요것이 반복되고 있다.

반복되는 것은? 재귀를 사용할 수 있다는 뜻이다.

흐름을 정리해보면 다음과 같다.

1) Root에 값이 없으면 Root에 값을 넣는다.

2) Root에 값이 있으면, 

   입력된 값이 Root보다 크면 오른쪽에 넣고, 작으면 왼쪽에 넣는다.

3) 오른쪽 혹은 왼쪽에 값이 이미 들어있으면,

    입력된 값과 비교해서 크면 오른쪽에 넣고, 작으면 왼쪽에 넣는다.

4) 오른쪽 혹은 왼쪽에 값이 이미 들어있으면,

    입력된 값과 비교해서 크면 오른쪽에 넣고, 작으면 왼쪽에 넣는다.

..... 

확실히 반복되는 흐름을 볼 수 있다.

우리는 반복되지 않는 1,2번을 코드로 만든 후 3번 이후를 재귀 호출 시키면 된다.

소스까지 넣으면 너무 길어질 것같아서 다음편으로 나누겠음 ㅎㅎ

다음편 - http://marobiana.tistory.com/82