트리의 종류와 특징

기술노트

트리 (Tree)의 종류와 특징

트리(Tree)는 노드(Node)와 간선(Edge)으로 이루어진, 사이클이 없는 계층적 비선형 자료구조입니다. 하나의 루트(Root) 노드에서 시작하여, 각 노드는 0개 이상의 자식 노드를 가질 수 있으며, 데이터베이스, 파일 시스템, 자료 검색 등 다양한 분야에서 효율적인 데이터 관리를 위해 사용됩니다.

🌳 트리의 기본 특징 및 용어

  • 계층적 구조 : 부모-자식 관계를 가지는 계층적 데이터를 표현하는 데 적합합니다.
  • 비순환 그래프 : 사이클이 없는 연결 그래프(Acyclic Connected Graph)의 일종입니다.
  • 주요 용어

> * 루트 (Root) : 트리의 최상위 노드. > * 리프 (Leaf) : 자식 노드가 없는 단말 노드. > * 내부 노드 (Internal Node) : 리프 노드가 아닌 노드. > * 깊이 (Depth) : 루트에서 특정 노드까지의 간선 수. > * 높이 (Height) : 특정 노드에서 리프 노드까지의 가장 긴 경로의 간선 수. (트리의 높이는 루트의 높이)

🌲 주요 트리의 종류와 사용 사례

  • 이진 트리 (Binary Tree)

> * '정의': 모든 노드의 자식 노드 수가 2개 이하인 트리입니다. > * '종류': 포화 이진 트리(Full), 완전 이진 트리(Complete) 등이 있으며, 완전 이진 트리는 힙(Heap)의 기반이 됩니다.

  • 이진 탐색 트리 (BST, Binary Search Tree)

> * '정의': 탐색에 효율적인 이진 트리로, '왼쪽 서브트리는 부모보다 작고, 오른쪽 서브트리는 부모보다 큰' 규칙을 가집니다. > * '시간 복잡도': 평균적으로 O(log n)의 탐색/삽입/삭제 시간을 가지지만, 트리가 한쪽으로 치우쳐진 편향 트리(Skewed Tree)가 되면 최악의 경우 O(n)이 됩니다.

  • 자가 균형 이진 탐색 트리 (Self-Balancing BST)

> * '정의': 데이터의 삽입/삭제 시 자동으로 트리의 균형을 맞추어, 최악의 경우에도 O(log n)의 시간 복잡도를 보장하는 트리입니다. > * '종류': AVL 트리, 레드-블랙 트리 (Red-Black Tree) 등이 있으며, Java의 `HashMap`, `TreeMap` 등에서 사용됩니다.

  • B-Tree / B+Tree

> * '정의': 하나의 노드에 여러 개의 데이터를 저장할 수 있는 균형 잡힌 트리입니다. > * '사용 사례': 대용량 데이터를 디스크에 저장하고 검색하는 데이터베이스나 파일 시스템의 인덱스(Index)로 주로 사용됩니다. 디스크 I/O 횟수를 줄이는 데 최적화되어 있습니다.

  • 힙 (Heap)

> * '정의': 완전 이진 트리에 기반한 자료구조로, 부모 노드의 키가 항상 자식 노드의 키보다 크거나 같은(Max Heap) 또는 작거나 같은(Min Heap) 특징을 가집니다. > * '사용 사례': 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다.

  • 트라이 (Trie)

> * '정의': 문자열 검색에 특화된 트리 자료구조입니다. > * '사용 사례': 검색어 자동 완성, 사전 검색 등에 사용됩니다.

💡 개발자 핵심 Point

  • 트리 순회 (Tree Traversal) : 트리의 모든 노드를 한 번씩 방문하는 방법으로, 면접에서 자주 질문되는 주제입니다.

> * 전위 순회 (Pre-order): Root → Left → Right (폴더 구조 탐색) > * 중위 순회 (In-order): Left → Root → Right (BST에서 사용 시 정렬된 순서로 노드 방문 가능) > * 후위 순회 (Post-order): Left → Right → Root (파일 삭제, 메모리 해제)

  • 어떤 종류의 트리를 선택할지는 데이터의 특성, 수행하려는 연산(탐색, 삽입, 삭제), 그리고 성능 요구사항에 따라 달라집니다.
원본 주소 "https://technote.wiki/index.php?title=트리의_종류와_특징&oldid=1089"