제5장 트리.

Presentation on theme: "제5장 트리."— Presentation transcript:

1 제5장 트리

2 5.6 히프 정의 최대트리(max tree)는 각 노드의 키값이(자식이 있다면) 그 자식의 키값보다 작지 않은 트리.
최대히프(max heap)는 최대 트리이면서 완전 이진 트리. 최소트리(min tree)는 각 노드의 키값이(자식이 있다면) 그 자식의 키값보다 크지 않은 트리. 최소히프(min heap)는 최소 트리이면서 완전 이진 트리.

3 structure MaxHeap Objects : 각 노드의 값이 그 자식들의 것보다 작지 않도록 조직된 n>0 원소의 완전 이진트리 Functions : 모든 heapMaxHeap, itemElement, n, max_sizeinteger MaxHeap Create(max_size) ::= 최대 max_size개의 원소를 가질 수 있는 공백 히프를 생성 Boolean HeapFull(heap, n) ::= if(n==max_size) return TRUE else return FALSE MaxHeap Insert(heap,item,n)::= if(!HeapFull(heap,n))item을 히 프에 삽입하고 그 히프를 반환 else return 에러 Boolean HeapEmpty(heap,n) ::= if(n>0) return TRUE Element Delete(heap,n) ::= if(!HeapEmpty(heap,n))히프에 서 가장 큰 원소를 제거, 그원소반환

4 5.6 히프 최대 히프에서 데이터의 삽입 20 15 2 5 14 10

5 5.6 히프 20 20 15 2 15 5 14 10 14 10 2

6 5.6 히프 최대 히프에서 데이터의 삽입 20 15 2 21 14 10

7 5.6 히프 20 20 15 2 15 21 14 10 14 10 2

8 5.6 히프 20 21 15 21 15 20 14 10 2 14 10 2

9 5.6 히프 #define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n==MAX_ELEMENTS-1) #define HEAP_EMPTY(n) (!n) typedef struct{ int key; } element; element heap[MAX_ELEMENTS]; int n = 0;

