자료구조 tree의 종류

 

🌲tree

 

1. 계층형, 그룹형 자료구조

2. 그래프의 일종으로 순환이 없는 자료구조

3. 부모노드에서 자식노드로, 자식노드에서 다시 자식노드로 재귀적 성격을 가짐

4. 많은 시스템에서 차용되는 자료구조

 

 

 

 

binary tree

자식 노드가 최대 2개인 트리

 

 

 

 

 

 

binary search tree

1. 같은 레벨, 다른 레벨의 노드들이 대소 관계를 가지는 트리

2. 왼쪽 자식 노드는 자신보다 작으며 오른쪽 노드는 자신보다 크다는 특징이 존재합니다.

3. 삽입, 삭제 연산마다 노드들의 위치를 재조정해줍니다.

4. 탐색 시간복잡도 O(logN), 한 단계씩 내려갈 때마다 반대 방향의 노드가 탐색범위에서 제외

 

 

 

 

 

balance tree

1. 좌우가 크게 편향되지 않은 트리입니다.

2. 편향될수록 탐색에 매우 비효율적

3. 예로는 AVL, red-black tree등이 존재

 

 

 

 

 

complete binary tree

1. 마지막 레벨을 제외한 모든 노드가 꽉 채워짐

2. 마지막 레벨의 노드들은 좌측부터 채워짐 

 

 

 

 

 

 

full binary tree

1. 모든 노드들이 자식을 아예 안가지거나 꽉 채움

 

perfect binary tree

1. 피라미드 형태를 가집니다.

2. 노드의 수가 2n - 1(n = level)

3. 모든 노드들이 자식을 꽉 채워가짐