#. 트리(tree)
##1. 트리(tree)란?
트리는 컴퓨터 과학에서 중요한 자료구조 중 하나로, 노드들이 edge로 연결된 계층적 구조를 가진다.
트리의 최상위 노드를 루트 노드라고 하며, 나머지 노드들은 부모-자식 관계를 가지며 서로 연결된다.
##2. 트리(tree)의 특징
- 계층적인 구조: 트리는 자료들 사이의 계층관계를 나타내는 데 적합하다.
- 루트 노드: 트리의 최상위에 위치한 노드로, 트리는 루트 노드에서 시작한다.
- 부모-자식 관계: 트리의 노드들은 부모-자식 관계를 가지며, 각 노드는 하나의 부모 노드와 여러 개의 자식 노드를 가질 수 있다. 이러한 노드들은 edge로 연결된다.
##3. 트리(tree)의 구조
###3.1 용어
-
root : 트리 최상위 노드
-
edge : 노드와 노드를 연결하는 선
-
parent : 자식 노드를 보유한 노드
-
child : 부모 노드의 하위 노드
-
sibling : 같은 부모 노드를 가진 동일 선상의 노드
-
leaf : 트리 최하단 노드
-
size : 모든 노드들의 개수 (root 포함)
-
depth : 선택한 노드에서 root까지의 거리
-
height : 선택한 노드에서 leaf 노드까지 가장 긴 경로에 있는 edge의 개수
###3.2 종류
- 편향 트리
- 모든 노드들이 하나의 자식 노드만 가지는 트리
- 이진 트리 (binary tree)
- 부모 노드 밑의 자식 노드 개수를 최대 2개로 제한하는 형태
- 노드의 값, 데이터 크기 등과 상관없이 구성된다.
- 이진 탐색 트리 (binary search tree)
- 부모 노드를 기준으로 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가진다.
###3.3 순회
- 중위 순회 (in-order traversal)
left → visit → right
- 전위 순회 (pre-order traversal)
visit → left → right
- 후위 순회 (post-order traversal)
left → right → visit
##4. 트리(tree)의 장점과 단점
###4.1 장점
데이터를 계층적이고 직관적으로 표현할 수 있어, 데이터 검색과 정렬, 삽입, 삭제 등의 연산이 효율적이다.
###4.2 단점
트리의 구조가 복잡하여 설계와 구현이 어렵고, 데이터의 추가나 삭제에 따라 트리의 구조를 재조정해야 할 수도 있다.
##5. 트리(tree)의 사용
트리는 데이터를 계층적이고 직관적으로 표현할 수 있어, 데이터의 관계를 이해하기 쉽고, 데이터 검색과 정렬, 삽입, 삭제 등의 연산이 효율적이다.
##5.1 웹 페이지 렌더링
웹 페이지는 HTML 태그의 계층적 구조를 가지는 DOM (Document Object Model) 트리를 사용하여 렌더링된다.
##5.2 프로그래밍 언어의 구문 분석
프로그래밍 언어의 컴파일러는 소스 코드를 분석하고 실행하기 위해 구문 트리(Syntax tree)를 사용한다.
##5.3 데이터베이스
데이터베이스 관리 시스템(DBMS)에서는 B-트리, B+ 트리 등의 트리 구조를 사용하여 데이터를 효율적으로 관리한다.