10 5.6 히프 void insert_max_heap(element item, int *n)
{ /*n개의 원소를 갖는 최대 히프에 item을 삽입*/ int i; if (HEAP_FULL(*n)){ fprintf(stderr,”The heap is full.\n”); exit(1); } i = ++(*n); while((i!=1)&&(item.key>heap[i/2].key)){ heap[i] = heap[i/2]; i/=2; heap[i]=item;

11 5.6 히프 5 20 15 2 14 10 n void insert_max_heap(element item, int *n)
{ /*n개의 원소를 갖는 최대 히프에 item을 삽입*/ int i; if (HEAP_FULL(*n)){ fprintf(stderr,”The heap is full.\n”); exit(1); } i = ++(*n); while((i!=1)&&(item.key>heap[i/2].key)){ heap[i] = heap[i/2]; i/=2; heap[i]=item; 5 20 15 2 14 10 n

12 20 5.6 히프 15 2 void insert_max_heap(element item, int *n) { /*n개의 원소를 갖는 최대 히프에 item을 삽입*/ int i; if (HEAP_FULL(*n)){ fprintf(stderr,”The heap is full.\n”); exit(1); } i = ++(*n); while((i!=1)&&(item.key>heap[i/2].key)){ heap[i] = heap[i/2]; i/=2; heap[i]=item; 14 5 n 10 20 15 2 14 10 n

13 5.6 히프(삭제) 20 15 2 14 10

14 5.6 히프(삭제) 20 10 15 2 15 2 14 10 14

15 5.6 히프(삭제) 10 15 15 10 15 2 2 14 2 14 14 10

16 element delete_max_heap(int *n)
{ /*가장 큰 값의 원소를 히프에서 삭제*/ int parent, child; element item, temp; if(HEAP_EMPTY(*n)){ fprintf(stderr,”The heap is empty\n”): exit(1); } /*가장 큰 키 값을 저장*/ item = heap[1]; /* 히프를 재구성하기 위해 마지막 원소를 이용*/ temp = heap[(*n)--]; parent = 1; child = 2; while(child <= *n){ /*현 parent의 가장 큰 자식을 탐색*/ if(child < *n)&&(heap[child].key)<heap[child+1].key child++; if(temp.key >= heap[child].key) break; /*아래 단계로 이동*/ heap[parent]=heap[child]; parent=child; child*=2; heap[parent]=temp; return item;

17 5.7 이진탐색트리 데이터의 검색(10) 20 15 2 14 10

18 5.7 이진탐색트리 히프 임의의 원소 삭제 => O(n) 임의의 원소 탐색 => O(n)
비효율적 => 이진탐색트리

19 5.7 이진탐색트리 이진탐색트리 : 공백이 가능한 이진 트리이다. 만약 공백이 아니라면 다음 성질을 만족한다.
모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다. 즉 키는 유일한 값을 가진다. 공백이 아닌 왼쪽 서브트리에 있는 키들은 그 서브트리의 루트의 키보다 작아야 한다. 공백이 아닌 오른쪽 서브트리에 있는 키들은 그 서브트리의 루트의 키보다 커야 한다. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

20 5.7 이진탐색트리 20 30 10 22 5 40 9 11 25 2

21 5.7 이진탐색트리(탐색-순환) tree_pointer search(tree_pointer root, int key)
{ /* 키값이 key인 노드에 대한 포인터를 반환함. 그런 노드가 없는 경우에는 NULL을 반환 */ if (!root) return NULL; if (key==root->data) return root; if (key<root->data) return search(root->left_child, key); return search(root->right_child, key); }

22 5.7 이진탐색트리(탐색-반복) tree_pointer search2(tree_pointer tree, int key) {
while(tree){ if (key==tree->data) return tree; if (key<tree->data) tree=tree->left_child; else tree=tree->right_child; } return NULL;

23 5.7 이진탐색트리 분석 높이가 h인 이진 탐색 트리에 대한 탐색에 걸리는 시간 => O(h) => O(log n)

24 5.7 이진탐색트리(노드삽입) 1. 트리 탐색 2. 탐색이 실패하면 탐색이 종료된 그 지점에 원소를 삽입
동일한 키값 존재여부 확인 2. 탐색이 실패하면 탐색이 종료된 그 지점에 원소를 삽입

25 5.7 이진탐색트리 30 5 40 2

26 5.7 이진탐색트리 80 삽입 30 30 node 5 40 5 40 2 2 80

27 5.7 이진탐색트리 35 삽입 30 node 5 40 2 80

28 void insert_node(tree_pointer *node, int num)
{ /*트리내의 노드가 num을 가리키고 있으면 아무일도 하지 않음; 그렇지 않은 경우는 data=num인 새 노드를 첨가*/ tree_pointer ptr, temp=modified_search(*node, num); if (temp || !(*node)){ /* num이 트리내에 없음 */ ptr=(tree_pointer)malloc(sizeof(node)); if(IS_FULL(ptr)){ fprintf(stderr,”The memory is full\n”); exit(1); } ptr->data=num; ptr->left_child=ptr->right_child=NULL; if(*node) if(num<temp->data) temp->left_child = ptr; else temp->right_child = ptr; else *node=ptr;

29 5.7 이진탐색트리(노드삭제) 35 삭제 30 5 40 2 35 80

30 5.7 이진탐색트리 40 삭제 30 30 5 40 5 80 2 80 2

31 5.7 이진탐색트리 노드삭제 삭제하고자 하는 노드를 왼쪽에서 가장 큰 값이나 오른쪽에서 가장 작은 값으로 대체

32 5.7 이진탐색트리 40 20 60 10 30 50 70 45 55 52

33 5.7 이진탐색트리 이진 탐색 트리의 높이 최악의 경우에도 높이가 O(logn)인탐색트리=>균형탐색트리
최악 => O(n) ex, 1,2,3,…n 순서로 입력 평균 => O(logn) 최악의 경우에도 높이가 O(logn)인탐색트리=>균형탐색트리 AVL트리 2-3트리 레드-블랙트리

34 과제물 이진 탐색 트리에서 노드의 삭제를 위한 프로그램 작성

35 제6장 그래프

36 6.1 그래프 추상데이타타입 오일러 행로(Eulerian walk) : 각 다리를 한번씩만 건너서 시작점으로 돌아오는 경로

37 6.1 그래프 추상데이타타입

38 6.1 그래프 추상데이타타입 그래프 G=(V,E) V(G) : 공집합이 아닌 정점(vertex)들의 유한집합
E(G) : 간선(edge)의 집합(정점의 쌍) (무방향)그래프 : undirected graph (v0,v1)=(v1,v0) : 무순서 방향(directed) 그래프 : digraph <v0,v1>!=<v1,v0> : 순서 tail head

39 6.1 그래프 추상데이타타입 G1 G2 G3

40 6.1 그래프 추상데이타타입 G1 G2 G3 G1, G2 : 무방향 그래프 G3 : 방향 그래프 G2 : 트리

41 6.1 그래프 추상데이타타입 G1 G2 G3 V(G1)={0,1,2,3} V(G2)={0,1,2,3,4,5,6}
E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)} E(G3)={<0,1>,<1,0>,<1,2>}

42 6.1 그래프 추상데이타타입 그래프의 제한 V(G), E(G)=집합 Self loof 는 허용 안됨
간선의 중복은 안됨 : 다중그래프(multigraph)

43 6.1 그래프 추상데이타타입 n-정점 무방향 그래프 n-정점 방향 그래프 간선의 최대수 = n(n-1)/2
=> 완전(complete) 그래프 n-정점 방향 그래프 간선의 최대수 = n(n-1)

44 6.1 그래프 추상데이타타입 G의 부분그래프 G’ V(G’)V(G)  E(G’)E(G)

45 6.1 그래프 추상데이타타입 경로 : 정점(간선)들의 연속 경로의 길이 : 경로상의 간선수
단순경로(simple path) : 서로다른 정점으로 구성된 경로(처음과 끝 정점은 같아도 됨) 사이클(cycle) : 처음과 끝정점이 같은 단순경로 Directed path, directed cycle

46 6.1 그래프 추상데이타타입 연결(connected) 그래프, G 연결요소(connected component)
All vi, vj V(G) => vi에서 vj로의 경로존재 연결요소(connected component) 최대 연결 부분그래프(maximal connected subgraph) 트리 : 사이클없이 연결된 그래프

47 6.1 그래프 추상데이타타입 강력연결그래프(strongly connected graph) G
모든 쌍의 정점들 사이에 상호 방향 경로 존재 All vi, vj V(G) => 방향경로 vi,…,vj, vj,…,vi 존재

48 6.1 그래프 추상데이타타입 강력연결요소(strongly connected component) 강하게 연결된 최대 부분그래프

49 6.1 그래프 추상데이타타입 정점의 차수 : 정점에 부속한 간선의 수 방향그래프
v의 진입차수(in-degree):v가 간선의 머리 v의 진출차수(out-degree):v가 간선의 꼬리 e=(sum(di),{i=0,n-1})/2 , di=정점 i의 차수

50 6.1 그래프 추상데이타타입 그래프 표현 인접행렬(adjacency matrix) n*n 배열 adj_mat
adj_mat[i][j]=1:(vi,vj)or(vj,vi)  E(G) adj_mat[I][j]=0:otherwise 무방향:대칭, 방향:비대칭 공간 n2 무방향 그래프:n(n-1)/2로 감소(상위삼각행렬)

51 6.1 그래프 추상데이타타입 vi의 차수(무방향) :sum(adj_mat[i][j]){j=1,n} 방향그래프
행 i의 합=방향그래프에서 vi의 진출차수 열 j의 합=방향그래프에서 vj의 진입차수

52 6.1 그래프 추상데이타타입 1 2 3 1 1 1 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 1 2

53 6.1 그래프 추상데이타타입 (2) 인접리스트(adjacent list) n개의 연결리스트(헤드노드) vi:
무방향그래프(e:간선의수):2e개의 리스트노드 방향그래프 : e개의 리스트 노드 vj link

54 6.1 그래프 추상데이타타입 headnode vertex link 1 2 3 1 2 3 2 3 1 3 1 2 1 2 1 2

55 6.1 그래프 추상데이타타입 인접리스트를 위한 C 선언문 #define MAX_VERTICES 50 //정점의 최대수
typedef struct node* node_pointer; typedef struct node{ int vertex; struct node *link; }; node_pointer graph[MAX_VERTICES]; int n=0; // 현재 사용중인 정점들

56 6.1 그래프 추상데이타타입 (3) 인접 다중리스트(adjacency multilists)
다중리스트 : 노드가 여러 리스트에 의해 공유 노드구조 : 간선, (v1, v2) marked v1 v2 path1 path2

57 6.1 그래프 추상데이타타입 headnode N1 edge(0,1) 1 2 3 1 N2 N4 N2 edge(0,2) 2 N3
1 2 3 1 N2 N4 N2 edge(0,2) 2 N3 N4 N3 edge(0,3) 3 NULL N5 N4 edge(1,2) 1 2 N5 N6 N5 edge(1,3) 1 3 NULL N6 N6 edge(2,3) 2 3 NULL NULL The lists are : vertex 0:N1->N2->N3 vertex 1:N1->N4->N5 vertex 2:N2->N4->N6 vertex 3:N3->N5->N6

58 6.1 그래프 추상데이타타입 가중치 간선 네트워크 : 가중치 간선을 가진 그래프 그래프의 간선에 가중치(weights)를 부여
가중치는 한 정점에서 다른 정점까지의 거리나 한 정점에서 인접한 정점으로 가는 비용등을 표현 노드구조에 weights 필드 추가 네트워크 : 가중치 간선을 가진 그래프