트리(Tree)

데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있음, 주로 계층 구조를 표현하는 용도로 많이 사용함

트리 구조

🔹루트 노드(root node)

노드 중 가장 위에 있는 노드

🔹간선(edge)

노드와 노드 사이를 이어주는 선

트리에서는 단방향 간선
루트로부터 각 노드까지 경로는 유일
레벨 : 루트 노드로부터 특정 노드까지 거쳐가는 최소한의 간선 수

🔹부모-자식 관계

간선으로 연결된 노드들

부모 노드 (parent node) : 상대적으로 위에 있는 노드
자식 노드(child node) : 상대적으로 아래에 있는 노드
형제 노드(sibling ndoe) : 같은 부모를 갖는 노드

🔹 리프 노드(leaf node)

자식이 없는 노드, 자식이 없는 말단 노드

🔹차수(degree)

특정 노드에서 아래로 향하는 간선의 개수

이진 트리(binary tree)

※ 다양한 트리가 있지만 코딩 테스트에서는 이진트리만 알고 있어도 충분함

이진 트리 : 모든 노드의 최대 차수가 2를 넘지 않는 트리

이진 트리 순회

순회 : 어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것

🔹전위 순회

전위 순회는 현재 노드를 부모 노드로 생각했을 때 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문

🔹중위 순회

현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순서로 방문

거쳐 가는 노드는 거치기만 하고 ‘방문’하지 않음
정렬된 순서대로 값을 가져올 때 사용

※ 방문 : 탐색에서 방문은 탐색을 마친 상태, 탐색 과정에서 지나치는 것과 아닌 것을 구분하기 위해

🔹후위 순위

현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 → 오른쪽 자식 → 부모 노드 순서로 방문

노드를 삭제할 때는 부모를 먼저 삭제하면 안 되므로 자식 노드부터 방문하는 특성이 있는 후위 순위는 트리 삭제에 자주 활용됨

배열로 표현하기

배열 : 선형 자료구조 / 트리 : 계층 자료구조
장점 : 구현 난이도는 쉬우므로 메모리가 넉넉하다면 구현 시간을 단축하는 용도로 추천
단점 : 안 쓰는 배열 공간에 대한 메모리 낭비

포인터로 표현하기

노드는 노드의 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 가짐

장점 : 포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않아 메모리 공간 낭비 ❌
단점 : 실제 노드를 따라가도록 구현해야 하므로 구현 난이도가 배열보다 높음

인접 리스트로 표현하기

정점의 번호(수)만큼 리스트를 만들어야 함

리스트는 해당 정점에서 연결된 노드의 변호가 됨
장점1 : 자식 노드가 2개 이상일 경우도 표현하기 좋음
장점2 : 메모리 공간이 크게 낭비되지 않음
장점3 : 어떤 정점에서 이동할 수 있는 다음 정점을 빠르게 탐색할 수도 있어 시간 복잡도 면에서 이점이 많음
트리, 그래프 등의 문제에서 많이 사용함

이진 탐색 트리(binary search tree)

데이터 크기를 따져 크기가 작으면 왼쪽 위치에, 크거나 같으면 오른쪽 자식 위치에 배치함

데이터를 전부 삽입한 후 정렬하는 것이 아닌 데이터를 하나씩 탐색하면서 이진 탐색 트리를 구축
삽입과 동시에 정렬
장점 : 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로 빠르게 검색 가능
시간 복잡도(트리 균형이 잡힌 경우) : $O(\log N)$
시간 복잡도(트리 균형이 안 잡힌 경우) : $O(N) \sim$ 배열

※균형이 잡힌 경우 : 왼쪽과 오른쪽 서브 트리의 높이 차가 1인 경우

※균형이 안 잡힌 경우 : degenerate binary tree 처럼 한 쪽으로 치우쳐진 트리인 경우

이진 탐색 트리 구축

이진 탐색 트리 탐색하기

'코딩테스트 > 개념정리' 카테고리의 다른 글

[ 알고리즘 ] Dynamic Programming (0)	2025.06.22
[ 알고리즘 ] 완전탐색(재귀) - 백트래킹, pruning (1)	2025.06.13
[ 알고리즘 ] 재귀(Recursion) (0)	2025.04.25
[ 자료구조 ] Hash (0)	2025.04.20
[ 자료구조 ] Queue (0)	2025.04.06

[ 자료구조 ] 트리(Tree)