트리 (Tree)

트리 (Tree)

노드들이 계층적으로 연결된 비선형 자료구조로, 하나의 루트 노드에서 시작하여 부모-자식 관계로 연결되며 사이클이 없는 연결 그래프

목적: 계층 구조 표현, 빠른 검색·삽입·삭제, 정렬된 데이터 유지

특징: 계층 구조, 사이클 없음, 루트, 부모-자식, 재귀적 구조

구성요소

• •루트(Root): 최상위 노드
• •노드(Node): 데이터+자식 포인터
• •간선(Edge): 노드 간 연결
• •리프(Leaf): 자식이 없는 노드
• •서브트리(Subtree): 노드와 그 자손들

용어

• •깊이(Depth): 루트부터 노드까지 간선 수
• •높이(Height): 루트부터 리프까지 최대 간선 수
• •레벨(Level): 같은 깊이의 노드들
• •차수(Degree): 자식 노드 수

종류: 이진 트리, 이진 탐색 트리(BST), AVL 트리, Red-Black 트리, B-트리, 힙

순회(Traversal)

• •전위(Preorder): Root → Left → Right
• •중위(Inorder): Left → Root → Right (BST는 정렬 순서)
• •후위(Postorder): Left → Right → Root
• •레벨순서(Level-order): BFS, 큐 사용

장점: 계층 표현, 빠른 검색(O(log n)), 정렬 유지, 범위 쿼리

단점: 불균형 시 성능 저하, 포인터 메모리, 구현 복잡도

적용사례: 파일 시스템, DOM, 조직도, 데이터베이스 인덱스, 컴파일러 파싱

비교: 트리(계층/사이클없음) vs 그래프(일반/사이클가능)

연관: 이진 트리, BST, 그래프, 순회, 재귀