[자료구조론]트리(Tree)

소개글

트리(Tree)의 정의, 종류 및 용어 등에 관해 자세히 설명하였습니다.
레포트 제출이나 시험을 대비하여 공부하실 때 편리하게 쓰일 수 있을 것입니다.

목차

◆ 트리의 정의

◆ 용어설명

◆ 트리의 목적

◆ 트리의 종류
1. 순서 트리(ordered tree)와 비순서 트리(oriented tree)
2. 닮은 트리(similar tree)와 대등한 트리(equivalent tree)
3. 이진 트리(binary tree)
4. 이진 탐색 트리 (Binary Search Tree)

◆ B트리
1. B트리
2. B+ 트리
3. B*트리
4. B 트리에서의 삽입과 삭제연산 알고리즘
5. B트리와 B+트리 삽입 알고리즘의 차이점
6. B트리와 B+트리 삭제 알고리즘의 차이점

본문내용

◈ 트리(tree)
◆ 트리의 정의
- 대상 정보를 계층적으로 구조화시키고자 할 때 사용하는 자료구조가 "트리" 이다.
(자료 사이의 계층적 관계를 구조화)

위의 혈통도는 "가계"라는 대상 정보를 단순히 데이터 요소를 나열하여 표현하지 않고, 데이터 요소들 간의 "parent-child" 관계를 계층적으로 표현하고 있다. 혈통도는 "I"를 뿌리로 하여 가지가 갈라져 나온 거꾸로 된 나무 모양을 하고 있기 때문에 "트리(tree)" 구조를 가졌다고 한다. 트리에서 단위 데이터 요소들은 하나의 노드로 표현된다.

트리는 다음과 같이 재귀적으로 정의할 수 있다.

-트리에는 하나의 루트(root) 노드가 있다.
-루트를 제외한 나머지 노드들은 서로 중복되지 않는 여러 개의 노드 집합으로 나뉘어 진다. 이 때 각각의 노드 집합들은 역시 트리가 된다. (나머지 노드들은 각각이 트리이면서 교차하지 않는 분리 집합 으로 분할된다.
이 때, 을 루트의 서브트리(subtree)라 한다.)

혈통도를 예로 들어 설명하면 "I" 노드는 전체 트리의 루트 노드가 되고, 루트를 제외한 나머지 노드들은 {father, grand father, grand mother} 집합과 {mother, grand father, grand mother} 의 두 집합으로 나뉘어 진다. 이 때 두 개의 집합은 각각 "father" 노드와 "mother" 노드를 루트로 하는 트리가 된다.

참고 자료

C언어로 설명한 자료구조