Microsoft PowerPoint - lec07_tree [호환 모드]

Size: px
Start display at page:

Download "Microsoft PowerPoint - lec07_tree [호환 모드]"

Transcription

1 Tree 2008학년도 2학기 kr -1-

2 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 -2-

3 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조. ~ 정렬된배열 탐색은빠르지만 O(logN), 삽입 / 삭제는느림 (O(N)). ~ 연결리스트 ~ 트리 삽입 / 삭제는빠르지만 (O(1)), 탐색은느림 (O(N)). 삽입과삭제, 탐색이모두빠름 (O(logN)). -3-

4 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드, 아래있는노드를자식노드. 키(key) ~ 자료항목을찾거나또는다른동작을하기위해필요한값 ~ 각자료항목을구분해주는역할, 자료항목을대표하는값 -4-

5 하위트리 (subtree) ~ 하나의큰트리에속해있는부분트리. 방문 (visiting) ~ 노드에도착해노드의자료값을읽는행위. 순회 (traversing) ~ 트리의노드전체를방문하는행위. 레벨 (level) ~ 어떤노드의레벨은루트노드로부터얼마나많이떨어졌는지를의미 ~ 여기에서는루트를레벨 1 로가정. 높이 (height) ~ 높이는최장루트- 잎경로의길이이다. -5-

6 노드 (node) ~ 트리의구성요소 루트 (root) ~ 부모가없는노드 (A) A 서브트리 (subtree) ~ 하나의노드와그노드들의자손들로이루어진트리 단말노드 (leaf node) ~ 자식이없는노드 (A,B,C,D) B C D 비단말노드 ~ 적어도하나의자식을가지는노드 (E,F,G,H,I,J) 레벨 (level) ~ 트리의각층의번호 E F G H I J 높이 (height) ~ 트리의최대레벨 (3) 차수 (degree) ~ 노드가가지고있는자식노드의개수 -6-

7 -7-

8 트리의일반적인성질 한노드에서다르노드로가는경로가유일 ~ 임의의두노드에대해최소공통선조 (least common ancestor) 를갖음. 두노드가가질수있는가장가까운선조 ~ 경로가중복되지않는다면두노드간의경로는반드시한노드에서최소공통선조까지올라갔다다른노드로내려오는유일한경로만이존재. N 개의노드를갖는트리는 N-1 개의링크. ~ 그래프와달리루트를제외하고는모든노드가자신의선조를향한하나의링크를가지고있음. ~ N 개의노드를가진트리는 N-1 개의링크를갖음. -8-

9 이진트리 (binary tree) 2. 이진트리 ~ 트리구조중자식을최대둘까지가질수있는트리 ~ 모든노드의차수가 2 이하 구현하기가편리함 ~ 모든노드가 2 개의서브트리를가지고있는트리 ~ 서브트리는공집합일수있음. ~ 이진트리에는서브트리간의순서가존재 ~ 각노드들은자식이없거나, 하나또는두개의자식노드를유지 ~ 가장보편적인트리구조, 이진탐색트리 (binary search tree) -9-

10 특징 생김새 ~ 왼쪽자식 (left child), 오른쪽자식 (right child). ~ 왼쪽자식의키 (key) 는부모노드의키보다작고, 오른쪽자식의키는부모노드의키보다크다. -10-

11 노드의개수가 n 개이면간선의개수는 n-1-11-

12 높이가 h 인이진트리 ~ 최소 h 개의노드 ~ 최대 2 h -1 개의노드 -12-

13 n 개의노드를가지는이진트리의높이 ~ 최대 n, 최소 log 2 (n+1) -13-

14 완전이진트리 (complete binary tree) ~ 마지막레벨을제외한각레벨의노드들이모두차있고, 마지막레벨에서는노드들이순서대로존재하는상태 꽉찬이진트리 (full binary tree) ~ 모든레벨이꽉찬이진 v 트리 -14-

15 -15-

16 배열표현법 3. 이진트리구현 ~ 모든이진트리를포화이진트리라고가정 ~ 각노드에번호부여, 그번호를배열의인덱스 -16-

17 배열구현법에서인덱스결정 ~ 노드 i 의부모노드인덱스 : i/2 ~ 노드 i 의왼쪽자식노드인덱스 : 2i ~ 노드 i 의오른쪽자식노드인덱스 : 2i+1-17-

18 링크표현법 ~ 포인터를이용하여부모노드가자식노드를가리키게하는방법 -18-

19 노드구조, in C ~ 노드 구조체로구현 각노드가포인터 (= 링크 ) 를가지고있어노드와노드를연결 typedef struct TreeNode { } int data; struct TreeNode struct TreeNode *left; *right; ~ 교재 p.256, 프로그램 7.1 참고. -19-

