트리 ( Tree )
트리(Tree) 자료구조는 계층적인 데이터를 모델링하기 위해 사용되는 추상 데이터 타입이다. 트리는 노드(Node)와 이 노드들을 연결하는 간선(Edge)으로 구성된다.
특징
-
루트 노드(Root Node): 트리의 최상위에 위치하는 노드다. 이 노드는 부모가 없다.
-
자식 노드(Child Node): 다른 노드의 하위에 연결된 노드다. 각 노드는 여러 자식 노드를 가질 수 있다.
-
부모 노드(Parent Node): 특정 노드의 상위에 연결된 노드다.
-
잎 노드(Leaf Node): 자식이 없는 노드다. 트리의 말단에 위치한다.
-
간선(Edge): 노드를 연결하는 선이다. 부모 노드와 자식 노드를 연결한다.
-
깊이(Depth): 루트 노드로부터 특정 노드까지의 거리다.
-
높이(Height): 트리의 높이는 가장 긴 경로에 있는 노드의 깊이로 정의된다.
종류
-
이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가지는 트리다.
-
이진 탐색 트리(Binary Search Tree, BST): 이진 트리의 한 종류로, 왼쪽 자식은 부모 노드보다 작고, 오른쪽 자식은 부모 노드보다 큰 값을 가진다.
-
균형 트리(Balanced Tree): 트리의 높이가 최소화되도록 설계된 트리다. AVL 트리와 레드-블랙 트리가 이에 해당한다.
-
N-아리 트리(N-ary Tree): 각 노드가 N개 이하의 자식을 가질 수 있는 트리다.
-
트라이(Trie): 문자열 검색에 사용되는 특수한 트리 구조다.
예시
트리 구조의 간단한 예시
-
파일 시스템: 컴퓨터의 파일 시스템은 트리 구조로 조직된다. 여기서 각 폴더(디렉토리)는 노드로 간주되며, 이 폴더 내의 파일이나 하위 폴더는 자식 노드로 표현된다. 루트 디렉토리는 트리의 루트 노드가 된다.
-
웹사이트의 DOM(Document Object Model): 웹 페이지의 구조는 DOM을 통해 트리 구조로 표현된다. 이 트리는 HTML 태그를 노드로 가지며, 각 태그 내의 요소들이 자식 노드가 된다.
-
이진 탐색 트리: 데이터베이스 시스템에서 데이터 검색을 빠르게 하기 위해 이진 탐색 트리가 사용된다. 이 구조를 통해 데이터 삽입, 검색, 삭제 등의 작업을 효율적으로 수행할 수 있다.
-
의사 결정 트리(Decision Tree): 기계 학습에서 의사 결정 트리는 데이터 분류나 회귀 분석을 위해 사용된다. 각 노드는 결정을 나타내며, 데이터는 이 트리를 따라 최종 결정에 도달한다.
