Data Structure - Trees (1)

1. Tree란?

-   위계적인 구조를 나타낸 추상적인 모델

-   parent - child 관계로 이루어져 있음

 

적용 : 목차 구성, 파일 시스템, 개발 환경

---

용어 정리

Tree의 구조

Root : 부모가 없는 근본 노드 (A)

Internal node : 자식이 하나 이상 있는 노드 (A, B, C, F)

External node (a.k.a 잎) : 자식이 없는 노드 (E, I, J, K, G, H, D)

 

노드의 조상(ancestors) : 부모, 조부모, 증조부모 모두 포함한 부모노드들

노드의 후손(descendant) : 자식, 손, 증손 모두 포함한 자식노드들

 

노드의 깊이 (Depth) : 각 노드의 조상의 수

Tree의 높이(Height) : 노드들의 깊이 중 가장 깊은 것의 크기 (여기서는 3)

노드의 높이 : 노드의 깊이가 가장 위가 0 부터 하나씩 내려갈때마다 1씩 더해지는 거라면, 노드의 높이는 그 노드의 자식들 중 external한 것을 0부터 위로 올라갈때부터 1씩 더해져서 얻어지는 값 중 가장 큰 값. 자세한건 후술

 

Subtree : 노드와 그 자식들로 이루어진 tree안의 tree 구조

 

---

Tree ADT ( Abstract Data Type)의 메소드

포괄적 (Generic) 메소드 :

   - size() : 트리 안의 노드 갯수 return (int)

   - empty() : 비워져있으면 true 아니면 false return (boolean)

 

접근자 (Accessor) 메소드 :

   - root() : tree의 root의 position return (position), tree가 empty면  에러 

　- positions() : tree의 모든 노드들의 position list return (list <position>)

 

위치 기반 메소드 (Position - based methods) : 

   - p.parent() : 노드 p의 부모 return (position), p가 root일시 에러

   - p.children() : 노드 p의 자식들의 position list return (list <position>)

 

쿼리 (Query) 메소드 : 

   - p.isRoot() : p가 root면 true, 아니면 false return (boolean)

   - p.isExternal() : p가 external이면 true, 아니면 false return

 

일반적인 Tree의 연결된 구조

Tree는 요소, 부모 노드, 자식 노드들의 sequence 들로 표현 할 수 있다.

Node 객체는 Position ADT로 implement 된다.

 

2. Tree 관련 알고리즘

Tree 횡단 알고리즘 - Depth & Height

1. p의 depth는 p 자신을 제외한 p의 조상 수

 

2. 트리 T의 노드 p의 height 또한 recursive하게 정해진다.

   - p가 external 하다면 해당 p의 높이는 0이라고 잡고 부모 노드에 1씩 추가한다.'

 

     예를 들면,

그럼 Root의 높이는 2일까 4일까?

Root의 height는 그럼 2일까 4일까? Height는 자식노드들의 높이중 가장 높은 값에 1을 더하는 것이다. 따라서 Root node의 height = Height of Tree는 4이다.

 

Tree 횡단 알고리즘 - Preorder Traversal

Preorder로 Tree를 횡단하는 방법은 우리가 순차적으로 책을 적고 읽을 때 순서와 비슷하다.

우리가 책을 적을 때 생각해보면,

 

제목을 먼저 적고,

그 다음 부제목,

대단원 1,

소단원 1 - 1, 소단원 1 - 2

대단원 2,

소단원 2 - 1, 소단원 2 - 2

 

이런식으로 적지 않는가? 이것이 바로 Preorder Traversal이다.

그림과 알고리즘과 구조도으로 표현하면 아래와 같다.

 

 

Postorder Traversal

인는 어떠한 노드의 자식 노드가 있으면 자식 노드부터 먼저 읽는 것으로 아래와 같다. 디렉토리와 서브디렉토리에 있는 파일이 사용하는 공간을 계산할 때 이런 방향으로 진행된다.

 

소단원 1 - 1, 소단원 1 - 2

대단원 1

소단원 2 - 1, 소단원 2 - 2

대단원 2

부제목

제목

 

알고리즘과 구조도로 표현하면 아래와 같다.

 

Inorder Traversal

Inorder Traversal는 왼쪽 subtree를 먼저 읽고 그 후 오른쪽 subtree들을 읽는 형식이다.

binary Tree를 그릴 때 활용된다는데 아직까진 잘, 이해가 안된다.

 

알고리즘과 구조도로는 아래와 같이 표현된다.

 

예제) 아래와 같은 Tree를 Preorder, Postorder, Indorder의 순서대로 횡단해보자

답) 각 알고리즘의 설명에서 굵은 글씨로 적은 것이 곧 풀이이다. (Preorder과 Postorder의 경우)

     (Inorder의 경우 아래 답에 내가 알아낸 꿀팁 풀이 있음, 아래 더 보기 클릭)

Preorder : a b e j k n o p f  c d g l m h i 

Postorder : j n o p k e f b c l m g h i d a

 

Inorder : j e n k o p b f a c l g m d h i

문자에 동그라미 친 게 패키지