Microsoft PowerPoint - 제8장-트리.pptx

Transcription

1 제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1

2 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 검색을중간부터시작하여좌우중하나로분기, 1/2 씩검색대상을줄여나감으로써이진검색의효과를얻는다 ptr

3 1. 트리의개념 트리의정의트리는 1개이상의노드를갖는집합으로노드들은다음조건을만족한다. 1) 트리에는루트 (root) 라고부르는특별한노드가있다. 2) 다른노드들은원소가중복되지않는 n개의부속트리 (subtree) T1, T2,, Tn으로나누어지며 Ti 각각은루트의부속트리라고부른다. ( 트리는사이클이없는그래프 (acyclic graph) 이며계층구조를이룬다.) 트리 T 3 T 2 T 1 root 3

4 자료구조트리 (tree) 는나무를거꾸로그린다. 부속트리 T 1, T 2, T 3 는다시트리구조를이룬다. root root T 1 T 3 T 1 T 3 T 2 T 2 D E F H I J K L G M 4

5 루트 (root) 노드 레벨 (level) 1 D 2 E F G H I J 3 K L M 4 맆 (leaf) 노드 5

6 트리자료구조는왜필요할까요? - 트리구조에저장하면더효율적인자료들이있기때문이다. 예를들면, 계층적인데이터형태들은트리에저장하면자연스럽게표현된다. 1) 회사나정부의조직구조, 2) 나라, 지방, 시 군별, 계층적인데이터의저장, 3) 인덱스 ( 인덱스는계층적자료구조로검색을쉽게해준다.) 레벨 (Level) 한국 1 서울 경기 강원 2 강북 강남 수원 강릉 속초 원주 3 종로 신촌 중앙동 4 6

7 트리에관한용어 - 노드의차수 (degree) : 노드의부속트리의개수 - 트리의차수 (degree of tree) : 트리의최대차수 - 맆 (leaf, 단말, terminal) 노드 : 차수가 0인노드, 즉맨끝에달린노드들이다. - 내부 (internal, non-terminal) 노드 : 차수가 1 이상인노드 - 부모 (parent) : 부속트리 (subtree) 를가진노드 - 자식 (child) : 부모에속하는부속노드 - 형제 (sibling) : 부모가같은자식노드들 - 조상 (ancestor) : 노드의부모노드들의총집합 - 자손 (descendant) : 노드의부속트리에있는모든노드들 - 레벨 (level) : 루트노드들로부터깊이 ( 루트노드의레벨 = 1) - 트리의깊이 (depth of tree) : 트리에속한노드의최대레벨 7

8 * 트리의예전체노드개수 = 13 개단말 ( 맆 ) 노드개수 = 7 개내부노드개수 = 6 개 트리의차수 = 3 트리의깊이 = 4 루트노드 레벨 (level) 1 K 의조상들 D 2 E F G H I J 3 K L M 의자손들 맆노드들 ( 총 7 개 ) H 의형제노드 4 8

9 트리구조를컴퓨터내부에저장하는방법 1) n- 링크표현법 - 노드에 n 개의링크를두고자식의개수만큼링크에저장한다. 모든노드는자식노드수에관계없이최대 n 개의링크를갖는다. 각링크는부속트리가저장된곳을링크한다. * 차수가 n 인경우표현된노드 data link 1 link 2 link n 참고 : 트리를리스트형태로표현하는방법 괄호를사용하여같은레벨에있는노드들을같은괄호로묶는다. 예 ) (((E(K,L),F),(G),D(H(M),I,J))) 2) 왼쪽자식노드-오른쪽형제노드표현방법 모든노드에링크를 2개를둔다. 첫째링크는첫번째자식노드를표현하고둘째링크는자신의오른쪽형제노드를표현한다. - 노드의길이가 2개로고정되기때문에 n-링크방법보다간편하다. 9

10 * 왼쪽자식노드 - 오른쪽형제노드표현법 data left child right sibling * 왼쪽자식노드 - 오른쪽형제노드방법으로저장된트리 노드의모습 G D D D E F G H I J K L M E F G H I J K L M 10

11 차수가 n인트리를차수가 2인트리로저장하는방법 트리를왼쪽자식노드-오른쪽형제노드로변환하여그린다음 45도시계방향으로돌리면된다.( 약간수정은필요 ) 모든노드가 2개이하의자식노드를갖는다. 차수가 n인트리가차수가 2인트리가된다.( 이진트리 ) D D E F G H I J E F G H I J K L M K L M 일반트리 -> 왼쪽자식 - 오른쪽형제표현 -> 이진트리모양으로회전 11

