(CS) 트리 & 트라이

트리

트리는 계층적 구조를 가지며, 각 노드들이 서로 연결되어 있는 자료구조이다. 트리는 하나의 루트(root) 노드에서 시작하여 다양한 자식 노드들로 확장된다. 각 노드는 부모와 자식 노드 간의 관계를 가진다. 트리는 순환 구조를 갖지 않으며, 각 노드는 정확히 하나의 부모를 가진다.

트리를 이루는 구조를 하나씩 알아보자.

 

Node(정점, Vertex)

• 트리의 기본 단위로, 정보를 저장하는 단일한 항목
• 노드는 데이터 필드(Key)와 하나 이상의 포인터를 가짐

Key

• 노드를 구분하거나 정렬하는데 사용하는 값
• 노드의 데이터 필드에 저장되는 값

Edge(간선)

• 노드 간의 연결 관계를 나타내는 선으로, 트리의 구조를 형성
• 두 노드 간의 간선은 부모-자식 관계를 나타냄

Root

• 트리의 최상위 노드로, 모든 다른 노드는 루트로부터 접근 가능
• 트리는 하나의 루트 노드만을 가짐

Parent(부모)

• 어떤 노드에서 그 노드의 바로 위에 있는 노드를 가리킴

Child(자식)

• 어떤 노드에서 그 노드의 바로 아래에 있는 노드를 가리킴

Sibling(형제)

• 트리에서 특정 노드와 같은 부모를 가지는 다른 노드를 가리킴

Leaf

• 자식이 없는 노드로, 트리의 가장 끝에 위치한 노드

Subtree

• 트리 내에서 특정 노드와 해당 노드의 자손들로 이루어진 트리를 가리킴
• 서브트리는 트리 내의 일부분을 나타냄

Level(레벨)

• 트리의 각 깊이를 나타냄
• 트리의 루트에서부터 어떤 노드까지 이동하는데 필요한 단계의 수
• 루트 노드의 레벨은 0이며, 그 아래의 레벨은 1, 2, 3, ... 순으로 증가

Height(높이)

• 트리의 최대 깊이
• 루트 노드에서 가장 깊숙이 위치한 리프 노드까지의 거리

트리의 종류

1. 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가지는 트리
   

   

2. 이진 탐색 트리(Binary Search Tree): 이진 트리이면서, 각 노드의 왼쪽 자식은 현재 노드보다 작은 값을 가지고, 오른쪽 자식은 현재 노드보다 큰 값을 가지는 트리
   

   

3. AVL(Adelson-Velsky and Landis) 트리: 이진 탐색 트리이면서, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 트리
   

   

4. B-트리: 균형 트리로서, 각 노드가 여러 개의 키와 서브트리를 가지는 트리 => 주로 데이터베이스 시스템에서 사용
   

   

5. B+트리:  B-트리의 변형으로, 실제 데이터는 리프 노드만 가지는 것이 B-트리와의 차이점
   => 리프 노드들이 연결 리스트로 이루어져 있어 범위 탐색이나 순차적 접근 매우 용이하기에 주로 데이터베이스의 인덱스 구조로 사용됨 
   

   

트라이

트라이는 검색 트리의 일종으로, 키 값을 저장하고 검색하는 자료구조이다.

각 노드의 키는 문자이며, 경로를 따라가면서 키 값을 찾는 특징이 있다.

트라이는 문자열 검색에 효과적이며, 특히 사전 검색이나 자동 완성과 같은 응용 분야에서 사용된다.

특징

노드 구성: 각 노드는 문자를 나타내며, 루트에서부터 경로를 따라 내려갈수록 문자열의 한 부분을 나타낸다.
키의 검색: 루트에서 시작하여 문자열의 각 문자를 차례로 따라가면서 키 값을 검색한다.
공통 접두사 활용: 트라이는 키들 간의 공통 접두사를 효과적으로 활용하여 메모리를 절약할 수 있다.
시간 복잡도: 키 길이에 따라 O(m)의 시간 복잡도를 갖는다. (m은 키의 길이)

참고 링크

Introduction to Tree - Data Structure and Algorithm Tutorials - GeeksforGeeks

Trie | (Insert and Search) - GeeksforGeeks