자료구조 - Tree (2)

 

 

 

자료구조 중 Tree는 여러 형태, 여러 종류를 가지고 있다.

 

각각의 Tree 별로 고유한 특징이 있으며 그 특징에 따라 데이터를 관리하거나
특정 알고리즘을 수행할 때 최적의 역할로 기능한다.

 

 

 

Tree의 종류

 

 

 

 

 

이진 트리 (Binary Tree)

 

• 모든 노드들이 둘 이하 (0,1,2)의 자식 노드를 가지는 트리

 

• 같은 수의 자식 노드를 가지고 있어도 자식 노드의 위치가 왼쪽이냐 오른쪽이냐에 따라 각각 다른 이진 트리로 구분함.

 

• 이진 트리 중에서도 많은 종류의 이진트리가 있음.

 

 

이진 탐색 트리 (Binary Search Tree)

 

• 왼쪽 자식 노드는 부모보다 작고 오른쪽 자식 노드는 부모보다 큰 이진트리

 

• 탐색 과정이 트리의 높이만큼 탐색하기 때문에 O(logN) 의 시간복잡도를 가짐.

 

• 편향트리가 되어버린다면 배열과 비슷해지기 때문에 이 경우의 시간복잡도는 O(N)임.

 

 

 

 

정 이진 트리 (Full Binary Tree)

 

 

• 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리

 

 

 

 

완전 이진 트리 (Complete Binary Tree)

 

• 마지막 레벨을 제외한 모든 레벨이 채워져야 하는 트리

 

• 노드는 반드시 왼쪽부터 오른쪽으로 채워야 함.

 

포화 이진 트리 (Perfect Binary Tree)

 

• 정 이진 트리 (Full Binary Tree) + 완전 이진 트리 (Complete Binary Tree) 의 특징을 지님.

 

• 모든 리프 노드의 레벨이 동일하고 가득 차 있어야 하는 트리임.

 

 

편향 이진 트리(Skewed Binary Tree)

 

 

• 같은 높이의 이진 노드중 최소 갯수의 자식 노드만 가져야 하는 트리임.

 

• 왼쪽 혹은 오른쪽으로의 서브트리로 구성되어야 함. (단방향)

 

• 성능을 따져보면 배열이나 Linked List와 동일한 시간 복잡도를 가짐 [O(N)]

 

 

 

균형 이진 트리 (Balanced Binary Tree)

 

 

• 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 일정 기준 이상으로 나지 않는 트리. (최대 1의 높이 차이)

 

• 트리의 높이를 어느 정도 강제성을 가지고 관리하기 때문에 연산시 비교적 빠르게 처리되는 편임.

 

 

---

 

 

레드 - 블랙 트리 (Red-Black Tree)

 

 

 

• 모든 노드는 Red 혹은 Black의 색깔 노드로 선언됨.

 

• 루트 노드는 반드시 Black 노드여야 하며 모든 리프 노드 역시 Black이어야 함. (Null in Black)

 

• Red 노드는 반드시 자식 노드로 Black 노드를 가짐.

 

• 데이터 삽입, 삭제에 있어서 AVL 트리보다 유리함.

 

 

높이 균형 이진 탐색 트리 (Adelson-Velsky and Landis, AVL 트리)

 

 

• 균형 이진 트리의 한 종류이며 조금 더 엄격한 균형 조건을 가짐.

 

• 스스로 균형을 관리하는 트리인데 Balance Factor라는 기준을 가지고 관리함.

 

• Balance Factor , 즉 BF는 왼쪽 자식 노드와 오른쪽 자식 노드의 높이 차이를 뜻함. 

 

• BF는 최대 차이가 1로 유지되어야 함.

 

• 이진 탐색 트리는 시간 복잡도가 최악의 경우 O(N) 이지만 AVL 트리의 경우
  평균 뿐 아니라 최악의 경우에도 O(logN) 임 (삽입, 삭제, 탐색 모두)

 

• 데이터 탐색에 있어 RB 트리보다 유리함.

 

 

 

 

 

 

 

 

 

 

---

 

사진 출처 : https://www.geeksforgeeks.org/

GeeksforGeeks | A computer science portal for geeks