이진트리란 ?
이진트리는 각 노드가 최대 2개의 자식을 갖는 트리를 말합니다. 즉, 각 노드는 자식이 없거나 한개 이거나 두개만을 갖는 것 입니다.
이진탐색트리의 특징
- 각 노드에 중복되지 않는 키가 있다
- 루트노드의 왼쪽 서브트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 구성된다.
- 루트노드의 오른쪽 서브트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 구성된다.
- 이진탐색트리는 기존 이진트리보다 탐색이 빠르다.
- 이진탐색트리의 탐색연산은 트리의 높이가 h 라면 O(h) 의 시간 복잡도를 가진다.
이진탐색트리의 탐색과정
- 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이면 탐색을 종료한다
- 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
- 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브트리로 탐색을 진행한다.
서브트리 : 전체 트리에 속한 작은 트리
노드 : 데이터의 인덱스와 value를 표현하는 요소
위 과정을 찾고자 하는 값을 찾을때 까지 반복해서 진행한다.
만약 값을 찾지 못한다면 그대로 종료한다.
이러한 탐색 과정을 거치면 최대 트리의 높이(h)만큼 탐색이 진행되게 된다.
이진탐색 예시 링크텍스트
.
.
.
직접 문제를 통해 알아!! 보았다 !!
고통의 시작..
백준 5639번 - 이진검색트리
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int[] tree = new int[10000];
// start : 현재 서브트리의 루트노드 , end : 해당 서브트리의 끝노드의 다음 인덱스
static void postOrder(int start, int end) {
int i;
// 서브트리가 비어있거나 노드가 하나인 경우는 바로 리턴해 아무 작업도 수행하지 않는다.
if (start >= end) {
return;
}
for (i = start+1; i < end; i++) {
if(tree[start] < tree[i] )break;
}
// i를 기준으로 왼쪽 서브트리를 후위순회
postOrder(start+1, i);
// i를 기준으로 오른쪽 서브트리를 후위순회
postOrder(i, end);
// 현재 노드값 출력
System.out.println(tree[start]);
return ;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int i = 0;
String input;
// 입력받기
while((input = br.readLine()) != null) {
tree[i++] = Integer.parseInt(input);
}
// 후위순회 호출
postOrder(0, i);
}
}코드에 대해 직접 풀어본 풀이,,
재귀함수과 재귀호출에 대한 개념이 많이 아주 많이 부족한 상태에서 재귀호출이 2번이나 일어나는 문제를 풀려하니까 아주 힘들었다,,
거의 2일넘게해서 어떻게 알고리즘이 풀어지는지 이해하고 풀어봤지만 확실한 이해와 반복적으로 문제를 풀어봐야겠다.
Backend Developer