20 순회 (traversal) 4. 트리순회 (traverse) ~ 트리의노드들을체계적으로방문하는것 순회방법 ~ 전위순회 (preorder traversal), VLR ~ 자손노드보다루트노드를먼저방문. ~ 중위순회 (inorder traversal), LVR ~ 왼쪽자손, 루트, 오른쪽자손노드순서로방문. ~ 후위순회 (postorder traversal), LRV ~ 루트노드보다자손노드를먼저방문. -20-

21 전위순회 전위순회 (Preorder Traverse) ~ 루트를먼저방문하는순회방법 1. 루트노드. 2. 왼쪽하위트리. 3. 오른쪽하위트리. // 전위순회 preorder( TreeNode *root ){ if ( root ){ } } printf("%d", root->data t ); // 노드방문 preorder( root->left ); // 왼쪽서브트리순회 preorder( root->right ); // 오른쪽서브트리순회 -21-

22 -22-

23 중위순회 중위순회 (Inorder Traverse) ~ 왼쪽서브트리 -> 루트 -> 오른쪽서브트리순서로방문 1. 왼쪽하위트리. 2. 노드를방문. 3. 오른쪽하위트리. // 중위순회 inorder( TreeNode *root ){ if ( root ){ } } inorder( root->left );// 왼쪽서브트리순회 printf("%d", root->data ); // 노드방문 inorder( root->right );// 오른쪽서브트리순회 -23-

24 * / a b c d -24-

25 -25-

26 후위순회 후위순회 (Postorder Traverse) ~ 왼쪽서브트리 -> 오른쪽서브트리 -> 루트노드순으로방문 1. 왼쪽하위트리방문. 2. 오른쪽하위트리방문. 3. 노드방문. // 후위순회 postorder( TreeNode *root ){ if ( root ){ } } postorder( root->left );// 왼쪽서브트리순회 postorder( root->right );// 오른쪽서브트리순회 printf("%d", root->data ); // 노드방문 -26-

27 -27-

28 선택방법 전위, 중위, 후위순회구현 교재 p.265, 프로그램 7.3 참고. 레벨순회, 그림 7-31, 프로그램 7.4 참고. -28-

29 수식트리 수식트리 (evalaution tree) ~ 산술식을트리형태로표현한것 비단말노드 : 연산자 (operator) 단말노드 : 피연산자 (operand) -29-

30 수식 a + b a - (b c) (a < b) or (c < d) 전위순회 +ab - a bc or < a b < c d 중위순회 a + b a - b c a < b or c < d 후위순회 a b + a b c - a b < c d < or -30-

