트리

트리

트리(Tree)는 정점과 간선 구성되며 계층으로 데이터를 표현하는 지료구조이다.

1. 일반 트리

png

일반 트리(Generic Tree)는 자식을 0개에서 n개까지 가질 수 있는 트리를 가리킨다. 일반 트리는 다음과 같이 구성된다.

• 트리를 구성하는 기본 단위인 노드

• 트리의 최상위 노드를 가리키는 Root

• 노드의 값을 가리키는 Key

• 노드와 노드를 연결하는 간선인 Edge

• 가장 마지막 노드를 가리키는 Leaf

2. 이진 트리

png

이진 트리(Binary Tree)는 자식을 0개에서 2개까지 가질 수 있는 트리를 가리킨다.

2.1. 이진 탐색 트리

png

이진 탐색 트리(Binary Search Tree)는 root를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 저장하는 트리를 가리킨다.

2.2. AVL 트리

png

AVL 트리(Adelson-Velsky and Landis Tree)는 이진 탐색 트리의 계층 차이가 1이하인 트리를 가리킨다. AVL 트리는 스스로 트리의 균형을 유지하므로 자가 균형 이진 탐색 트리라고도 부른다.

2.3. 레드 블랙 트리

png

레드 블랙 트리(Red-Black Tree)는 아래 조건을 만족하는 AVL 트리를 가리킨다.

1. 모든 노드는 빨강 혹은 검정

2. 루트 노드는 검정

3. 모든 리프 노드는 검정

4. 빨강 노드의 자식은 검정(= 빨강 노드 연속 출현 불가)

5. 모든 리프 노드에서 Black Depth는 동일(= 리프 노드 -> 루트 노드 경로의 검정 노드 개수 동일)

3. B 트리

3.1. B 트리

png

B 트리는 아래 조건을 만족하는 균형 트리를 가리킨다.

1. 모든 노드는 최대 M-1개의 키와 M개의 자식을 가질 수 있음

2. 루트 노드와 리프 노드를 제외한 모든 B-트리 노드는 최소 M/2개의 자식을 가져야 함

3. 루트 노드는 최소 2개의 노드를 가져야 함

4. 모든 리프 노드는 동일한 레벨에 있어야 함

B 트리는 높이를 작게 유지하면서 대량의 키를 저장할 수 있어 효율적인 검색 및 삽입 성능을 제공한다. 따라서 데이터베이스 및 파일 시스템과 같은 많은 응용 프로그램에서 사용한다.

3.2. B+ 트리

png

B+ 트리는 B 트리를 변형해 데이터를 리프 노드에 저장하고 키 값을 내부 노드에 저장하는 트리를 가리킨다.

참고 자료

• https://www.javatpoint.com/tree

• https://www.cs.usfca.edu/~galles/visualization/Algorithms.html