트리(Tree)는 계층적 구조를 가진 비선형 자료구조이다. 일반적으로 나무를 거꾸로 뒤집은 형태로, 하나의 노드에서 시작해 여러 하위 노드로 가지처럼 뻗어나가는 구조이다.
비선형 / 계층적 구조란?
- 비선형은 데이터가 일렬로 나열되지 않은 구조를 뜻한다. 배열이나 연결 리스트처럼 순서대로 하나씩 연결된 선형 구조와 달리 한 노드가 여러 노드와 연결될 수 있는 구조이다.
- 계층적 구조란 '위와 아래' 로 구분되어 '부모-자식'로 연결된 구조를 뜻한다. 상위 개념에서 하위 개념으로 내려가는 단계적 구조이다.
선형구조와 비선형 구조의 차이
| 정의 | 데이터가 일렬(1차원)로 나열 | 데이터가 계층적, 네트워크형으로 연결됨 |
| 구조 형태 | 앞뒤(순차) 관계 | 부모-자식, 여러 연결 관계 |
| 대표 예시 | 배열, 리스트, 스택, 큐 | 트리, 그래프 |
| 접근 방식 | 순차적으로 접근 | 계층적(큰 구조를 위에서부터 아래 단계로 차근차근 나누어 살펴보는 방식)으로 접근 |
용어
-
루트: 부모가 없는 최상위 노드
-
부모: 노드A에서 노드B로 가는 간선이 있을 때 A를 B의 부모라고 한다.
-
자식: 노드A에서 노드B로 가는 간선이 있을 때 B를 A의 자식이라고 한다.
-
형제: 같은 부모를 갖는 노드들
-
단말노드: 자식이 없는 노드
-
깊이/레벨: 루트에서 해당 노드으로 가는 최단 경로의 길이
-
높이: 노드들의 깊이의 최댓값
-
너비: 각 레벨에 속한 노드의 수의 최댓값
- 내부노드 : 하나 이상의 자식 노드를 가지고 있는 노드
트리 종류
평향트리 : 모든 노드들이 자식을 하나만 가진 트리이다
왼쪽방향으로만 자식을 하나씩만 가질 때 왼쪽 평향 트리, 오른쪽으로만 방향을 가질 때 오른쪽 평향 트리라고 한다.
이진트리(Binary tree)
각 노드가 최대 2개의 자식 노드를 가지는 트리 구조이다. 즉, 하나의 노드는 왼쪽 자식과 오른쪽 자식을 가질 수 있다.
최대 노드의 개수에 따라 n진트리로 종류가 달라진다.
포화이진트리(full binary tree)
포화이진트리는 모든 레벨이 꽉 차 있으며 모든 단말노드가 동일한 레벨에 존재하는 이진트리이다.
즉, 트리의 모든 내부 노드가 자식 노드를 정확히 두 개씩 가지고 단말노드는 모두 같은 층에 위치한 구조이다.
완전이진트리(full binary tree)
완전이진트리는 마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며 마지막 레벨의 노드들이 왼쪽부터 순서대로 채워져 있는 이진트리이다.
Q. 완전이진트리는 배열로 구현할 수 있는데, 왜 BST는 배열로 구현하기 어려울까?
완전이진트리는 노드가 왼쪽부터 빈틈없이 채워지는 구조라 인덱스로 부모·자식의 위치를 정확히 계산할 수 있지만,
BST는 삽입 순서에 따라 모양이 달라지고 빈 공간이 불규칙하게 생기기 때문에 배열 인덱스 구조를 유지하기 어려워서 배열로 구현하기 적합하지 않다.
특징
- 마지막 레벨의 노드는 왼쪽부터 연속적으로 채워진다.
- 가운데나 오른쪽이 비어 있으면 안 된다.
- 트리의 높이가 최소화되어 효율적인 메모리 구조를 가진다.
이진탐색트리(Binary Search Tree, BST)
이진탐색트리는 왼쪽 서브트리에는 작은 값이, 오른쪽 서브트리에는 큰 값이 저장되는 정렬된 이진트리이다.
기본 규칙
- 왼쪽 자식 노드의 값은 부모보다 작아야 한다.
- 오른쪽 자식 노드의 값은 부모보다 커야 한다.
- 중복값은 일반적으로 허용하지 않는다.
사용 사례
운영체제에서 폴더와 파일을 관리할 때 트리 구조를 사용한다. 루트 디렉터리에서 하위 폴더와 파일이 뻗어나가는 형태이므로 트리 구조와 동일하다.