31 노드개수 5. 이진트리연산 ~ 탐색트리안의노드의개수를계산 ~ 각서브트리에대하여순환호출한다음, 반환되는값에 1 을더하여반환 int get_node_count(treenode *node) { int count=0; if( node!= NULL ) count = 1 + get_node_count(node count(node->left)+ get_node_count(node->right); return count; } -31-

32 트리높이구하기 ~ 서브트리에대하여순환호출 ~ 서브트리들의반환값중에서최대값을구하여반환 int get_height(treenode *node) { } int height=0; if( node!= NULL ) height = 1 + max(get_height(node->left), get_height(node->right)); return height; -32-

33 정의및특징 6. 스레드이진트리 ~ 이진트리의 NULL 링크를이용하여순환호출없이도트리의노드들을순회 ~ NULL 링크에중위순회시에후속노드인중위후속자를저장시켜놓은트리 ~ 단말노드와비단말노드의구별을위히여 is_thread 필드필요 -33-

34 이진트리 (binary tree) ~ 모든원소의키는유일 7. 이진트리탐색 ~ 왼쪽서브트리의키값들은루트의키값보다작다. ~ 오른쪽서브트리의키값들은루트의키값보다크다. ~ 왼쪽과오른쪽서브트리도이진트리의특성유지. -34-

35 탐색 (search) ~ 어떤주어진키를가지고그키와동일한값을갖는노드를찾는것. ~ 루트노드부터방문하여노드의키값과주어진키값을비교하여내려가는식으로진행. Public Node find(int key) { Node current = root; while (current.keydata!= key) { if (current == null) return null; if (key < current.keydata) current = current.leftchild; else current = current.rightchild; } return current; } -35-

36 특징 ~ 탐색작업을효율적으로하기위한자료구조 ~ key( 왼쪽서브트리 ) key( 루트노드 ) key( 오른쪽서브트리 ) ~ 이진탐색를중위순회하면오름차순으로정렬. -36-

37 알고리즘 ~ 비교한결과가같으면탐색성공. ~ 주어진키값이루트노드의키값보다작으면탐색은이루트노드의왼쪽자식을기준으로다시시작. ~ 주어진키값이루트노드의키값보다크면탐색은이루트노드의오른쪽자식을기준으로다시시작. -37-

38 search(x, k) if x=null if k=x->key then return NULL; then return x; else if k<x->key then return search(x->left, k); else return search(x->right, k); -38-

39 -39-

40 최대값과최소값탐색 ~ 현노드보다작은값은왼쪽자식에, 큰값은오른쪽자식에위치 ~ 최소값 트리의가장왼쪽 ~ 최대값 트리의가장오른쪽에존재 ~ 루트에서왼쪽자식을따라내려가면서더이상왼쪽자식이없는노드를만나면그노드가최소값을가진노드 ~ 최대값은오른쪽자식을따라가면찾을수있다. -40-

41 pubilc Node findmin() { } Node current = root; while (current.leftchild!= null) current = current.leftchild; return current; public Node findmax() { } Node current = root; while (current.rightchild!= null) current = current.rightchild; rightchild; return current; -41-

42 -42-

43 방법 이진트리에서삽입 ~ 노드가삽입될위치탐색. ~ 적절한경로를따라내려간뒤그위치의부모가되는노드탐색 ~ 삽입될위치의부모노드의키보다삽입될노드의키가작다면부모노드의왼쪽자식으로, 크다면부모노드의오른쪽자식으로생성. -43-

44 -44-

45 insert_node(t,z) p NULL; t root; while t NULL do p t; if z->key < p->key then t p->left; else t p->right; if p=null then root z;// 트리가비어있음 else if z->key < p->key then p->left z else p->right z -45-

46 이진트리에서삭제 3 가지의경우 ~ 삭제하려는노드가단말노드일경우 ~ 삭제하려는노드가하나의왼쪽이나오른쪽서브트리중하나만가지고있는경우 삭제하려는노드의자식노드가하나일때 ~ 삭제하려는노드가두개의서브트리모두가지고있는경우 삭제하려는노드의자식노드가둘일때 -46-

47 1. 삭제하려는노드의자식이없을때, 단말노드삭제 ~ 삭제노드의부모노드에게서삭제노드를가리키는링크를 null If (current.leftchild == null && current.rightchild == null) { if (current == root) root = null; else if (current == parent.leftchild) parent.leftchild = null; else parent.rightchild = null; } -47-

48 ~ 단말노드의부모노드를찾아서연결을삭제 (null) -48-

49 2. 삭제하려는노드의자식이하나일때 ~ 삭제하려는노드의자식노드와부모노드를바로연결. -49-

50 -50-

51 3. 삭제하려는노드의자식이둘일때 ~ 삭제하려는노드의자식중하나로그위치를대체할수없음 ~ 삭제될노드의위치를채워줄후보노드선정. 후보노드 (candidate node) ~ 삭제될노드의키값보다바로위의키값을가진노드나바로아래의키값을가진값을후보노드로선택. -51-

52 후보노드선정 1 ~ 삭제될노드보다큰값을갖는 ( 오른쪽 ) 서브트리선택. ~ 서브트리에서가장작은값을갖는노드를후보노드로지정. -52-

53 후보노드선정 2 ~ 삭제될노드보다작은값을갖는 ( 왼쪽 ) 서브트리선택. ~ 서브트리에서가장큰값을갖는노드를후보노드로지정. -53-

54 삭제하려는노드의자식이둘일때 ~ 잘못된대체의예 -54-

55 후보노드가삭제노드의오른쪽자식일경우 ~ 부모노드에서삭제노드에대한링크절단 ~ 후보노드로링크를연결. ~ 삭제노드의왼쪽자식은삭제노드와의링크절단, 후보노드의왼쪽자식으로링크. -55-

56 후보노드가삭제노드의오른쪽자식의왼쪽자손일경우 ~ 후보노드의오른쪽자식 후보노드의부모노드에대한왼쪽자식노드로저정 ~ 삭제노드의오른쪽자식 후보노드의오른쪽자식으로지정. ~ 부모노드에서삭제노드에대한링크절단, 후보노드로연결 ~ 삭제노드의왼쪽자식 삭제노드와의링크를끊고후보노드의왼쪽자식으로연결 -56-

57 -57-

58 -58-

59 특징 4.7 효율성 ~ 트리연산은하위레벨로의탐색을포함. ~ 꽉찬트리에서노드의반정도가맨아래레벨에존재. ~ 노드들에대한연산 ( 삽입, 삭제등 ) 은최하위레벨에있는노드까지찾는연산을필요로함 ~ 탐색하는동안최소한하나의레벨에하나의노드를방문 ~ 어떠한연산을하는데걸리는시간은트리의레벨에따라유추 노드의수를 N, 레벨의수를 L ~ L = log 2 (N + 1) -59-

Microsoft PowerPoint - chap10_tree

Microsoft PowerPoint - chap10_tree Chap. 10 : Tree 2007 학년도 2 학기 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드

More information

Ch.1 Introduction

Ch.1 Introduction Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2 트리자료구조를사용하는이유?

More information

o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드,

o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드, Tree & Heap SANGJI University Kwangman Ko kkman@sangji.ac.kr - 1 - o 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 - 2 - o 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조.

More information

7장

7장 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트

More information

08장.트리

08장.트리 ---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 회사의조직 파일디렉토리구조 결정트리 ( 예 ) 골프에대한결정트리 트리의용어 노드 (node): 트리의구성요소

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 yicho@gachon.ac.kr 1 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 2 2 회사의조직 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 7. 트리 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 트리의개념 트리 (Tree) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 정의 (1) 하나의루트 (root) 노드 (2) 다수의서브트리 (subtree) 트리는부모-자식관계의노드들로이루어짐

More information

chap 5: Trees

chap 5: Trees Chapter 5. TREES 목차 1. Introduction 2. 이진트리 (Binary Trees) 3. 이진트리의순회 (Binary Tree Traversals) 4. 이진트리의추가연산 5. 스레드이진트리 (Threaded Binary Trees) 6. 히프 (Heaps) 7. 이진탐색트리 (Binary Search Trees) 8. 선택트리 (Selection

More information

chap 5: Trees

chap 5: Trees 5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경

More information

입학사정관제도

입학사정관제도 자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1 8 장트리 소프트웨어학과원성현교수 93 1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy)

More information

제 1 장 기본 개념

제 1 장 기본 개념 이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)

