[Section2][자료구조/알고리즘] 자료구조 - Tree

트리(Tree)란?

자료구조 중 하나로, 데이터 구조가 마치 트리(나무) 형태 같다고 (정확히는 거꾸로된 나무 형태) 하여 지어진 이름이다.

자료구조 중에서도 그래프 형태의 자료구조로, 단방향 형태이며, 하나의 데이터를 기준(root)으로 삼아 나무의 가지처럼 뻗어나간 형태이다. 

 

그림1  -  출처 : https://yoongrammer.tistory.com/68

위 그림에서 알 수 있듯이,

데이터가 사람의 가계도처럼 계층을 이룬다.

하지만 각 데이터들의 방향성은 없다. 

예를 들면, 1 -> 2-> 3-> 이런 형태가 아니라는것이다. 그냥 단지 연결되어져 있다.

하지만 tree 기준의 나름 정렬방법이 있어서 정렬은 되어져 있다.

각 데이터들(1, 2, 3, 4 ...... 15) 은 노드(Node)라고 불리우며,

1번 데이터는 root 라고 불리운다. 현 트리구조 데이터들의 뿌리인것이다.

데이터가 들어올때 기준이 root에서부터 시작된다.

트리 데이터는 배열과 같이 데이터들이 순차적으로 위치하고 쌓이는 구조가 아니다.

그러므로 선형구조의 데이터가 아니라 비선형 구조이며, 데이터는 아래로만 쌓이기 때문에 사이클은 존재하지 않는다.

 

즉, 정리하자면 트리는 다음과 같은 특징을 가진다.

• 단방향 구조
• 계층형 구조
• 비선형 구조
• 무방향성

 

각 노드의 의미

그림 2   -  출처 : https://smujihoon.tistory.com/153

 

위 그림을 토대로 설명 하겠다.

 

• Root 노드 : 최초로 들어온 노드이며 트리구조의 기준이 된다.
• Parent 노드 : 자신의 하위에 노드(Child노드)를 가진 노드로써, 하위 노드와 자신노드로써 Sub-tree(트리안에 트리구조)라고 말할 수 있겠다
• Child 노드 : 자신의 상위 계층에 노드(Parent노드)가 존재하는 노드
• Sibling 노드 : 형제 노드로써, 같은 계층(레벨)의 노드를 의미한다.
• Leaf 노드 : 자신의 하위 계층 노드가(Child 노드) 존재하지 않는 나뭇잎처럼 쓸쓸한 노드를 말한다.
  자식이 없으니 쓸쓸한 노드..라고 기억하자.

 

트리구조에서 쓰이는 개념

• 깊이(depth)
  루트로부터 하위 계층의 특정 노드까지의 깊이(depth), root는 깊이가 0이다
• 레벨
  같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)
  그림 2 기준으로, B, C 노드가 같은 레벨 (1레벨)이다.
  
  
• 높이
  리프 노드에서 자신의 노드까지의 레벨수이다.
  각 리프 노드는 높이가 0이다. 

그림 3

부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가집니다.
위에 내용이 무엇이냐면, 그림3를 기준으로 말했을때,
일단 2, 5, 11, 4 노드는 자식 노드가 없기 때문에 모두 리프 노드이다. 그러므로 높이는 0이다.
그런데 이때!!!! 7노드를 보자! 
2 리프노드를 기준으로 봤을땐 높이가 1이고,
5, 11 노드를 기준으로 봤을땐 2이다.
이럴때 위에 말했듯이! 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가집니다.
라는 말과 같이, 6의 높이가 7의 자식 중에 가장 높다. 그러므로 2이다!

 

• 서브 트리
  트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에 존재하는 트리 구조를 갖춘 작은 트리를 서브 트리라고 한다. (D, H, I)로 이루어진 작은 트리도 서브 트리이고, (D, H, I)나 (C, F, G)도 서브 트리이다.

 

이진트리의 종류

이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다

 

 

 

 

 

 

 

참조 : https://yoongrammer.tistory.com/68