Tree 구조 (트리 구조) 자료구조 / 트리 순회 방법 세가지 전위, 중위, 후위 순회 알고리즘 문제

 

 

 

Tree(트리) 구조란?

자료구조 Tree는 이름 그대로 나무를 거꾸로 뒤집은 형태를 가지고 있습니다.

 

 

 

트리구조는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조입니다.

데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래 여러개의 데이터가 존재할 수 있는 비선형 구조로 되어있습니다. 또한 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어가기에 사이클이 따로 존재하지 않습니다.

 

 

 

 

 

 

트리(Tree) 구조의 기본적 개념 

1. 트리는 노드로 이루어진 구조입니다. (각각의 데이터를 노드라함.)

2. 루트 노드는 0개 이상의 자식 노드를 가지고 있습니다 (현재 이미지에서는 A가 루트.)

3. 그 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 이는 반복적으로 정의됩니다. (아래로만 뻗어져 나감.)

4. A는 B와 C의 부모노드(Parent Node)이고, B와 C는 A의 자식노드(Child Node)입니다. 자식이 없는 G,H,I,J,K 와같은 노드를 리프 노드(Leaf 노드)라 합니다

5. 노드(node)들과 노드들은 연결하는 간선 으로 구성되어 있습니다.

6. 노드들은 특정 순서로 나열될 수도 있고, 그럴 수 없을 수도 있다.

7. 각 노드는 부모 노드로의 연결이 있을수도 있고, 없을 수도 있다.

8. 각 노드는 어떠한 자료형으로도 표현이 가능하다.

 

 

 

 

Class Node {
 public String name;
 public Node[] Parent;
}

 

 

 

 

Tree 관련 용어

노드(Node): 트리 구조를 이루는 모든 개별 데이터

부모 노드(Parent node): 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에 가깝게 있는 노드

자식 노드(Child node): 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드 즉 

형제(Sibling): 같은 부모를 가지는 노드

노드의 크기(Size): 자신을 포함한 모든 자손 노드의 개수
노드의 깊이(Depth): 루트에서 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(Level): 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(Degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(Degree of tree): 트리의 최대 차수
트리의 높이(Height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이내부(internal) 노드: 단말 노드가 아닌 노드
간선(Edge): 노드를 연결하는 선 (link, branch 라고도 부름)

리프(Leaf): 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

   → 단말 노드(Leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.

루트(Root): 트리 구조의 시작점이 되는 노드

 →루트 노드(Root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.

 

와 같이 필수 개념을 정리 할 수 있다.

 

 

 

 

Tree의 특징

* 그래프의 한 종류이다. '최소 연결 트리' 라고 부른다.

* 트리는 계층 모델이다.

* 트리는 사이클이 없다. 즉 방향성이 있는 비순환 그래프의 한 종류이다.

                                            loop, circuit, self-loop가 없다.

* 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 

  (총 간선은 정점 개수 -1)

* 루트에서 어떤 노드로 가는 경로는 유일하다.

* 한개의 루트 노드만이 존재하고 모든 자식 노드는 한개의 부모 노드만을 가진다.

  A부모에서 -> C, D 자식 노드가 있는데 F에서 C를 다시 참조할 수 없다라는 것임.

* 트리의 종류로는 정 이진트리, 포화 이진 트리, 완전 이진 트리, 이진 힙, 균현 트리 등이 있다.

 

 

 

 

 

 

Binary Search Tree의 종류 (이진 탐색 트리)

정 이진 트리, 포화 이진 트리, 완전 이진 트리 등이 있다.

 

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고,

모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다는 특징이 있다.

 

 

 

정 이진 트리(Full binary tree) :

각 노드가 0개 또는 2개의 자식 노드를 갖는다.

 

 

 

 

 

포화 이진 트리(Perfect binary tree) :

정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고,

모든 레벨이 가득 채워져 있는 트리이다.

 

 

 

 

 

완전 이진 트리(Complete binary tree) :

마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고,

마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 있어야 한다.

 

 

 

 

이진 트리의 순회 과정

순회 과정은

전위 순회, 중위 순회, 후위 순회, 층별 순회로 나누어 볼 수 있다.

G -> D -> H -> B -> I -> E -> A -> C -> J -> F -> K

 

 

 

전위 순회(Preorder travers) :  [루트 - 왼쪽 자식 - 오른쪽 자식]

뿌리를 먼저 방문하게 된다.

A -> B -> D -> G -> H -> E -> I -> C -> F -> J -> K

 

 

이와같이 좌측에 최하위 자식노드부터 읽어가기 시작하는 루틴으로 반복된다.

 

 

 

중위 순회(Indorder travers) : [왼쪽 자식 - 루트 - 오른쪽 자식]

왼쪽 하위 트리를 방문한 후 뿌리(Root)를 방문한다.

G -> D -> H -> B -> I -> E -> A -> C -> J -> F -> K

 

 

 

 

후위 순회(Postorder travers) : [왼쪽 자식 - 오른쪽 자식 - 루트]

하위 트리를 모두 방문한 후 뿌리 (Root)를 방문

G -> H -> D -> I -> E -> B -> J -> K -> F -> C- > A

 

 

 

층별 순회(Level oreder travers) : [노드 순서대로 읽어옴]

위 쭉 node들 부터 아래방향으로 차례로 방문

 

A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K

 

 

 

Tree의 장점? 사용하는 이유?

* (Dynamic) Array나 Linked List에서는 삽입이나 삭제를 수행하는데 O(N) 시간이 소요된다.

   Array : Index로 빠르게 접근 가능하지만, Shift과정에서 O(N) 소요

   Dynamic Array: Index로 빠르게 접근이 가능하지만, 작업 외 데이터들을 임시 배열로 복사/ 이동 하는 과정에서 O(N)소요

   Linked List : 작업 데이터를 찾기 위해 순회하는 과정에서 O(N) 소요

 

 

* 트리는 편향 트리가 아닌 이상 일반적으로 삽입/삭제 수행하게 된다면 O(logN)시간이 소요됨.

* 계층적 관계를 표현하기에 용이하다.

 

 

 

트리와 비슷하게 느껴지는 그래프란?↓

https://mininkorea.tistory.com/32

Grahp란? 자료구조 그래프 개념 및 특징.