PowerPoint 프레젠테이션

Transcription

1 트리 10 장. 트리 리스트나스택, 큐가데이터집합을한줄로늘어세운선형자료구조라면트리는두갈래로나누어세운비선형구조이다. 비선형구조를고안한동기는바로이구조가지닌효율성때문이다. 즉, 삽입, 삭제, 검색이라는주작업에대해서선형구조보다나은시간적효율을보일수있다. 학습목표 트리와관련된용어를정확히이해한다. 이진트리의세가지순회방법의차이점을이해한다. 포인터로구현한이진탐색트리의탐색, 삽입, 삭제코드를이해한다. 이진탐색트리의균형에따른효율의차이를이해한다. 1

2 트리 Section 01 트리개요 - 트리 계층구조를표현 : 디렉터리구조, 기업구조도, 족보, 결정트리 [ 그림 10-1] 디렉터리계층구조 [ 그림 10-2] 결정트리의예 2

3 트리관련용어 [ 그림 10-3] 일반트리 트리의구성요소에해당하는 A, B, C,..., F 를노드라함. B 의바로아래있는 E, F 를 B 의자식노드라함. B 는 E, F 의부모노드이고, A 는 B, C, D 의부모노드임. 같은부모아래자식사이에서로를자매노드라함. B, C, D 는서로자매노드이며, E, F 도서로자매노드임. 주어진노드의상위에있는노드들을조상노드라함. B, A 는 F 의조상노드임. 어떤노드의하위에있는노드를후손노드라함. B, E, F, C, D 는 A 의후손노드임. 부모가없는노드즉, 원조격인노드를루트노드라함. C, D, E, F 처럼자식이없는노드를리프노드라함. 리프노드를터미널노드라함. 리프노드를제외한모든노드를내부노드라함. 주어진트리의부분집합을이루는트리를서브트리라함. 이는임의의노드와그노드에달린모든후손노드를합한것임. 주어진트리에는여러개의서브트리가존재할수있음. 그림의 B, E, F 가하나의서브트리이며, 또 C 자체로서하나의서브트리임. 둘이상의자식노드를가질수있는트리를일반트리라함. 최대두개까지의자식노드를가질수있는트리를이진트리라함 3

4 계산식트리 [ 그림 10-4] 계산트리 계산식트리 컴파일작업에이용, 식 (a * (c - d)) + k를평가하기위한것연산자는내부노드에, 피연산자는리프노드에위치연산의우선순위가트리모습자체에내장됨 (c - d) 가먼저계산되어야 (a * (c - d)) 가계산된다 4

5 일반트리의이진트리변환 [ 그림 10-4] 계산트리 [ 그림 10-5] 일반트리 일반트리 이진트리로바꾸어표현가능일반트리의자식노드수는가변. 따라서확정적인자료구조로선언불가부모노드가무조건첫자식노드를가리키게자식노드로부터일렬로자매노드들을이으면이진트리 5

6 재귀적정의 첫째, 아무런노드가없거나, 이진트리정의 둘째, 가운데노드를중심으로좌우로나뉘되, 좌우서브트리모두이진트리다. [ 그림 10-6] 이진트리의정의 6

7 트리의레벨, 높이트리의레벨 루트노드를레벨 0으로하고아래로내려오면서증가트리의높이는최대레벨과일치루트만있는트리의높이는 0 비어있는트리의높이는 -1 [ 그림 10-7] 트리의레벨, 높이 7

8 재귀적정의 트리의높이 트리의높이 = 1 + Max( 왼쪽서브트리의높이, 오른쪽서브트리의높이 ) [ 그림 10-8] 트리의높이 8

9 포화이진트리포화이진트리 ( 飽和, Full Binary Tree) 높이 h인이진트리에서모든리프노드가레벨 h에있는트리리프노드위쪽의모든노드는반드시두개의자식노드를거느려야함. 시각적으로볼때포화될정도로다차들어간모습 [ 그림 10-9] 포화이진트리 (FULL) 9

10 완전이진트리완전이진트리 ( 完全, Complete Binary Tree) 레벨 (h-1) 까지는포화이진트리마지막레벨 h에서왼쪽에서오른쪽으로가면서리프노드가채워짐하나라도건너뛰고채워지면안됨포화이진트리이면완전이진트리. 그러나역은성립안됨 [ 그림 10-10] 완전이진트리 (COMPLETE) 10

11 균형 (Balance) 트리의균형 루트노드를기준으로왼쪽서브트리와오른쪽서브트리간의높이차이 균형트리 (Height Balanced Tree) 왼쪽, 오른쪽서브트리높이가차이가 1 이하 완전균형트리 (Completely Height-Balanced Tree) 왼쪽, 오른쪽서브트리높이가완전히일치하는트리를말한다. 11

