[자료구조] 트리, 이진 탐색 트리

자료 출처: https://youtu.be/i5yHkP1jQmo

1. 트리

계층적인 구조를 표현할 때 사용할 수 있는 자료구조로, 다음과 같은 요소를 갖는다. 트리의 크기가 n일 때 전체 간선의 수는 n-1 개이다.

• 루트 노드 (root node)
• 단말 노드 (leaf node)
• 크기 (size): 트리에 포함된 모든 노드의 개수
• 깊이 (depth): 루트 노드부터의 거리
• 높이 (height): 깊이 중 최댓값
• 차수 (degree): 각 노드의 자식방향의 간선의 개수

2. 이진 탐색 트리 (Binary Search Tree)

이진 탐색을 쉽게 할 수 있게 해주는 트리로, 다음을 만족한다.
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

데이터의 조회 과정은 다음과 같다.

 

• 루트 노드부터 방문하여 탐색을 시작함
• 현재 노드와 값을 비교
• 원소를 찾으면 탐색을 종료