More information

05_tree

05_tree Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical

More information

Microsoft PowerPoint - 제8장-트리.pptx

Microsoft PowerPoint - 제8장-트리.pptx 제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,

More information

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600 균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at

More information

Chapter 08. 트리(Tree)

Chapter 08. 트리(Tree) 윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예

More information

Microsoft PowerPoint - 자료구조2008Chap07

Microsoft PowerPoint - 자료구조2008Chap07 제 7 장트리 7.1 트리의정의 1 Tree 비선형구조, 다차원적구조 원소마다다음에여러개의원소가존재 하나이상의노드로구성된유한집합 정의1 : 루트 (root) 라는특별한노드를가지는사이클이존재치않는그래프 (acyclic graph) 정의 2 : 하나이상의노드로구성된유한집합 루트 (root) 라는특별한노드존재 나머지노드들은다시각각의트리이면서교차하지않는분리집합 (disjoint

More information

제 11 장 다원 탐색 트리

제 11 장 다원 탐색 트리 제 11 장 다원탐색트리 Copyright 07 DBLB, Seoul National University m- 원탐색트리의정의와성질 (1) 탐색성능을향상시키려면메모리접근횟수를줄여야함 탐색트리의높이를줄여야함 차수 (degree) 가 2보다큰탐색트리가필요 m- 원탐색트리 (m-way search tree) 공백이거나다음성질을만족 (1) 루트는최대 m 개의서브트리를가진다.

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음

More information

Microsoft PowerPoint - 제9장-트리의응용.pptx

Microsoft PowerPoint - 제9장-트리의응용.pptx 제 9 강의. 트리의탐색 1. 이진트리탐색알고리즘 2. 쓰레드 (Threaded) 이진트리 3. 이진트리를다루는알고리즘 1 1. 이진트리탐색알고리즘 트리의탐색 (traversal) 은트리의각노드를방문하는작업을말한다. ( 왜방문할까요?) 다음과같은방법들을생각해볼수있다. 방법 1) 레벨순 : 레벨이낮은순으로방문 A B C D E F G H 3가지다른방법이나올수있다.

More information

Microsoft PowerPoint - Chap5 [호환 모드]

Microsoft PowerPoint - Chap5 [호환 모드] 데이터구조 (hapter 5: Trees) 2011 년봄학기 숙명여자대학교정보과학부멀티미디어과학전공박영호 Index hapter 01: asic oncepts hapter 02: rrays and Structures hapter 03: Stacks and Queues hapter 04: Lists hapter 05: Trees hapter 06: Graphs

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터

More information

e-비즈니스 전략 수립

