PowerPoint 프레젠테이션

Transcription

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

2 트리 트리 계층구조를표현 : 디렉터리구조, 기업구조도, 족보, 결정트리 2

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

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

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

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

8 트리의높이 재귀적정의 트리의높이 = 1 + Max( 왼쪽서브트리의높이, 오른쪽서브트리의높이 ) 8

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

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

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

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

13 배열에의한이진트리 #define MAXNODE 100 최대노드수 typedef struct 배열요소는구조체 { char Name[ ]; 성명필드 int LChild; 왼쪽자식 int RChild; 오른쪽자식 node; typedef node treetype[maxnode]; treetype은구조체배열타입 Index Structure Name LChild RChild 0 Park Kim Seo Lee Cho UnUsed 6 UnUsed 7 UnUsed 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 에있다. 규칙존재이유 완전이진트리의정의 15

16 포인터에의한이진트리구현 typedef struct { char Name[ ]; 성명필드 node* LChild; node* RChild; 왼쪽자식을가리키는포인터 오른쪽자식을가리키는포인터 node; 노드는구조체타입 typedef node* Nptr; 노드를가리키는포인터를 Nptr 타입으로명명 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); 오른쪽재귀호출 18

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

20 중위순회, 후위순회 방문의위치 방문 ( 데이터처리 ) 명령의위치에따라서중위순회 ( 中位, Inorder 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); 20

21 트리 전위, 중위, 후위표기 중위순회결과 : A, C, E, G, L 후위순회결과 : A, E, C, L, G 계산식트리 전위표기 : 전위순회하면 + * a - c d k 중위표기 : 중위순회하면 a * c - d + k 프로그래머가사용후위표기 : 후위순회하면 a c d - * k + 컴파일러번역결과 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 스택에의한전위순회 코드 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 필드를스레드로대용. 재귀호출이나사용자스택없이중위순회 스택팝에의해이전노드로되돌아가는대신이전포인터를트리에내장 스레드트리는전위순회나후위순회에도이용 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 이진트리의복사 코드 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 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) 을중심으로작은것은모두왼쪽, 큰것은모두오른쪽 서브트리만놓고볼때도다시파티션된상태이다 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) else 오류처리후빠져나옴 찾아낸노드포인터를리턴 return Search(T->LChild, Key); Call by Value 로전달 return Search(T->RChild, Key); 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; 현재서브트리의루트포인터 30

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

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

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

34 이진탐색트리의삭제 셋째, 삭제할노드가두개의자식노드를거느린경우가장복잡한경우노드 B 를삭제. B 의부모인 F 의 LChild 가동시에 A 와 D 를가리키게? D 가 B 로복사. 원래의 D 를삭제. 이진탐색트리의키크기관계는유지 B 의자리를 B 보다큰 D 가차지하더라도, B 보다작았던 A 가불만할수없음. A < B < D 관계이므로 B 가없어지면당연히 A < D 이고따라서 A 는그대로 D 의왼쪽에있어야한다. 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, 先行者 ) 라고함. 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; T = T->RChild; 후속자의부모와자식을연결 delete Temp; else 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) 진행하는트리 = 편향이진트리 38

39 균형이잘잡혀있는경우 이진탐색트리의효율 높이는 lgn에가까움. 높이만큼키비교를요함. 효율 O(lgN) 균형이무너진경우 최악의경우연결리스트에가까움 효율 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 40