12 Section 02 추상자료형트리 - 추상자료형트리작업 Create: 새로운트리를만들기 Destroy: 사용되던트리를파기하기 Insert: 트리에새로운노드를삽입하기 Delete: 트리의특정노드를삭제하기 Search: 주어진키를가진노드레코드를검색하기 IsEmpty: 빈트리인지를확인하기 CopyTree: 주어진트리를복사하기 Traverse: 트리내부노드를하나씩순회하기 12

13 Section 03 배열에의한이진트리구현 - 배열에의한이진트리 #define MAXNODE 100 최대노드수 typedef struct 배열요소는구조체 { char Name[ ]; 성명필드 int LChild; 왼쪽자식 int RChild; 오른쪽자식 node; typedef node treetype[maxnode]; treetype은구조체배열타입 [ 그림 10-11] 트리예시 Index Structure Name LChild RChild 0 Park Kim Seo Lee Cho UnUsed 6 UnUsed 7 UnUsed [ 표 10-1] 배열에의한트리구현 13

14 인덱스 배열에의한이진트리 Park 의 Lchild = 1 이라는것은 LChild 인 Kim 이인덱스 1 번에있음을의미인덱스 -1 은빈트리 (Empty Tree) 를의미 Lee 삭제데이터필드에서 Lee 를찾아서해당엔트리를 Unused 로표시나중에그공간을재사용할수있도록함. 빈공간을관리하기위해서는삭제된첫노드를가리키는인덱스를저장하고, 첫노드의 RChild 필드가두번째삭제된노드를가리키도록체인을형성 Lee 삭제부모노드인 Kim 의 Rchild 도 -1 로부모노드를찾기위해서는 Lee 의인덱스 3 을가지고배열전체를뒤져야함. 시간면에서너무비효율적임. 배열에의한이진트리는거의사용안함 ( 예외 : 완전이진트리 ) 14

15 완전이진트리와배열 완전이진트리와배열 노트필기순으로배열에저장인덱스 K 에있는노드의왼쪽자식은 (2K + 1) 에오른쪽자식은 (2K + 2) 에인덱스 K 에있는노드의부모노드는 (K - 1) / 2 에있다 규칙존재이유 완전이진트리의정의 [ 그림 10-12] 완전이진트리의배열인덱스 15

