Tree - 트리와 이진트리란

 

1. 트리란?

 

트리는 계층적관계를 표현하는 자료구조이다.

출처: https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/

 

1.2 선형자료구조와의 차이점 (약간)

 

자료구조는 데이터를 표현하는 방법이다. 저장, 삭제, 조회 등의 기능이 제공되는 것이다.

- 선형자료구조는 데이터를 저장하는 것과 표현하는 것을 나누어 생각하기 힘들지만, 비선형은 데이터를 표현하는 관점에서 자료구조의 특징이 잘 들어난다.

 

출처: https://yjg-lab.tistory.com/118

- 예를들어 위와 같은 연결리스트로 동물의 종의 데이터와 사원의 이름 데이터를 저장한다고 한다면, 정해진 순서에 맞게 데이터를 일정한 방향으로 추가하여 저장할 것이다. 이를 위해 우리는 동물에 맞는 연결리스트 혹은 사원에 맞는 연결리스트를 따로 만들진 않았다.

 

- 이와 다르게 트리를 이용해 종속과목강문계에 따라 동물의 데이터를 나타내려는 것과 사원 데이터를 직급별로 나타내려는 것은 데이터만 다른 것이 아니라, 표현하고자 하는 목적에 따라 트리 자체의 구조도 다를 것이다.

즉 선형 자료구조와는 다르게 데이터를 어떻게 표현할 것인지에 따라 자료를 구성하는 방법 자체도 변화하는 것이다. 이러한 점이 선형자료구조와는 조오금 다른 점이라고 볼 수 있다.  

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=megapantera&logNo=220208214580

https://www.edrawsoft.com/kr/diagram-tutorial/how-to-make-an-organization-chart.html

 1.3 트리 관련 용어

 

https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/

 - 노드 node: 트리의 구성요소로 A,B,C.. 등등 전부

 

 - 간선 edge: 노드와 노드를 연결하는 연결선

 

- 루트노드 root node: 트리 구조에서 최상위에 존재하는 A와 같은 노드

 

- 단말 노드 terminal node: 아래로 또 다른 노느가 연결되어 있지 않은 노드 (leaf node)

 

- 내부 노드: internal node : 단말 노드를 제외한 모든 노드  (nonterminal node)

 

- 노드 간 부모, 자식, 형제 관계가 있다. (계층별 분리)

 

- 큰 트리에 속하는 작은 트리를 가리켜 서브 트리라고 한다. T1은 하나의 서브트리임 

 

*트리는 독립적 서브트리가 모여서 전체를 구성하는 건 아님! 각 서브트리는 트리에 종속적이다!

 

- 높이와 레벨 

출처:열혈자료구조

트리는 레벨 0부터 시작하며, 최고 레벨을 가리켜 높이라고 한다.

 

2. 이진트리(binary tree)

 

이진 트리란 (재귀적 정의) 

 > 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

 > 나뉘어진 두 서브 트리도 모두 이진 트리이어야한다.

 

*정의 자체가 재귀적이므로, 연산도 재귀적으로 이루어지는 경우가 많다

 

 

윤성우 열혈자료구조

노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다. 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다.

 

2.1 포화 이진 트리와 완전 이진 트리 

출처: 열혈자료구조

포화 이진 트리란 노드를 추가하려면 레벨을 늘려야 하는 이진트리 즉 모든 레벨이 꽉 찬 이진트리를 포화 이진 트리라고 한다.

 

완전 이진 트리란 포화 이진 트리 처럼 모든 레벨이 꽉 찬 상태는 아니지만, 노드가 빈 틈 없이 채워진 이진 트리를 뜻한다. 

노드가 위에서 아래로 왼쪽에서 오른쪽 순서로 채워졌음을 의미하는 것이다.

 

 

참고자료:  윤성우 열혈자료구조