🌳 트리(Tree)

트리.png

정의

트리는 비선형 구조 자료구조로, 계층 구조를 추상화한 모델이다.

주요 특징 :

정보를 쉽게 검색하기 위해 저장할 때 유용하며, 계층 구조를 직관적으로 표현한다.

가계도, 회사 조직도, 파일 시스템 등이 좋은 예시이다.

특징	설명
부모-자식 관계	루트 노드를 제외한 모든 노드는 정확히 하나의 부모 노드를 가짐
간선의 개수	노드가 N개인 트리는 항상 N-1개의 간선을 가짐
경로의 유일성	루트에서 특정 노드로 가는 경로는 유일함 (중복 경로 없음)
계층성	노드들이 레벨(깊이)에 따라 계층적으로 구성됨

📌 트리의 종류와 구조에 따라 시간복잡도가 달라진다.

장점	단점
계층 구조를 직관적이고 효율적으로 표현	탐색 효율이 낮을 수 있음 (평균 O(n))
메모리 효율적 (간선이 최소: N-1개)	불균형 트리는 성능 저하 (한쪽으로 치우친 트리는 선형 리스트처럼 동작)
상위-하위 관계를 명확하게 표현	일반 트리는 실제 프로그래밍에서 거의 사용되지 않음
(대신 특수한 형태의 트리 사용)
트리를 기반으로 한 다양한 최적화된 자료구조 개발 가능
(이진 탐색 트리, 힙, AVL 트리 등)