이진 탐색 트리 정의, 동작 방법, 트리의 순회 (전위, 중위, 후위)

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

이진 탐색 트리

트리란
트리는 가계도와 같은 "계층적인 구조"를 표현할 때 사용할 수 있는 자료구조.
 

 [트리 관련 용어]
 루트 노드 : 부모가 없는 최상위 노드
 단말 노드 : 자식이 없는 노드
 크기 : 트리에 포함된 모든 노드의 개수
 깊이 : 루트 노드부터의 거리
 높이 :  깊이 중 최댓값
 차수 : 각 노드의 (자식 방향) 간선 개수

 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개임.

 

 

이진 탐색 트리

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종임.
 이진 탐색 트리의 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
  - 부모 노드보다 왼쪽 자식 노드가 작습니다.
  - 부모 노드보다 오른쪽 자식 노드가 큽니다.

 

 이진 탐색 트리가 이미 구성되어 있다고 가정하고 데이터를 조회하는 과정을 살펴본다.
 찾고자 하는 원소 37
 

            30
     17           48
 5    23      37  50

 (1) 루트 노드 부터 방문해 탐색 진행.
  (1-1) 현재 노드(30)와 찾는 원소 37 비교
  (1-2) 찾는 원소가 더 크므로 오른쪽 방문
 (2) 현재 노드와 값을 비교 (48)
  (2-1) 현재 노드와 찾는 원소를 비교
  (2-2) 찾는 원소가 더 작으므로 왼쪽을 방문
 (3) 현재 노드(37)과 찾는 원소를 비교
  (3-1) 원소를 찾았으므로 탐색 종료.

 

트리의 순회(Tree Traversal)
 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미함.
  -트리의 정보를 시각적으로 확인할 수 있음.

 

 '대표적인 트리 순회' 방법은 다음과 같다.
  "전위 순회(pre-order traverse)" : 루트를 먼저 방문
  "중위 순회(in-order traverse)" : 왼쪽 자식을 방문한 뒤에 루트를 방문.
  "후위 순회(post-order traverse)" : 오른쪽 자식을 방문한 뒤 루트를 방문.

              A
      B             C
 D     E        F     G

 전위 순회 : A - B - D - E - C -F - G
 중위 순회 : D - B - E - A - F - C - G
 후위 순회 : D - E - B - F - G -C -A

 

 

---