16 Section 04 포인터에의한이진트리구현 - 포인터에의한이진트리구현 typedef struct { char Name[ ]; 성명필드 node* LChild; 왼쪽자식을가리키는포인터 node* RChild; 오른쪽자식을가리키는포인터 node; 노드는구조체타입 typedef node* Nptr; 노드를가리키는포인터를 Nptr 타입으로명명 [ 그림 10-13] 노드구조 16

17 트리구성이유 삽입, 삭제, 검색이를위해서는순회 (Traversal) 가필요트리정의가재귀적. 따라서순회도재귀적 코드 10-1: 트리순회 Traverse(T) { if (T is Empty) { else { Traverse(Left Subtree of T); Traverse(Right Subtree of T); 왼쪽서브트리와오른쪽서브트리로나누어서재귀호출 베이스케이스 처음부터빈트리를의미하는널. 이진트리순회의기본 재귀호출에의해서브트리를따라내려가리프노드의왼쪽오른쪽서브트리인 LChild 와 RChild 포인터값이널. 17

18 코드 10-2: 전위순회 전위순회 void PreOrder(Nptr T) { if (T!= NULL) { Visit(T->Name); 전위, 아래재귀호출보다앞위치 PreOrder(T->LChild); 왼쪽재귀호출 PreOrder(T->RChild); 오른쪽재귀호출 [ 그림 10-14] 이진트리의순회 18

19 방문순서 : G, C, A, E, L 전위순회 호출함수가루트노드 G 를가리키는포인터 R 을넘김 R 이복사되어 T = T1 으로들어감데이터 G 를일단찍고, G 의 LChild 를넘기며재귀호출이번에는 G 의 LChild 가 T = T2 로들어감값호출에의해포인터복사본이넘겨짐이경우에는읽기만하는작업이므로사실상참조호출이필요없음 [ 그림 10-14] 이진트리의순회 19

20 방문의위치 중위순회, 후위순회 방문 ( 데이터처리 ) 명령의위치에따라서중위순회 ( 中位, In-order Traversal), 후위순회 ( 後位, Post-order Traversal) 로구분. 전위, 중위, 후위라는용어는재귀호출의상대적인위치 전위, 중위, 후위모두각노드를단한번씩만방문. 따라서효율은 O(N) 코드 10-3: 중위순회 void InOrder(Nptr T) { if (T!= NULL) { InOrder(T->LChild); Visit(T->Name); InOrder(T->RChild); 코드 10-4: 후위순회 void PostOrder(Nptr T) { if (T!= NULL) { PostOrder(T->LChild); PostOrder(T->RChild); Visit(T->Name); [ 표 10-2] 중위순회와후위순회 20

21 트리 중위순회결과 : A, C, E, G, L 후위순회결과 : A, E, C, L, G 전위, 중위, 후위표기 계산식트리전위표기 : 전위순회하면 + * a - c d k 중위표기 : 중위순회하면 a * c - d + k 프로그래머가사용후위표기 : 후위순회하면 a c d - * k + 컴파일러번역결과 [ 그림 10-14] 이진트리의순회 [ 그림 10-4] 계산트리 21

22 레벨순회코드 10-5: 레벨순회 void LevelOrder (Nptr T) { Q.Create( ); 새로운큐를만들고 Q.Add(T); 트리의루트포인터를큐에삽입 while (! Q.IsEmpty( )) 큐가비지않을때까지 { Nptr Current = Q.GetFront( ); 프런트포인터를꺼내 Visit(Current->Name); 가리키는노드를방문하고 if (Current->LChild!= NULL) 왼쪽자식이있으면 Q.Add(Current->LChild); 포인터를큐에삽입 if (Current->RChild!= NULL) 오른쪽자식도있으면 Q.Add(Current->RChild); 포인터를큐에삽입 22

23 Section 05 스택과스레드이진트리 - 스택에의한전위순회 코드 10-6: 스택에의한전위순회 IterativePreorder (Nptr p) 루트를가리키는포인터 p { S.create( ); 새로운스택을만들기 if (p!= NULL) 빈트리가아니면 { S.Push(p); 루트를스택에푸쉬 while (! S.IsEmpty( )) 스택이비지않을때까지 { p = S.Pop( ); 스택탑을꺼내서 Visit(p); 일단방문하고 if (p->rchild!= NULL) 오른쪽자식이있으면 S.Push(p->RChild); 스택에넣고 if (p->lchild!= NULL) 왼쪽자식도있으면 S.Push(p->LChild); 스택에넣는다. 스택사용시스템스택이건사용자스택이건스택공간과함께, 푸쉬팝을위한실행시간이요구됨스택의사용을완전히배제함으로써효율성을추구할수는없는가. 23

24 중위순회의예 스레드이진트리 노드마다추가로중위순회선행자, 중위순회후속자포인터추가이러한포인터를스레드 ( 실, Thread) 라함. 실제로는중위순회후속자만있으면되고, 또 Rchild 가널일경우만중위순회후속자가필요. 따라서 Rchild 필드를스레드로대용. 재귀호출이나사용자스택없이중위순회스택팝에의해이전노드로되돌아가는대신이전포인터를트리에내장스레드트리는전위순회나후위순회에도이용 [ 그림 10-15] 선행자 / 후속자스레드 [ 그림 10-16] 후속자스레드 24

25 코드 10-7: 스레드에의한중위순회 ThreadInorder (Nptr p) { if (p!= NULL) 스레드이진트리 { while (p->lchild!= NULL) p = p->lchild; 트리의가장왼쪽자식으로 while (p!= NULL) 더이상순회할곳이없을때까지 { Visit(p); 일단방문하고 Prev = p; 현재노드를 Prev에저장 p = p->rchild; 오른쪽자식노드또는중위후속자로이동 if (p!= NULL && Prev->IsThread = = FALSE) 오른쪽자식노드라면 while (p->lchild!= NULL) 다시가장왼쪽자식으로 p = p->lchild; 중위순회에서가장먼저방문해야할것은가장왼쪽자식두번째 while 루프 p 는현재 Q 를가리키고있으므로 p = p->rchild 에의해서중위후속자인 G 를가리킴. 그림의경우에는 Q 의 RChild 가스레드로사용. 따라서중위후속자인 G 를향해순회만약에이것이스레드가아니라면현재 p 가가리키는것이 G 가아니라 Q 의오른쪽자식노드임을의미. 이자식노드가널이아니라면다시그자식노드로부터가장왼쪽자식으로가서거기서부터방문을다시시작 25

26 Section 06 이진트리의복사 - 이진트리의복사 코드 10-8: 이진트리의복사 Nptr CopyTree(Nptr T) T 는원본의루트포인터 { if (T = = NULL) 원본포인터가가리키는노드가더이상없다면 return NULL; 복사할노드포인터도널로세팅 else 원본포인터에매달린노드가있다면 { Nptr T1 = (node *)malloc(sizeof(node)); 새로운노드를만들고 T1->Name = T->Name; 데이터를복사한다. T1->LChild = CopyTree(T->LChild); 서브트리의루트포인터를할당 T1->RChild = CopyTree(T->RChild); 서브트리의루트포인터를할당 return T1; 서브트리의루트포인터를리턴 전위순회를이용 26

27 Section 07 이진탐색트리 - 이진탐색트리 typedef struct { int Key; 학번 char Name[12]; 성명 char Address[200] 주소 datatype; typedef struct { datatype Data; 데이터는하나의구조체 node* LChild; 왼쪽자식을가리키는포인터 node* RChild; 오른쪽자식을가리키는포인터 node; 구조체타입노드 27

28 이진탐색트리 탐색에유리. 노드위치는키값을기준으로결정 모든노두 N 에대하여, N 의왼쪽서브트리에있는노드는모두 N 보다작고, N 의오른쪽서브트리에있는노드는모두 N 보다크다 N 의왼쪽서브트리와 N 의오른쪽서브트리도이진탐색트리다 약하게정렬되어있다 루트를중심으로왼쪽서브트리는작은것, 오른쪽서브트리는큰것쾌속정렬의파티션과유사. 루트노드는일종의피벗에해당피벗 (Pivot) 을중심으로작은것은모두왼쪽, 큰것은모두오른쪽서브트리만놓고볼때도다시파티션된상태이다 [ 그림 10-17] 이진탐색트리의예 28

29 이진탐색트리의탐색 코드 10-9: 이진탐색트리의탐색 Nptr Search(Nptr T, int Key) { if (T = = NULL) printf("no Such Node"); else if (T->Data.Key = = Key) return T; else if (T->Data.Key > Key) return Search(T->LChild, Key); else return Search(T->RChild, Key); 오류처리후빠져나옴찾아낸노드포인터를리턴 Call by Value로전달 Call by Value로전달 29

30 이진탐색트리의삽입 Nptr Insert(Nptr T, int Key) { if (T = = NULL) 리프노드의 Child 포인터 { T = (node*)malloc(sizeof(node)); 삽입할새노드를만들기 T->Data.Key = Key; 필요시나머지데이터필드복사 T->LChild = NULL; T->RChild = NULL; 리프노드이므로자식노드를널로 else if (T->Data.Key > Key) T->LChild = Insert(T->LChild, Key); 왼쪽서브트리로재귀호출 else T->RChild = Insert(T->RChild, Key); 오른쪽서브트리로재귀호출 return T; 현재서브트리의루트포인터 [ 그림 10-18] 이진탐색트리의삽입 30

31 이진탐색트리의삽입참조호출효과 재귀호출에서되돌아오면서트리자체의자식노드포인터값이바뀜베이스케이스에서 T3가호출함수에리턴호출함수에서는그값을 C의 LChild에할당같은방식으로 T2가 G의 LChild로할당된다. 같은방식으로 T1이 R에되돌려지면, 결국 R은 G를가리킴리프노드 C를제외한나머지포인터값은원래의값그대로를재할당 31

32 이진탐색트리의삭제첫째, 삭제할노드가리프노드인경우 자식이없어서간단함. 예를들어키 A인노드를삭제하려면부모노드인 B의 LChild를널로마찬가지로노드 K를삭제하려면노드 H의 RChild를널로놓으면된다 [ 그림 10-19] 이진탐색트리의삭제 32

33 이진탐색트리의삭제 둘째, 삭제할노드가하나의자식노드를거느린경우 왼쪽자식또는오른쪽자식. 역시간단함. 노드 F 를삭제하려면 F 의부모노드가 F 의자식노드를가리키면됨. 마찬가지로노드 L 을삭제하려면 G 의 RChild 가 H 를가리키면됨. 이렇게하더라도이진탐색트리의특성은유지 L, H, K 모두 G 보다크기때문에 G 의오른쪽서브트리에존재 L 이삭제되고 H 가 G 의오른쪽서브트리에붙어도이진탐색트리의크기관계는유지됨 [ 그림 10-19] 이진탐색트리의삭제 33

34 이진탐색트리의삭제 셋째, 삭제할노드가두개의자식노드를거느린경우 가장복잡한경우노드 B 를삭제. B 의부모인 F 의 LChild 가동시에 A 와 D 를가리키게 D 가 B 로복사. 원래의 D 를삭제이진탐색트리의키크기관계는유지 B 의자리를 B 보다큰 D 가차지하더라도, B 보다작았던 A 가불만할수없음 A < B < D 관계이므로 B 가없어지면당연히 A < D 이고따라서 A 는그대로 D 의왼쪽에있어야한다 [ 그림 10-20] 자식이둘인노드의삭제 34

35 이진탐색트리의삭제 G 를삭제하면 G 의자리로복사되어가야할것은? 이진탐색트리를중위순회 (In-order Traversal) 하면정렬된결과 A, B, D, F, G, H, K, L. 크기면에서 A < B < D < F < G < H < K < L G 가삭제된후대로정렬된순서를그대로유지하려면 G 의자리에는 G 의바로오른쪽 H 나, 아니면 G 의바로왼쪽 F 가들어가야함. G 바로다음에나오는 H 를 G 의중위후속자 (In-order Successor, 後續者 ) 라하고, G 바로직전에나오는 F 를 G 의중위선행자 (In-order Predecessor, 先行者 ) 라고함. [ 그림 10-21] 자식이둘인노드의삭제 ( 일반적 ) 35

36 이진탐색트리의삭제 void BSTclass::Delete(Nptr& T, int Key) { if (T = = NULL) 삭제할노드못찾고리프노드의널까지오면 printf("no Record with Such Key"); 오류처리 else if (T->Data.Key > Key) 삭제키가현재노드의키보다작으면 Delete(T->LChild, Key); 왼쪽서브트리로가서삭제 else if (T->Data.Key < Key) 삭제키가현태노드의키보다크면 Delete(T->RChild, Key); 오른쪽서브트리로가서삭제 else if (T->Data.Key = = Key) 현재 T가가리키는노드가삭제할노드 { if ((T->LChild = = NULL) && (T->RChild = = NULL)) 자식이없는경우 { Nptr Temp = T; T = NULL; Delete Temp; T에널값을할당 else if (T->LChild = = NULL) 오른쪽자식만있는경우 { Nptr Temp = T; T = T->RChild; Delete Temp; 부모를오른쪽자식에 else if (T->RChild = = NULL) 왼쪽자식만있는경우 { Nptr Temp = T; T = T->LChild; Delete Temp; 부모를왼쪽자식에연결 else 자식이둘인경우 SuccessorCopy(T->RChild, T->Data); 오른쪽자식노드포인터와 현재노드의레코드를넘김 36

37 이진탐색트리의삭제 void BSTclass::SuccessorCopy(Nptr& T, datatype& DelNodeData) { if (T->LChild = = NULL) 중위후속자이라면 { DelNodeData.Key = T->Key; 후속자레코드를넘어온레코드에복사 Nptr Temp = T; else T = T->RChild; delete Temp; 후속자의부모와자식을연결 SuccessorCopy(T->LChild, DelNodeData); 후속자찾아서왼쪽으로이동 후속자는자식이없거나자식이하나임 후속자의 Lchild 는항상널이기때문 만약널이아니면후속자가아님 37

38 키 Lee 인노드를찾기 이진탐색트리의효율 Park, Kim, Lee( 왼쪽트리 ) 대 Cho, Kim, Lee( 오른쪽트리 ) 키 Yoo 인노드찾기 Park, Seo, Yoo: ( 왼쪽트리 ) 대 Cho, Kim, Lee, Park, Seo, Yoo ( 오른쪽트리 ) 균형왼쪽트리는완전한균형. 오른쪽트리는왼쪽서브트리의높이가 -1( 빈트리 ), 오른쪽서브트리의높이가 4 로서균형이무너짐. 최악의경우탐색은리프노드까지왼쪽트리는최악의경우에도높이가 2. 오른쪽트리는최악의경우높이 5 를모두타고내려와야함. 오른쪽트리는연결리스트 (Linked List) 에가까움. 연결이한쪽으로일직선으로 (Linear Structure) 진행하는트리 = 편향이진트리 [ 그림 10-22] 이진탐색트리의균형 38

39 균형이잘잡혀있는경우 이진탐색트리의효율 높이는 lgn 에가까움. 높이만큼키비교를요함. 효율 O(lgN) [ 그림 10-23] 이진탐색트리의비교경로 균형이무너진경우최악의경우연결리스트에가까움효율 O(N) 39

40 자료구조별탐색효율비교 자료구조별탐색효율비교 최악의경우 평균적경우 탐색 삽입 삭제 탐색 삽입 삭제 정렬된배열 lgn N N lgn N/2 N/2 정렬안된연결리스트 N 1 1 N/2 1 1 이진탐색트리 N N N lgn lgn N 1/2 [ 표 10-3] 자료구조별효율비교 40

41 Thank you 41