e-비즈니스 전략 수립 트리 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 트리의개념을이해한다. 이진트리의자료구조를알아본다. 이진트리에서의순회를이해한다. 이진탐색트리의개념을이해하고연산방법을이해한다. 히프의자료구조를이해한다. 내용 트리 이진트리 이진트리의구현 이진트리의순회 이진탐색트리 히프 2/104 1. 트리 트리 (tree) 원소들간에 1:

More information

슬라이드 1

슬라이드 1 6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,

More information

Microsoft PowerPoint - 6장 탐색.pptx

Microsoft PowerPoint - 6장 탐색.pptx 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential

More information

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures 단일연결리스트 (Singly Linked List) 신찬수 연결리스트 (linked list)? tail 서울부산수원용인 null item next 구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.date // 구조체 a의멤버접근 struct

More information

1장. 리스트

1장. 리스트 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential

More information

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우

More information

PowerPoint 프레젠테이션

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 3. 트리 3.1 트리의개요 3.2 이진트리 3.3 트리의운행 3.1 트리의개요 트리 : 그래프의일종 데이터 : 노드 순환적정의 T = {R, T 1,T 2, T n } R : 루트 T i : 서브-트리 ( 트리 ) 3.1 트리의개요 1. 노드 2. 근노드 3. 서브트리 4. 차수 5. 단노드 6. 간노드 (nonterminal node) 7. 부-노드,

More information

4.1 관계

4.1 관계 5 장트리 트리 (tree) 정보의항목들이가지 (branch) 로연결될수있게데이터가조직되는것, 예 ) 그림 5.1 정의 : 트리는 1 개이상의노드로이루어진유한집합으로서 1 root node 2 나머지노드들은 n( 0) 개의분리집합 (disjoint set) T 1, T 2,, T n 으로분리, T i 는각각트리로서 subtree 노드 : 정보항목 + 다른노드로뻗어진가지

More information

PowerPoint 프레젠테이션

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

More information

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100 2015-1 프로그래밍언어 9. 연결형리스트, Stack, Queue 2015 년 5 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 연결리스트 (Linked List) 연결리스트연산 Stack

More information

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]

More information

슬라이드 제목 없음

슬라이드 제목 없음 Chapter 5: TREES Trees Trees Def) a tree is finite set of one or more nodes such that 1) there is a special node (root) 2) remaining nodes are partitioned into n 0 disjoint trees T 1,T 2,,T n where each

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)

More information

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를 리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은

More information

06장.리스트

06장.리스트 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :

More information

Microsoft PowerPoint - Chap5 [호환 모드]

Microsoft PowerPoint - Chap5 [호환 모드] 5.3 Binary Tree Traversal Tree 의각 node 를한번씩방문하는알고리즘 각 node 와그 node 의 subtree 들을동등하게취급하면 6 개의 traversal 조합이있다. (L: Left 로움직임, V: 노드를 visiting, R: Right 로움직임 ) (1) LVR, (2) LRV, (3) VLR, (4) VRL, (5) RVL,

More information

5 장 트 리

5 장  트 리 5 장 트리 Copyright 2007 DBLAB, Seoul National University 트리구조 Copyright 2007 DBLAB, Seoul National University 2 트리 트리 : 하나이상의노드 (node) 로이루어진유한집합 1 하나의루트 (root) 노드 2 나머지노드들은 n( 0) 개의분리집합 T 1, T 2,, T n 으로분할

More information

Lab 3. 실습문제 (Single linked list)_해답.hwp

Lab 3. 실습문제 (Single linked list)_해답.hwp Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.

More information

C 언어 강의노트

C 언어 강의노트 C언어 (CSE2035) (15-1 Lists) Linear list 의구성, Insertion, deletion 윤용운, Ph.D. Dept. of Computer Science and Engineering Sogang University Seoul, Korea Tel: 010-3204-6811 Email : yuyoon0@sogang.ac.kr 2018-01-11

More information

OCW_C언어 기초

OCW_C언어 기초 초보프로그래머를위한 C 언어기초 4 장 : 연산자 2012 년 이은주 학습목표 수식의개념과연산자및피연산자에대한학습 C 의알아보기 연산자의우선순위와결합방향에대하여알아보기 2 목차 연산자의기본개념 수식 연산자와피연산자 산술연산자 / 증감연산자 관계연산자 / 논리연산자 비트연산자 / 대입연산자연산자의우선순위와결합방향 조건연산자 / 형변환연산자 연산자의우선순위 연산자의결합방향

More information

CH06)자료구조.hwp

