자료구조 - 트리란 무엇인가?

트리란 무엇인가?

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

이진 탐색 트리 (Binary Search Tree)

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종
이진 탐색 트리의 특징:

• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
  • 부모 노드보다 왼쪽 자식 노드가 작습니다.
  • 부모 노드보다 오른쪽 자식 노드가 큽니다.

 

이진 트리란 무엇인가?

기본적으로 가장 많이 사용되는 비선형 자료구조는 이진 트리다.

배열 스택 큐 => 선형 자료구조
왼쪽 오른쪽으로 나누어져 있는 것 => 비선형 자료구조
왼쪽, 오른쪽 두 가지로 나눌 수 있는 것을 이진 트리라고 한다.

대표적인 예시로 데이터의 탐색 속도 증진을 위해 사용하는 구조

 

전위 순회, 중위 순회, 후위 순회란 무엇인가?

전위 순회

루트 노드가 가장 먼저 나오는 순회 방식
Root -> Left -> Right
자기 자신 -> 왼쪽 자식을 방문 -> 오른쪽 자식을 방문

중위 순회

각 루트 노드가 자식 노드의 사이에 위치
Left -> Root -> Right
왼쪽 자식을 방문 -> 자기 자신 -> 오른쪽 자식을 방문

후위 순회

루트 노드가 가장 마지막에 출력
Left -> Right -> Root
왼쪽 자식을 방문 -> 오른쪽 자식을 방문 -> 자기 자신