12 E K F G D L H M I 왼쪽자식노드 - 오른쪽형제노드표현방법 > 이진트리모양 J 12

13 Q/ 1. 다음차수가 3 인트리를왼쪽자식 - 오른쪽형제노드표현방법으로바꾸어보아라. 13

14 2. 이진 (inary) 트리 자식노드의수가 2 개이하인것을이진트리 (binary tree) 라고한다. 대부분응용에서일반트리보다는원래부터이진트리로표현된문제가많다. 정의 ) 이진트리 (a binary tree) 는유한개의노드로구성된트리로 1) 비어있거나혹은 2) 루트노드와 2 개의부속트리로구성된다. 2 개의부속트리는왼쪽부속트리, 오른쪽부속트리라고부른다. * 주의 : 노드가없는경우도이진트리의일종이다. 이진트리의예 : 왼쪽두트리는서로다른이진트리이다. 14

15 이진트리의성질 이진트리는자식의개수가 2개이하인일반트리와약간다르다. 노드가없는트리도 (empty node) 도이진트리가된다. 부속트리 ( 자식노드 ) 에순서가있다. 이진트리의최대레벨이 i 인경우트리의최대노드의개수는 2 i -1 이다. 레벨 1의최대노드개수 = 1 레벨 2의최대노드개수 = 2 레벨 i의최대노드개수 = 2 i-1 레벨 i인트리의최대노드는 = i-1 = 2 i -1 이진트리의맆노드의개수 n 0 와차수가 1인노드의개수 n 1, 차수가 2인노드의개수 n 2 에관한다음의등식이성립한다. n 0 = n ( 증명 ) 전체노드개수를 n이라고하면 1 n= n 2 + n 1 + n 0 ( 노드개수는세가지경우를합한것이다 ) 2 n= 2 * n * n * n ( 전체노드수는자식노드를곱한식에다, 루트노드 1을더한다.) 두식을계산하면 n과 n 1 이소거되어증명성립 15

16 트리와이진 (inary) 트리의예 트리 왼쪽자식 - 오른쪽형제표현 이진트리 트리 왼쪽자식 - 오른쪽형제표현 이진트리 D D E F G E F G E F G 트리왼쪽자식 - 오른쪽형제트리이진트리 16

17 다양한이진트리 스큐 (skewed) 이진트리 ( 정의 ) 트리의노드가왼쪽이나오른쪽으로한쪽으로만노드가있는트리이다. 포화 (full) 이진트리 (full binary tree of depth k) ( 정의 ) 트리의깊이가 k( 레벨을 1로시작 ), 2 k - 1 노드를가진이진트리 ( 트리깊이가 1이면노드가 1개, 2이면 3개, 3이면 7개, 4이면 15개, 로트리에노드가꽉차있는이진트리이다.) 완전 (complete) 이진트리 (complete binary tree) ( 정의 ) n개의노드를가진 complete( 완전 ) 이진트리는포화이진트리에서노드에 1부터 n까지번호를붙였을때만들어진트리이다. 17

18 1 2 3 이진 (inary) 트리의예 포화 (full) 이진트리 ( 깊이 =4) D E F G D Skewed 이진트리 H I 완전 (complete) 이진트리 E 18

19 Q/ * 다음트리에대하여답을구해보자 (1) 깊이가 5인이진트리의노드의최소개수는? (2) 깊이가 5인이진트리의노드의최대개수는? (3) 깊이가 5인포화이진트리의노드의최소개수는? (4) 깊이가 5인포화이진트리의노드의최대개수는? (5) 깊이가 5인완전이진트리의노드의최소개수는? (6) 깊이가 5인완전이진트리의노드의최대개수는? (7) 이진트리에서자식이 2인노드의개수가 4개일때맆노드의개수는? 19

20 3. 이진 (inary) 트리의저장 이진트리의저장 3-1 배열을이용한저장트리의레벨순서대로배열에저장을해두는방법이다. 트리의노드를레벨순서대로왼쪽에서오른쪽으로저장한다. 배열이름을 T[] 라고하면루트노드는 T[0] 에, 레벨 2 의첫째노드는 T[1] 에, 둘째노드는 T[2] 에,, 저장하는방식이다. 배열에저장할경우임의의배열원소의부모와왼쪽, 오른쪽자식을찾는함수는다음과같이된다.( 첨자가 0 부터시작할경우 ) 1) 부모노드의위치 parent(i) = (i 1) / 2 if i 0 parent(i) = 0 if i = 0 : ( 루트노드는부모가없다.) 2) 왼쪽자식의위치 - left_child(i) = 2 i + 1 3) 오른쪽자식의위치 - right_child(i) = 2 i + 2 * 첨자가 1 부터시작하면? 20