CH06)자료구조.hwp 자료구조 (Data Structure) ) 자료구조의정의 프로그램에서사용하기위한자료를저장매체에저장하는방법및각자료간의관계, 처리방법을분석하는이론 자료의표현과연산의기초과학이다. 일련의자료들을조직화, 구조화시킨다. 모든자료구조에대하여연산처리가가능하다. 구현된자료구조에따라프로그램실행시간이다르다. 2) 자료구조의목적 ( 이유 ) 실제적으로물리적인저장장치는일정한규칙으로하나의선형형태로존재하기때문에그특성에맞게적절한형태로

More information

Chapter 4. LISTS

Chapter 4. LISTS C 언어에서리스트구현 리스트의생성 struct node { int data; struct node *link; ; struct node *ptr = NULL; ptr = (struct node *) malloc(sizeof(struct node)); Self-referential structure NULL: defined in stdio.h(k&r C) or

More information

11장 포인터

11장 포인터 Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함

More information

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular

More information

11강-힙정렬.ppt

11강-힙정렬.ppt 11 (Heap ort) leejaku@shinbiro.com Topics? Heap Heap Opeations UpHeap/Insert, DownHeap/Extract Binary Tree / Index Heap ort Heap ort 11.1 (Priority Queue) Operations ? Priority Queue? Priority Queue tack

More information

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 Data structure: Assignment 1 Seung-Hoon Na October 1, 018 1 1.1 Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 multiline으로 구성될 수 있으며, 한 라인에는 임의의 갯수의 숫자가 순서대로 나열될

More information

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ 00. 리스트 자료구조 01. 링크드 리스트 02. 더블 링크드 리스트 03. 환형 링크드 리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : (

More information

1장. 리스트

1장. 리스트 01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef

More information

Algorithms

Algorithms 자료구조 & 알고리즘 리스트 (List) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 선형리스트 연결리스트 2 선형리스트 선형리스트 선형리스트의개념 선형리스트의구현 연결리스트 3 선형리스트개념 리스트 (List) 목록, 대부분의목록은도표 (Table) 형태로표시 추상자료형리스트는이러한목록또는도표를추상화한것

More information

Chapter 4. LISTS

Chapter 4. LISTS 6. 동치관계 (Equivalence Relations) 동치관계 reflexive, symmetric, transitive 성질을만족 "equal to"(=) 관계는동치관계임. x = x x = y 이면 y = x x = y 이고 y = z 이면 x = z 동치관계를이용하여집합 S 를 동치클래스 로분할 동일한클래스내의원소 x, y 에대해서는 x y 관계성립

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2 제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.

More information

Microsoft PowerPoint - chap04-연산자.pptx

Microsoft PowerPoint - chap04-연산자.pptx int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); } 1 학습목표 수식의 개념과 연산자, 피연산자에 대해서 알아본다. C의 를 알아본다. 연산자의 우선 순위와 결합 방향에

More information

2002년 2학기 자료구조

2002년 2학기 자료구조 자료구조 (Data Structures) Chapter 1 Basic Concepts Overview : Data (1) Data vs Information (2) Data Linear list( 선형리스트 ) - Sequential list : - Linked list : Nonlinear list( 비선형리스트 ) - Tree : - Graph : (3)

More information

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 제 11 장포인터 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습합니다.

More information

03_queue

03_queue Queue Data Structures and Algorithms 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2 큐의이해와 ADT 정의 Data Structures and Algorithms 3 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in,

More information

1장. 리스트

1장. 리스트 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 05. AVL 트리 06. B- 트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리,

More information

슬라이드 1

슬라이드 1 컬렉션프레임워크 (Collection Framework) 의정의 - 다수의데이터를쉽게처리할수있는표준화된방법을제공하는클래스들 - 데이터의집합을다루고표현하기위한단일화된구조 (architecture) - JDK 1.2 이전까지는 Vector, Hashtable, Properties와같은컬렉션클래스로서로다른각자의방식으로처리 - 컬렉션프레임워크는다수의데이터를다루는데필요한다양하고풍부한클래스들을제공하므로프로그래머의부담을상당부분덜어준다.

More information

1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ

1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ Linked List 2010 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트

More information

리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li

리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li Linked List 2011 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트

More information

Chap 6: Graphs

Chap 6: Graphs 5. 작업네트워크 (Activity Networks) 작업 (Activity) 부분프로젝트 (divide and conquer) 각각의작업들이완료되어야전체프로젝트가성공적으로완료 두가지종류의네트워크 Activity on Vertex (AOV) Networks Activity on Edge (AOE) Networks 6 장. 그래프 (Page 1) 5.1 AOV

More information

Microsoft PowerPoint - chap11-포인터의활용.pptx

Microsoft PowerPoint - chap11-포인터의활용.pptx #include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 포인터를 사용하는 다양한 방법에

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E > 제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다

More information

리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센

리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센 Linked List 2014 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트

More information

슬라이드 1

