[자료구조] Tree의 종류

출처 : https://www.techyloud.com/why-do-students-need-help-with-a-data-structure-assignment/

 

[자료구조 알고리즘] Tree의 종류

본 포스팅은 위의 영상을 정리한 글로 개인 공부를 목적으로 작성되었습니다.

---

들어가기 전에

자료구조가 어떻게 분류되는지 먼저 생각하기!

갑분 노트 필기

 

Tree란

그동안 우리가 배운 Array, Linked List, Stack, Queue 는 라인처럼 생긴 일직선 데이터 구조(linear)이다. 하지만 트리는 부모, 자식 구조를 가진 구조로 계층이 있고 그룹이 있다. 어떻게 이게 가능한가? 노드가 하나 이상의 차일드를 갖기 때문이다.

 

트리의 노드 중에는 부모를 아는 경우도 있고 자식만 아는 경우도 있고 어떤 특정한 순서에 의해서 데이터가 관리되는 경우도 있고 데이터가 섞여있는 경우도 있다. 참고로 트리의 맨 끝에 더이상 자식이 없는 노드를 leaf라고 부른다.

 

종류

1. 이진트리(Binary Tree)

노드가 하나 이상의 자식을 가지면 트리라고 한다. 그 중에 차일드 노드가 최대 두 개까지만 붙는 트리가 이진트리, 바이너리 트리이다.

 

2. 이진 검색 트리(Binary Search Tree)

이진트리 안에 데이터가 왼쪽 노드와 그 이하 차일드 노드들은 현재 노드보다 작아야 하고 오른쪽 노드와 그 이하 차일드 노드들은 현재 노드보다 커야 한다. 그래서 만약 어떤 노드를 보고 해당 노드의 값보다 큰 값을 찾고 싶으면 오른쪽에 가서 찾으면 되고

작은 값을 찾고 싶으면 무조건 왼쪽으로만 가서 찾으면 된다.

 

모든 값들이 노드들을 기준으로 딱딱 나뉘어져 있어서 어떤 값을 찾을 때 두 갈래 길을 선택해서 가다 보면 그 값을 찾다.

 

3. 삼항 트리(Ternary tree)

노드에 차일드가 세 개씩 있는 트리를 말한다.

 

4. 완전 이진트리(Complete Binary Tree)

완전 이진트리는 모든 노드들이 레벨 별로 왼쪽부터 채워져 있는 것이다. 트리를 만들다보면 레벨이 생기게 되는데 마지막 레벨을 제외한 모든 서브 트리의 레벨이 같아야 하고 마지막 레벨은 왼쪽부터 채워져 있으면 된다.

 

5. Full Binary Tree

노드들이 차일드를 가지려면 두 개를 모두 가지고 있어야 하고 그게 아니라면 아예 없어야 한다.

 

6. 포화 이진트리(Perfect Binary Tree)

양쪽으로 빈 공간 없이 모든 노드가 두 개의 자식을 가지고 레벨도 정확하게 딱 떨어지는 상태이다. 완벽하게 피라미드 구조를 생성하고 있을 때를 말한다. 레벨의 갯수가 n개일 때 노드의 갯수가 2ⁿ-1이 된다.

 

번외

Balance

노드들이 너무 지나치게 치우쳐져 있지 않으면 밸런스가 맞다고 표현한다. 밸런스가 맞는 대표적인 트리에는 red-black tree와 AVL tree가 있다.