이진트리 순회란?
이진트리 순회를 알려면 일단 트리를 알아야 한다.
다행스럽게도(?) 이전에 트리에 대해서 간략하게 설명한 부분을 참고하면 좋을 것 같다.
추가적으로 이진 트리는 트리구조를 따라가는데, 자식 노드가 0 ~ 2개 사이인 트리를 의미한다.
이진 트리에는 다음과 같은 종류가 있다.
- 편향트리 : 좌 또는 우 한쪽 서브트리만 가지는 트리.
- 포화이진트리 : 모든 레벨에서 노드들이 모두 채워진 트리.
- 완전 이진트리 : 마지막 레벨을 제외하고 ( 다 채워져 있어도 됨) 모든 노드가 채워진 트리
그렇다면 왜 이진 트리를 사용할까??
이진트리는 선형 구조와 달리 검색, 삽입에서 연산 횟수를 대폭 줄일 수 있다.
선형구조(배열, Linked List, 스택, 큐, 덱(데크))는 일자로 되어있기 때문에 하나의 데이터 뒤에는 또 하나의 데이터가 있다.
때문에, 선형구조에서는 정렬이 되어있지 않을 때 최악 시간 복잡도는 O(n)이 된다.
하지만, 이진 트리는 탐색하는데 드는 최적의 시간복잡도는 O(log n)이 된다.
위 그림을 예로 들어서 대답해 보자. 위는 9개의 데이터가 있다.
"9"를 찾기 위해서 몇 번을 검색해야 할까?
- 우선 11보다 작기 때문에 왼쪽으로 간다.
- 그 다음 5보다 크기 때문에 오른쪽으로 간다.
- 9보다 크기 때문에 오른쪽으로 간다.
- 10이다!
- 트리의 레벨이 3이라면 (데이터의 갯수가 2의 3승 - 1) 세번,
- 트리의 레벨이 4라면(데이터의 갯수가 2의 4승 - 1) 네번만 가면 찾을 수 있다.
쭉쭉 가서 데이터가 2의 n승 -1개라면 n 번을 가면 찾을 수 있기 때문에 시간 복잡도는 log n 번이다.
이진 트리 순회
다시 돌아와서, 이진 트리의 순회에 대해서 알아보자.
개념
이진트리 순회는 자료를 검색하거나, 정렬하는 알고리즘에서 사용된다.
종류
1) 중위 순회 (In-Order)
좌측 노드 → 중간 노드 → 우측 노드 순으로 순회한다.
2) 전위 순회 (Pre-Order)
루트(근) 노드 → 좌측 노드 → 우측 노드 순으로 순회한다.
3) 후위 순회 (Post-Order)
좌측 노드 → 우측 노드 → 루트(근) 노드 순으로 순회한다.
'자격증 > 정보처리기사' 카테고리의 다른 글
자료구조 - 비선형구조 : 트리, 그래프 (1) | 2023.04.30 |
---|---|
자료구조 - 선형구조(2/2) 덱, 선형 리스트, 연결 리스트 (0) | 2023.04.21 |
자료 구조 - 자료구조 개념과 선형구조 (1/2) (0) | 2023.04.09 |
정보처리기사-소프트웨어의 분류와 특성 (0) | 2022.03.18 |