슬라이드 1 Linked List 2015 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트

More information

Microsoft PowerPoint - chap4_list

Microsoft PowerPoint - chap4_list Chap. 4 : 리스트 (list) 2007 학년도 2 학기 리스트 1. 리스트개념 ~ 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 ~ 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 ~ 요일 : ( 일요일, 월요일,, 토요일 ) ~ 한글자음의모임 : (ᆨ,ᆫ,,ᄒ) ~ 핸드폰의문자메시지리스트

More information

Microsoft PowerPoint - chap-11.pptx

Microsoft PowerPoint - chap-11.pptx 쉽게풀어쓴 C 언어 Express 제 11 장포인터 컴퓨터프로그래밍기초 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 컴퓨터프로그래밍기초 2 포인터란? 포인터 (pointer): 주소를가지고있는변수 컴퓨터프로그래밍기초 3 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다.

More information

PowerPoint Presentation

PowerPoint Presentation 자바프로그래밍 1 배열 손시운 ssw5176@kangwon.ac.kr 배열이필요한이유 예를들어서학생이 10 명이있고성적의평균을계산한다고가정하자. 학생 이 10 명이므로 10 개의변수가필요하다. int s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; 하지만만약학생이 100 명이라면어떻게해야하는가? int s0, s1, s2, s3, s4,

More information

14장.탐색

14장.탐색 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 탐색 1/28 탐색 (search) 이란? 여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열,

More information

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D> 연결자료구조 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다. 연결자료구조를이용한다항식의덧셈연산방법을알아본다. 내용 배열연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다.

More information

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 (   ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각 JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( http://java.sun.com/javase/6/docs/api ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각선의길이를계산하는메소드들을작성하라. 직사각형의가로와세로의길이는주어진다. 대각선의길이는 Math클래스의적절한메소드를이용하여구하라.

More information

EA0015: 컴파일러

EA0015: 컴파일러 5 Context-Free Grammar 무엇을공부하나? 앞에서배운 " 정규식 " 은언어의 " 어휘 (lexeme)" 를표현하는도구로사용되었다. 언어의 " 구문 (syntax)" 은 " 정규언어 " 의범위를벗어나기때문에 " 정규식 " 으로표현이불가능하다. 본장에서배우는 " 문맥자유문법 " 은언어의 " 구문 (syntax)" 을표현할수있는도구이다. 어떤 " 문맥자유문법

More information

ABC 10장

ABC 10장 10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;

More information

Microsoft PowerPoint - ch07 - 포인터 pm0415

Microsoft PowerPoint - ch07 - 포인터 pm0415 2015-1 프로그래밍언어 7. 포인터 (Pointer), 동적메모리할당 2015 년 4 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) Outline 포인터 (pointer) 란? 간접참조연산자

More information

슬라이드 1

슬라이드 1 CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 비트연산자 1 1 비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 진수법! 2, 10, 16, 8! 2 : 0~1 ( )! 10 : 0~9 ( )! 16 : 0~9, 9 a, b,

More information

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770> 연습문제해답 5 4 3 2 1 0 함수의반환값 =15 5 4 3 2 1 0 함수의반환값 =95 10 7 4 1-2 함수의반환값 =3 1 2 3 4 5 연습문제해답 1. C 언어에서의배열에대하여다음중맞는것은? (1) 3차원이상의배열은불가능하다. (2) 배열의이름은포인터와같은역할을한다. (3) 배열의인덱스는 1에서부터시작한다. (4) 선언한다음, 실행도중에배열의크기를변경하는것이가능하다.

More information

중간고사 (자료 구조)

중간고사 (자료 구조) Data Structures 215 중간고사 문제에서명시적으로기술하지않은부분은교재의내용에근거함. 215. 1. 27. 1 다음용어에대하여간단하게설명하시오 ( 각 3 점 *1=3 점 ) 1 abstract data type 6 Circular linked list 2 recursion 3 time complexity 4 space complexity 5 Single

More information

Microsoft PowerPoint - 07-chap05-Stack.ppt

Microsoft PowerPoint - 07-chap05-Stack.ppt / 스택이란? 스택 stack): 쌓아놓은더미 hapter 5 스택 Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 스택의개념이해 스택의동작원리이해 배열과연결리스트를이용한스택구현 스택응용프로그램 스택의특징 후입선출 LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감.

More information

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Lab 5. 실습문제 (Double linked list)-1_해답.hwp Lab 5. Doubly-linked list 의구현 실험실습일시 : 2009. 4. 13. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 19. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다.

More information

adfasdfasfdasfasfadf