21 배열에저장된이진 (inary) 트리예 1 예를들어 T[6] 의부모는 T[(6-1)/2] 이고 T[3] 노드의왼쪽자식은 T[3*2 +1] 이다. T[1] 의오른쪽자식노드의위치를찾아보아라.( 소수점이하는버린다.) H D E F G I [0] [1] [2] [3] [4] [5] [6] [7] [8] D E F G H I 배열 T[ ] 21

22 배열에저장된이진 (inary) 트리예 2 E D [0] [1] [2] [3] [4] [5] [6] [7] [8] [15] D - E skew 이진트리 배열에서데이터가비어있는곳이많다. 22

23 배열을이용한이진트리저장의문제점 (1) 배열의이용하지않는저장공간이많다. 깊이가 k 인트리에서전체필요한공간은 S(k) = 2 k 1 이지만 skewed 이진트리처럼깊이에비하여노드수가적은경우기억공간활용율이낮다. - complete( 완전 ) 이진트리의저장에는효과적이다 (2) 트리의최대깊이를대비하여많은기억장소를확보하고, 트리가예상보다커지면프로그램수행을종료해야한다. 23

24 3-2 연결리스트를이용한트리의표현 (1) 데이터 (2) 왼쪽자식에대한포인터 (3) 오른쪽자식에대한포인터 struct tnode { int data; struct tnode * left_child; struct tnode * right_child; }; typedef struct tnode node; typedef node * tree_ptr; left_child data right_child left_child data right_child 24

25 연결리스트로표현한트리예 1 D E F G H I D null E null null F null null G null null H null null I null 25

26 연결리스트로표현한트리예 2 null null root null D D null E null E null skewed 이진트리경우 26

27 참고 이진트리를연결리스트로표현하는다른방법 필드를한개더추가하여부모노드에대한포인터를저장한다. 그러나트리를다룰때링크 3 개를관리해야하므로복잡하여잘사용하지않는다. parent left_child data right_child parent data left_child right_child 27

28 이진트리저장방법의비교 (1) 배열 - 저장이편하다. 배열선언 int T[MX]; - 노드의위치를쉽게알수있다. 첨자가 0부터시작한다고가정 m 레벨의 k번째노드의인덱스위치는? -> (2 m-1 1) + (k -1) 노드는 T[(2 m-1 1) + (k -1)] 에위치 (2) 연결리스트 - 트리의크기와깊이에관계없이노드수만큼의데이터를저장한다. - 트리의크기가증가하여도기억장소에서노드를확보하여트리를구성 - 트리전체를탐색하는알고리즘이배열보다는복잡하다. 28

29 일반트리도이진트리로변형하여저장하는것이더효율적이다. ( 일반트리에서자식노드의개수가변하기때문에저장방법이쉽지않다.) D D E F G E F G E F 트리 왼쪽자식 - 오른쪽형제트리이진트리 G 29

30 Q/ 다음트리에대하여답을구해보자 (1) 트리의깊이는? (2) 노드번호 6의형제노드는? (3) 노드번호 6의조상노드들은? (4) 노드번호 6의오른쪽자식노드는? (5) 트리를배열 X[ ] 에저장하였을때 ( 첨자 0부터시작 ) X[6] 에저장되는데이터는무엇인가? (6) 연결리스트로저장한다면전체노드의수는? (7) 연결리스트로저장할경우, 링크필드의전체개수는? (8) 연결리스트로저장할경우, 전체링크필드중링크에값이있는필드의수는?(NULL이아닌필드 ) (9) 연결리스트로저장할경우, 링크의값이 NULL인필드의수는? 30

31 Review 트리는중요한자료구조중의하나이다. 이장에서는트리의기본개념, 부모노드, 자식노드, 형제노드, 이진트리, complete 이진트리, full 이진트리, skewed 이진트리등용어에대하여살펴보았다. 이진트리를컴퓨터에저장하는방법은배열을사용하는방법과연결리스트를사용하는방법이있다. 배열은간단한반면, 기억공간효율성, 확장성에문제가있다. 연결리스트방식은트리의노드에자식노드를가리키는포인터를사용하여자식노드와연결을시킨다. 대부분의응용에서는연결리스트를사용한다. 31