adfasdfasfdasfasfadf C 4.5 Source code Pt.3 ISL / 강한솔 2019-04-10 Index Tree structure Build.h Tree.h St-thresh.h 2 Tree structure *Concpets : Node, Branch, Leaf, Subtree, Attribute, Attribute Value, Class Play, Don't Play.

More information

03장.스택

03장.스택 ---------------- DT STRUCTURES USING C ---------------- CHPTER 스택 1/30 스택이란? 스택 (stack): 쌓아놓은더미 후입선출 (LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감 2/30 스택의구조 스택상단 : top 스택하단 : 불필요 요소, 항목 공백상태, 포화상태 삽입, 삭제연산

More information

Chap 6: Graphs

Chap 6: Graphs AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node

More information

untitled

untitled 1. void inorder(tree_ptr ptr) { if(ptr) { inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child); 2) => A / B * C * D + E () A / B * C * D + E void preorder(tree_ptr ptr) { if(ptr)

More information

Microsoft PowerPoint Backtracking.pptx

Microsoft PowerPoint Backtracking.pptx 알고리즘 (Algorithm) g( 되추적 ) 2011년봄학기 강원대학교컴퓨터과학전공문양세 되추적 (backtracking)? 갈림길에표시를해두었더라면 간단히말해서되추적은갈림길에표시를해두는기법이다. Page 2 강의순서 되추적기술 n-queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits

More information

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1

More information

v 이원탐색트리 (binary search tree) u 인덱스를조직하는한가지방법 u 이진트리 (binary tree) 유한한수의노드를가진트리 공백 (empty) 이거나루트와두개의분리된이진트리즉, 왼쪽서브트리 (left subtree) 와오른쪽서브트리 (right su

v 이원탐색트리 (binary search tree) u 인덱스를조직하는한가지방법 u 이진트리 (binary tree) 유한한수의노드를가진트리 공백 (empty) 이거나루트와두개의분리된이진트리즉, 왼쪽서브트리 (left subtree) 와오른쪽서브트리 (right su 6장인덱스구조 v 인덱스 (index) u 특징 화일의레코드들에대한효율적접근을위한조직 < 키값, 레코드주소 ( 포인터 )> 쌍으로구성 u 종류 키값의유형에따른인덱스 기본인덱스 (primary index) : 키값이기본키인인덱스 보조인덱스 (secondary index) : 기본인덱스이외의인덱스 화일조직에따른인덱스 집중인덱스 (clustered index) :

More information

11장 포인터

11장 포인터 누구나즐기는 C 언어콘서트 제 9 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다. 첫번째바이트의주소는 0, 두번째바이트는 1, 변수와메모리

More information

Microsoft PowerPoint - 08-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In

More information

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-chap06-Queue.ppt / 큐 (QUEUE) Chapter 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 큐 Ticket ox Dongwon Jeong djeong@kunsan.ac.kr Department of Kunsan National University 전단 () 후단 () 학습목표 큐 DT 큐의개념및추상데이터타입에대한이해

More information

09J1_ _R.hwp

09J1_ _R.hwp 상수삽입전이시간을가지는양단우선순위큐 217 DOI: 10.3745/KIPSTA.2009.16-A.3.217 상수삽입전이시간을가지는양단우선순위큐 정해재 요 약 우선순위큐는스케줄링, 정렬, 유전자검색과같은우선순위에따른검색, 최단거리계산과같은응용에사용될수있다. 본논문에서제안하는배열을이용한양단우선순위큐자료구조는삽입과삭제연산에각각 O(1) 전이시간과 O(logn) 시간이걸린다.

More information

쉽게배우는알고리즘 5 장. 검색트리 IT COOKBOOK 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 한빛미디어 1

쉽게배우는알고리즘 5 장. 검색트리   IT COOKBOOK 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 한빛미디어 1 쉽게배우는알고리즘 5 장. 검색트리 htt://academy.hanb.co.k 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 - 2 - 한빛미디어 1 학습목표 검색에서레코드와키의역할을구분한다. 이진검색트리에서의검색 삽입 삭제작업의원리를이해한다. 이진검색트리의균형이작업의효율성에미치는영향을이해하고, 레드블랙트리의삽입

More information

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - 스택 (stack) SANGJI University Kwangman Ko o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 13 장. 균형탐색트리 균형탐색트리 트리의작업효율을높이기위한다양한균형트리알고리즘을비교 학습목표 트리의균형이효율에미치는영향을이해한다. AVL 트리에서균형을회복하기위한방법을이해한다. 스플레이기법을이해한다. 2-3 트리에서균형을회복하기위한방법을이해한다. 2-3-4 트리와레드블랙트리의관계를이해한다. 1 균형 균형 2 AVL G. M. Adelson-Velskii and

More information