제 10 장 최적 이원 탐색 트리
|
|
|
- 찬성 표
- 6 years ago
- Views:
Transcription
1 제 1 장 최적이원탐색트리 Copyright 27 DBLAB, Seoul National University
2 최적이원탐색트리 (1/11) 개요 정적원소들의집합에대한이원탐색트리구조 삽입이나삭제는하지않고탐색만수행 정렬된리스트 함수 Get( 프로그램 5.19 참고 ) 이용 비용측정방법 함수 Get 이용 for 루프를 l 번반복 리스트 (5,1,15) 에서의이원탐색에해당되는이원탐색트리 Copyright 27 DBLAB, Seoul National University 2
3 최적이원탐색트리 (2/11) 예제 (a) 두이원탐색트리 (b) 최악의경우탐색시간 : (a) 4 번, (b) 3 번 성공적인탐색에필요한평균 : (a) 2.4 번, (b) 2.2 번 5,1,15,2,25 가각각.3,.3,.5,.5,.3 의확률로탐색 : (a) 1.85, (b) 2.5 Copyright 27 DBLAB, Seoul National University 3
4 최적이원탐색트리 (3/11) 이원탐색트리의평가 특별한사각형노드 (square node) 추가시유용 (a) 확장이진트리 외부노드 ( 실패노드 ) : n+1 개의사각노드 내부노드 : 원래노드 (b) Copyright 27 DBLAB, Seoul National University 4
5 최적이원탐색트리 (4/11) 외부경로길이 (external path length) 루트로부터각외부노드경로길이의합 내부경로길이 (internal path length) 루트로부터각내부노드경로길이의합 내부경로길이 (I)= =7 외부경로길이 (E)= = I 와 E 의관례 (n 개의내부노드를가질경우 ) E=I+2n E 가최고일때 I 도최고 Copyright 27 DBLAB, Seoul National University 5
6 최적이원탐색트리 (5/11) I 의최소값 최악의경우 : 트리가편향될때 I n j 일반적인경우 i n( n 완전이진트리일경우 1 1) / i [log i O( nlog2 1 i n 2 n ) Copyright 27 DBLAB, Seoul National University 6
7 최적이원탐색트리 (6/11) 정적원소집합을이원탐색트리로표현 탐색이성공적일때비용 pi level( a 1 i n 탐색이실패적일때비용 q i ( level( 실패노드i) 1) 1 i n 이원탐색트리의총비용 p level( a ) q (level( 실패노드i) 1) 1 i n i 최적이원탐색트리의성립 p i qi 1 1 i n 1 i n i i ) (a i 를탐색할확률이 p i 일경우 ) ( 탐색중인원소가 Ei 에있을확률이 qi 일경우 ) 1 i n i Copyright 27 DBLAB, Seoul National University 7
8 최적이원탐색트리 (7/11) 예제 (a) (b) (c) (d) (e) 3 개의원소를가진이원탐색트리 똑같은확률 p i =q i =1/7 일경우 cost(tree a) = 15/7 ; cost(tree b) = 13/7 cost(tree c) = 15/7 ; cost(tree d) = 15/7 ; cost(tree e) = 15/7 p 1 =.5, p 2 =.1, p 3 =.5, q =.15, q 1 =.1, q 2 =.5, q 3 =.5 cost(tree a) = 2.65 ; cost(tree b) = 1.9 cost(tree c) = 1.5 ; cost(tree d) = 2.5 ; cost(tree e) = 1.6 Copyright 27 DBLAB, Seoul National University 8
9 최적이원탐색트리 (8/11) 최적이원탐색트리의성질 a 1 <a 2 <.<a n, n 개의키 T ij 가 a i+1,.,a j, i<j 가중치 : W ij = q i + 만약 T ij 가 a i+1,.,a j 와 r ij =k 에대한최적이원탐색트리라면 k 는 i<k j 를만족 비용 : c ij = p k + cost(l) + cost(r) + weight(l) + weight(r) = p k + c i,k-1 + c kj + w i,k-1 + w kj = w ij + c i,k-1 + c kj T ij 최적 r ij =k일때 w ij + c i,k-1 + c kj = {w ij + c i,l-1 + c lj } min min i 1 j c i,k-1 + c kj = {c i,l-1 + c lj } i 1 j j ( qk p k i 1 k ) L Weight(T i,k-1 ) = w i,k-1 ak R 최적이원탐색트리 T ij Weight(T kj ) = w kj Copyright 27 DBLAB, Seoul National University 9
10 최적이원탐색트리 (9/11) 예제 1.3 n=4, (a 1, a 2, a 3, a 4 ) = (1,15,2,25) (p 1, p 2, p 3, p 4 ) = (3, 3, 1, 1), (q, q 1, q 2, q 3, q 4 ) = (2, 3, 1, 1, 1) W 1 = p 1 + w + w 11 = p 1 + q 1 + w = 8 c 1 = w 1 + min {c + c 11 }= 8 r 1 = 1 W 12 = p 2 + w 11 + w 22 = p 2 + q 2 + w 11 = 7 c 12 = w 12 + min {c 11 + c 22 }= 7 r 12 = 2 W 23 = p 3 + w 22 + w 33 = p 3 + q 3 + w 22 = 3 c 23 = w 23 + min {c 22 + c 33 }= 3 r 23 = 3 W 34 = p 4 + w 33 + w 44 = p 4 + q 4 + w 33 = 3 c 34 = w 34 + min {c 33 + c 44 }= 3 r 34 = 4 Copyright 27 DBLAB, Seoul National University 1
11 최적이원탐색트리 (1/11) W = 2 C = R = W 1 = 8 C 1 = 8 R 1 = 1 W 2 =12 C 2 =19 R 2 = 1 W 3 =14 C 3 =25 R 3 = 2 W 4 =16 C 4 =32 R 4 = 2 W 11 = 3 C 11 = R 11 = W 12 = 7 C 12 = 7 R 12 = 2 W 13 = 9 C 13 =12 R 13 = 2 W 14 =11 C 14 =19 R 14 = 2 W 22 = 1 C 22 = R 22 = W 23 = 3 C 23 = 3 R 23 = 3 W 24 = 5 C 24 = 8 R 24 = 3 W 33 = 1 C 33 = R 33 = W 34 = 3 C 34 = 3 R 34 = 4 C 4 와 r 4 의계산 W 44 = 1 C 44 = R 44 = 계산은 행부터 4 행까지순서로수행됨 Copyright 27 DBLAB, Seoul National University 11
12 최적이원탐색트리 (11/11) 예제 1.3 에대한최적이원탐색트리 c 와 r 값을구하는함수의복잡도 C ij 는 (j-i)= 1, 2,., n 순서로계산 j-i=m일때 n-m+1개의 C ij 계산 j-i=m인모든 c ij 의총연산시간 : O(nm-m 2 ) 총연산시간 : n m 1 ( nm m 2 ) O( n 3 ) Copyright 27 DBLAB, Seoul National University 12
13 AVL 트리 (1/3) 어떤원소를찾기위한최대비교횟수 JAN JUL FEB MAR FEB MAY APR JUN MAY AUG JUL DEC 3.5 (a) 1 년 12 달에대한이원탐색트리 APR AUG DEC SEP AUG JAN MAR OCT OCT APR DEC JUN NOV SEP NOV (b) 1 년 12 달에대한균형트리 3.1 FEB JAN JUL 6.5 (c) 성능이저하된이원탐색트리 JUN MAR MAY NOV OCT Copyright 27 DBLAB, Seoul National University 13
14 AVL 트리 (2/3) 정의 공백트리는높이균형을이룬다 T L 과 T R 을가진공백이아닌이진트리라할때 T L 과 T R 이높이균형을이룬다 h L h R 1(h L 과 h R ) 은각각 T L T R 의높이 T 는높이균형을이루며그역도성립함 앞장에서 (a), (c) 는높이균형을이루지못하는반면 (b) 는높이균형을이룸 Copyright 27 DBLAB, Seoul National University 14
15 AVL 트리 (3/3) 균형인수 (balance factor) 왼쪽, 오른쪽서브트리사이의높이차 BF(T) = hl hr AVL 트리의어떠한노드 T 에대해서도 BF(T)= -1,, 1 삽입된노드 Y 에가장가까우면서균형인수가 ±2 인조상노드 A 에대한회전성질 LL: 새노드 Y 는 A 의왼쪽서브트리의왼쪽서브트리에삽입 LR: Y 는 A 의왼쪽서브트리의오른쪽서브트리에삽입 RR: Y 는 A 의오른쪽서브트리의오른쪽서브트리에삽입 RL: Y 는 A 의오른쪽서브트리의왼쪽서비트리에삽입 단일회전 (Single rotation) : LL 과 RR 불균형을바로잡는변환 이중회전 (Double rotation) : LR 과 RL 불균형을바로잡는변환 Copyright 27 DBLAB, Seoul National University 15
16 LL 회전 삽입전 B L 에삽입한뒤 LL 회전뒤 균형인수는노드안에있음 서브트리높이는서브트리이름밑에있음 Copyright 27 DBLAB, Seoul National University 16
17 LR 회전 삽입전 B R 에삽입한뒤 LR 회전뒤 b = bf(b) = bf(a) = 회전뒤 b = 1 bf(b) = and bf(a) = -1 회전뒤 b = -1 bf(b) = 1 and bf(a) = 회전뒤 Copyright 27 DBLAB, Seoul National University 17
18 트리확장및균형유지과정 (1/5) 삽입순서 MAR, MAY, NOV, AUG, APR, JAN, DEC, JUL, FEB, JUN OCT, SEP 순 -1 MAR MAR MAY (a) 삽입 MARCH (b) 삽입 MAY -2 MAR -1 MAY NOV RR MAR MAY NOV (c) 삽입 NOV Copyright 27 DBLAB, Seoul National University 18
19 트리확장및균형유지과정 (2/5) AUG +1 MAR +1 MAY NOV (d) 삽입 AUGUST APR +1 AUG +2 MAR +2 MAY NOV LL APR AUG +1 MAY MAR NOV (e) 삽입 APRIL Copyright 27 DBLAB, Seoul National University 19
20 트리확장및균형유지과정 (3/5) APR -1 AUG JAN +2 MAY +1 MAR NOV LR APR AUG MAR JAN -1 MAY NOV (e) 삽입 JANUARY APR -1 AUG DEC +1 MAR +1 JAN -1 MAY NOV APR -1 AUG DEC +1 MAR JAN -1 MAY JUL NOV (g) 삽입 DECEMBER (h) 삽입 JULY Copyright 27 DBLAB, Seoul National University 2
21 트리확장및균형유지과정 (4/5) ARP APR +1 AUG -2 AUG +2 MAR +1 JAN -1 DEC FEB -1 DEC FEB +2 MAR -1 JAN -1 MAY JUL -1 MAY -1 JUL JUN NOV RL ARP (i) 삽입 FEBRUARY NOV LR (j) 삽입 JUNE +1 AUG DEC FEB +2 MAR JAN +1 JAN DEC +1-1 AUG FEB ARP -1 MAY NOV Copyright 27 DBLAB, Seoul National University 21 JUL MAR -1 JUL -1 MAY JUN NOV
22 트리확장및균형유지과정 (5/5) JAN -1 DEC +1-1 MAR -1-2 AUG FEB JUL MAY -1 ARP JUN NOV OCT RR (k) 삽입 OCTOBER +1 JAN DEC MAR +1-1 AUG FEB JUL NOV ARP JUN MAY OCT +1 DEC +1 AUG FEB ARP -1 JAN -1 JUL JUN -1 MAR (l) 삽입 SEPTEMBER -1 NOV -1 MAY OCT SEP Copyright 27 DBLAB, Seoul National University 22
23 AVL 트리에서의삽입 여러구조들의비교 연산순차리스트연결리스트 AVL 트리 키가 k 인원소탐색 O(log n) O(n) O(log n) j 번째원소탐색 O(1) O(j) O(log n) 키가 k 인원소삭제 O(n) O(l) 1 O(log n) j 번째원소삭제 O(n - j) O(j) O(log n) 삽입 O(n) O(l) 2 O(log n) 순서대로출력 O(n) O(n) O(n) 1. K 의위치가알려진이중연결리스트 2. 삽입할위치가알려진경우 Copyright 27 DBLAB, Seoul National University 23
24 레드 - 블랙트리 (1/14) 정의 RB1. 루트와모든외부노드들은컬러가블랙이다. RB2. 루트에서외부노드로의경로는두개의연속적인레드노드를가질수없다. RB3. 루트에서외부노드로의모든경로들에있는블랙노드의수는동일하다. RB1'. 내부노드로부터외부노드로의포인터는블랙이다. RB2'. 루트에서외부노드로의경로는두개의연속적인레드포인터를가질수없다. RB3'. 루트에서외부노드로의모든경들에있는블랙포인터의수는동일하다. Copyright 27 DBLAB, Seoul National University 24
25 레드 - 블랙트리 (2/14) 레드 - 블랙트리 블랙포인터 레드포인터 Copyright 27 DBLAB, Seoul National University 25
26 레드 - 블랙트리 (3/14) 보조정리 1.1 루트로부터외부노드로의 2 개의경로 P, Q 가있을때 length(p) 2length(Q) 증명 임의레드 - 블랙트리에서루트의경로를 r 로둠. RB1' 로부터루트에서외부노드로의경로상에있는마지막포인터는블랙 RB2' 로부터 2 개의연속적인레드포인터를갖는경로미존재 각레드포인터뒤에는항상블랙포인터가와야함. 결과적으로루트에서외부노드로의각경로는 r, 2r 사이에서포인터를갖게됨. 따라서 length(p) 2length(Q) 임. Copyright 27 DBLAB, Seoul National University 26
27 레드 - 블랙트리 (4/14) 보조정리 1.2 레드 - 블랙트리높이 h, 트리내부노드수 n, 랭크 r 이면 (a) h 2r (b) n 2 r 1 (c) h 2log 2 (n+1) 증명 보조정리 1.1 에서 length > 2r 은존재하지않음. 따라서 h 2r 레벨 1 에서 r 까지외부노드가없고, 이러한레벨은 2 r -1 개의내부노드가있음. 따라서 2 r -1 은내부노드의최소한의수가됨. (b) 로부터 h 2log 2 (n+1) Copyright 27 DBLAB, Seoul National University 27
28 레드 - 블랙트리 (5/14) 레드 - 블랙트리의표현 구현에있어외부노드를표현하기위해물리적노드보다널포인터이용 노드의컬러를저장하기위해노드당 1bit 필요 포인터의컬러를저장하기위해노드당 2bit 필요 레드 - 블랙트리에서의탐색 일반적으로이원탐색트리의탐색에서사용하는 알고리즘을이용하여탐색 Copyright 27 DBLAB, Seoul National University 28
29 레드 - 블랙트리 (6/14) 레드 - 블랙트리로의삽입 불균형타입 LLb : pu 가 gu 의왼쪽자식이고 u 는 pu 의왼쪽자식이며, gu 의다른자식이블랙인경우 LLr : pu 가 gu 의왼쪽자식이고 u 는 pu 의왼쪽자식이며, gu 의다른자식이레드인경우 LRb : pu 가 gu 의왼쪽자식이고 u 는 pu 의오른쪽자식이며, gu 의다른자식이블랙인경우 LRr : pu 가 gu 의왼쪽자식이고 u 는 pu 의오른쪽자식이며, gu 의다른자식이레드인경우 위와마찬가지로 RRb, RRr, RLb, RLr 이있다. 불균형타입 XYr 는컬러에의해변경되지만, XYb 은회전이필요함. Copyright 27 DBLAB, Seoul National University 29
30 레드 - 블랙트리 (7/14) gu gu pu gur pu gur u pur u pur ul ur ul ur (a) LLr 불균형 (b) LLr 컬러변화뒤 gu gu pu gur pu gur pul u pul u ul ur (c) LRr 불균형 ul ur (d) LRr 컬러변화뒤 Copyright 27 DBLAB, Seoul National University 3
31 레드 - 블랙트리 (8/14) gu pu pu gur pul gu pul pur pur gur (a) LLb 불균형 (b) LLb 회전뒤 gu u pu gur pu gu pul u pul ul ur gur ul ur (c) LRb 불균형 (d) LRb 회전뒤 Copyright 27 DBLAB, Seoul National University 31
32 레드 - 블랙트리 (9/14) 예제 (a) 초기 (b) 7 을삽입 5 pu 5 gu u pu u 6 6 (c) 6 을삽입 (d) LLr 컬러변환 Copyright 27 DBLAB, Seoul National University 32
33 레드 - 블랙트리 (1/14) gu pu u (e) 65 삽입 (f) LRb 회전 gu 5 8 pu gu 65 9 u 65 9 pu u (g) 62 삽입 (g) LRr 컬러변경 Copyright 27 DBLAB, Seoul National University 33
34 레드 - 블랙트리 (11/14) (i) RLb 회전 Copyright 27 DBLAB, Seoul National University 34
35 레드 - 블랙트리 (12/14) 레드 - 블랙트리에조인 경우 1 A 와 B 가같은랭크를갖는다면 X, leftchild, rightchild B 의쌍을갖는새로운 root 를생성함으로써 C 가만들어진다고하자 C 의랭크는 A 와 B 의랭크보다하나높다 경우 2 rank(a) > rank(b) 를갖는다면 A 에서부터 B 와같은랭크를갖는 첫번째노드 Y 까지 rightchild 포인터를따라간다. p(y) 가 Y 의부모이면 rank(p(y)) = rank(y) + 1 P(Y) 에서 Y 로의포인터는블랙포인터 x, leftchild, Y, rightchild, B 의쌍을갖는새로운노드 Z 생성 경우 3 rank(a) < rank(b), 경우 2 와비슷 Copyright 27 DBLAB, Seoul National University 35
36 레드 - 블랙트리 (13/14) 3 원조인연산의분석 기술된함수가정확한지에대해서쉽게알수있다. 경우 1 은 O(1) 의시간이걸리고 경우 2, 3 은 O( rank(a) rank(b) ) 이걸린다 따라서 3 원조인은 O(log n) 의시간에수행될수있으며이때 n 은조인되고있는두트리의노드수를의미 레드 - 블랙트리의분할 단계 1 키값이 i 인원소를포함하고있는노드 P 를찾기위해 A 를탐색 그원소를참조인자 (parameter) x 에복사 B 와 C 를 P 의왼쪽과오른쪽서브트리가되도록초기화 단계 2 for (Q = parameter(p); Q; P = Q, Q = parent(q)) { if(p == Q leftchild) C.ThreeWayJoin(C,Q data, Q rightchild) else B.ThreeWayjoin(Q leftchild, Q data, B); } Copyright 27 DBLAB, Seoul National University 36
37 레드 - 블랙트리 (14/14) 분할연산의분석 분할되지않은트리에서노드 X 의랭크를 r(x) 라하면 R(Q) max{r(b), r(c)} 정의로부터 r(q )=r(q)+1 이고 R(B ) r(b)+1 이고 r(c ) r(c)+1 이므로 Q 가블랙자식 P 를가진노드를가리킬때 R(q )=r(q)+1 max{r(b), r(c)}+1 max{r(b ),r(c )} 성립 Q 가블랙자식을가진한노드를가리킬때시작부터 Q 가이노드에도달할때까지분할알고리즘 2 단계에서수행되는모든작업이 O(r(B)+r(C)+r(Q)) 를알수있음 R(Q) max{r(b), r(c)} 이기때문에단계 2 에서이루어진모든작업은 O(r(Q)) 이다. 요구되는시간은 O(log n) 임을알수있음 Copyright 27 DBLAB, Seoul National University 37
38 상향식스플레이트리 (1/8) 상향식스플레이트리 (bottom-up splay tree) 이원탐색트리와같은방식으로탐색, 삽입, 삭제, 조인연산이이루어지며, 다른것은연산이수행된후스플레이 (splay) 가실행됨 시작노드는다음과같이결정 탐색 : 스플레이를찾고자하는원소를포함하는노드로부터시작 삽입 : 스플레이에대한시작노드는새로삽입된노드 삭제 : 물리적으로삭제된노드의부모노드가스플레이의 시작노드가됨. 3 원조인 : 어떤스플레이도발생하지않음 분할 : 키 i 를분할한다고가정. 키 i 를포함하고있는노드에 대해먼저스플레이를수행한뒤에트리분할 Copyright 27 DBLAB, Seoul National University 38
39 상향식스플레이트리 (2/8) 단계정의 q를스플레이가수행되고있는노드라가정 초기에 q는스플레이가시작하는노드 만일 q가 이거나루트이면스플레이종료 만일 q가부모 p는있지만조부모가없는경우회전이수행되고스플레이가종료 만일 q가부모 p와조부모 gp를갖고있다면회전은 LL(p는 gp의왼쪽자식이고 q는 p의왼쪽자식 ) LR(p는 gp의왼쪽자식이고 q는 p의오른쪽자식 ) RR(p는 gp의오른쪽자식이고 q는 p의오른쪽자식 RL(p는 gp의오른쪽자식이고 q는 p의왼쪽자식 ) 분류되다. Copyright 27 DBLAB, Seoul National University 39
40 상향식스플레이트리 (3/8) p q a q p c gp b c a,b,c는서브트리 q가오른쪽자식이고조부모가없을때의회전 a q gp b q a p p d a p gp p b q gp c q d a b c d c d a b b c RR 타입회전 RL 타입회전 Copyright 27 DBLAB, Seoul National University 4
41 상향식스플레이트리 (4/8) i 번째연산에대한상환시간정의 (i 번째연산에대한실제시간 ) + P i P i-1 i 번째연산에대한실제시간정의 (i 번째연산에대한상환시간 ) + P i-1 P i 일련의 m 개연산을수행하는데필요한실제시간 (i번째연산에대한상환시간 ) + P P m i 전위함수정의 루트가 i 인서브트리의크기 s(i) 서브트리의총노드수일때 노드 i 의랭크 r(i) = log 2 s(i) 트리의전위 = i r ( i) Copyright 27 DBLAB, Seoul National University 41
42 Copyright 27 DBLAB, Seoul National University 42 상향식스플레이트리 (5/8) a b c d e f g h i j (a) 초기탐색트리 a b c d e f g h i j (b) RR 회전뒤 a b c d e f g h i j (c) LL 회전뒤 a b d ef g h i j c (d) LR 회전뒤
43 상향식스플레이트리 (6/8) a 2 8 j b 4 6 i c 3 d e f g 7 h (e) RL 회전뒤 Copyright 27 DBLAB, Seoul National University 43
44 상향식스플레이트리 (7/8) 보조정리 1.3 노드당 n 개의원소를갖는이원탐색트리고려 노드 q 에서시작하는연산의상환비용은 3( log 2 n -r(q))+1 증명 스플레이의정의의 3 단계를고려하면 (1) q 는 이거나루트, 트리의전위를바뀌지않으므로상환비용 = 실제비용, 비용은 1 (2) 회전수행, p 와 q 만랭크영향을받기때문에 Δp = r'(p)+r'(q)-r(p)-r(q), r'(p) r(p) 이므로 Δp = r'(q)-r(q) 상환비용은 r'(q)-r(q)+1 이하 (3) q, p, gp 의랭크만변경 Δp = r'(q)+r'(p)-r'(gp)-r(q)-r(p)-r'(gp), r(gp) = r'(q) 이므로 Δp = r'(p)+r'(gp)-r(q)-r(p) Copyright 27 DBLAB, Seoul National University 44
45 상향식스플레이트리 (8/8) RR 회전고려 r'(p) r'(q), r'(gp) r'(q), r(q) r(p) 이면 Δp 2(r'(q)-r(q)) gp q r'(q)>r(q) 라면 Δp 3(r'(q)-r(q)) -1 a p p d r'(q)=r(q) 라면 r'(q)=r(q)=r(p)=r(gp), s'(q)>s(q)+s'(g) 따라서 r'(gp)<r'(q) b q gp c r'(gp)=r'(q) 라면 s'(q)>2 r(q) +2 r '(gp) =2 r(q)+1 랭크정의를어기는것이므로 c d a b 식 (1) 로부터 Δp 2(r'(q)-r(q)) -1 = 3(r'(q)-r(q)) -1 RR 타입 따라서 RR 회전의상환비용은 1+3(r'(q)-r(q)) -1 = 3(r'(q)-r(q)) Copyright 27 DBLAB, Seoul National University 45
46 하향식스플레이트리 (1/6) 하향식스플레이트리 (Top-Down splay trees) 상향식스플레이트리에서적용된것과같이정의 루트에서스플레이노드까지경로를따름 3 개의구성요소 이원탐색트리 small 이원탐색트리 big 스플레이트리 7 개의경로 경우 : x 는스플레이노드인경우분할을종료한다. 경우 L : 스플레이노드가 x 의자식인경우, x 와그오른쪽서브트리는스플레이노드의키보다더큰키를포함 경우 R : 스플레이노드가 x 의오른쪽자식인경우 L 과대칭적임 경우 LR : 경우 L 을처리한후, 경우 R 을처리 경우 RL : 경우 R 을처리한후, 경우 L 을처리 경우 LL : 경우 L 을두번적용하는것이아니라, x 주변으로 LL 회전 경우 RR : 경우 LL 과대칭적임 Copyright 27 DBLAB, Seoul National University 46
47 하향식스플레이트리 (2/6) x big A b D B AR E DR BL BR (a) L 변형전 ER big x D B b E DR BL BR A ER (b) L 변형뒤 AR Copyright 27 DBLAB, Seoul National University 47
48 하향식스플레이트리 (3/6) x A big B AR b D C BR E DR ER CL CR (a) LL 변형전 big D x C b E DR CL CR B A ER (b) LL 변형뒤 BR AR Copyright 27 DBLAB, Seoul National University 48
49 Copyright 27 DBLAB, Seoul National University 49 하샹식스플레이트리의예하향식스플레이트리 (4/6) x b c d e f g h i 1 small s a 9 x big j (a) RL 변형뒤 (b) LR 변형뒤 c d e f g h x 1 small s a 2 b 9 x big j 8 i
50 Copyright 27 DBLAB, Seoul National University 5 하향식스플레이트리 (5/6) e f 1 small a (c) LL 변형뒤 x c d 2 b s i j h g big b (d) RR 변형뒤 5 e f x 1 2 a b small c 4 3 d s i j h g big b
51 Copyright 27 DBLAB, Seoul National University 51 하향식스플레이트리 (6/6) (e) 스플레이노드의서브트리를이동한뒤 5 x 1 2 a b small c 4 3 d s i j h g big b e f (f) 최종탐색트리 d e c i j h g f 5 a b
歯3일_.PDF
uuhm Daewoo Daily * 0.0% 23.6% 38.2% 50.0% 61.8% 100.0% 980 970 960 950 940 930 920 910 900 890 880 870 860 850 840 830 820 810 800 790 780 770 760 750 740 730 720 710 700 690 680 670 660 650 640 630
07.... 01V28.
National Election Commission 9 September S M T W T F S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23/30 24 25 26 27 28 29 11 November S M T W T F S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
제 11 장 다원 탐색 트리
제 11 장 다원탐색트리 Copyright 07 DBLB, Seoul National University m- 원탐색트리의정의와성질 (1) 탐색성능을향상시키려면메모리접근횟수를줄여야함 탐색트리의높이를줄여야함 차수 (degree) 가 2보다큰탐색트리가필요 m- 원탐색트리 (m-way search tree) 공백이거나다음성질을만족 (1) 루트는최대 m 개의서브트리를가진다.
정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2
13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우
Microsoft Word - retail_131122.doc
Analyst 유주연 (639-4584) juyeon.yu@meritz.co.kr RA 박지은 (639-451) jeeeun.park@meritz.co.kr 213.11.22 유통업 Overweight 1월 매출동향: 대형마트 -6.4%, 백화점 -2.2% Top Pick 하이마트 (7184) Buy, TP 15,원 현대홈쇼핑 (575) Buy, TP 21,원
Microsoft PowerPoint - 6장 탐색.pptx
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential
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
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 를가리키도록변경
08년요람001~016
Challenge to the Greatness, Beautiful Leader 2008 2009 06 07 JANUARY 01 JUNE 06 FEBRUARY MARCH 02 03 JULY AUGUST 07 08 APRIL MAY 04 05 SEPTEMBER OCTOBER 09 10 2008 schooling schedule 08 09 2008 schooling
µðÇÃÇ¥Áö±¤°í´Ü¸é
2013. JAN. FEB. VOL.23 2013. JAN. FEB. VOL.23 Review Preview Company Technical Point Focus Issue Market Trend Industrial Trend Policy Report KDIA News Tour Statistics KDIA 02 10 11 12 15 16 22 28 36 38
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
µðÇÃÇ¥Áö±¤°í´Ü¸é
Review 2 2013 JAN.FEB. vol. 23 Display Focus 3 Review 4 2013 JAN.FEB. vol. 23 Display Focus 5 Review 6 2013 JAN.FEB. vol. 23 Display Focus 7 Review 8 2013 JAN.FEB. vol. 23 Display Focus 9 Preview 2013.1
슬라이드 1
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드
April. 28, 216 Fixed Income Analyst 2 3 2. 1.5 (%) (%).1.5. (%) (%) 1. 1 y 2 y 3 y 4 y 5 y 7 y 1 1 1 2 -.5 2.5 2.2 (%) 1y 3y 5y 1y (%) 1.9 1.6 1.3 1. '15Y.8 '15Y.12 '16Y.4 (%) (%) () Apr. 28, 216
2013........10
06 07 04 13 14 18 22 26 28 32 36 40 44 72 86 87 88 48 80 82 90 GongGam Human Rights Law Foundation 02+03 인사글 하늘은 욕망 없는 생명을 만들지 아니하고 대지는 이름 없는 풀을 키우지 아니한다. (天不 세월과 권력과 부침에 흔들리지 않고 한국 사회에 뿌리 깊이 내린 한 그루 나무가
1장. 리스트
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential
7장
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트
지속가능경영보고서도큐_전체
C o n t e n t s 03 06 07 10 30 38 43 55 56 60 62 70 71 Korea Foundation for Women Annual Report 2010 SLOGAN VISION 2 3 MISSION 1 MISSION 3 MISSION 2 4 5 Korea Foundation for Women Annual Report 2010 Korea
PowerPoint 프레젠테이션
13 장. 균형탐색트리 균형탐색트리 트리의작업효율을높이기위한다양한균형트리알고리즘을비교 학습목표 트리의균형이효율에미치는영향을이해한다. AVL 트리에서균형을회복하기위한방법을이해한다. 스플레이기법을이해한다. 2-3 트리에서균형을회복하기위한방법을이해한다. 2-3-4 트리와레드블랙트리의관계를이해한다. 1 균형 균형 2 AVL G. M. Adelson-Velskii and
목 차
목 차 1. 제품동향 Production < Demand and Supply of GI > Domestic Sales (Unit:10 3 ton) Inventory Import Export Apr 247.0 161.9 162.4 30.3 57.3 May 255.9 183.1 139.5 28.3 51.1 Jun 236.8 164.5 132.7 21.0 53.7
¿ì¾ç-ÃÖÁ¾
Website : www.wooyang.org Email : wy-welcome@hanmail.net 우양홈페이지www.wooyang.org를 방문하셔서 더 다양한 내용에 관심 가져 주세요. 혹은 QR코드를 스캔해주세요. 2010 우양재단 사업보고서 닮고 싶은 청년 우양의 즐거운 섬김 발행일 2011년 5월 발행처 우양재단 발행인 정의승 주소 서울시 마포구
Jan. 27, 216 Fixed Income Analyst 1,,,, BOK 216-2, : Pass-Through of Imported Input Prices to Deomestic Producer Prices: Evidence from Sector- Level Data 2 215-53, 2p, : Alexander Chudik and Janet
, Analyst, , Figure 1 통신사가입자추이 ( 명, 000) 60,000 LG U+ KT SKT 50,000 40,000 30,000 20,000 10,000 0 자료 : MSIP. 미래에셋증권리서치센터
Earnings preview, Target price lowered Korea / Telecommunication&Utilities 7 July 2016 OVERWEIGHT Stocks under coverage Company Rating Price Target price Target price change Previous New, Analyst 3774
PowerPoint 프레젠테이션
균형탐색트리 13 장. 균형탐색트리 트리의작업효율을높이기위한다양한균형트리알고리즘을비교 학습목표 트리의균형이효율에미치는영향을이해한다. AVL 트리에서균형을회복하기위한방법을이해한다. 스플레이기법을이해한다. 2-3 트리에서균형을회복하기위한방법을이해한다. 2-3-4 트리와레드블랙트리의관계를이해한다. 1 Section 01 AVL 트리 - 균형 균형 2 AVL G.
1장. 리스트
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 05. AVL 트리 06. B- 트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리,
歯111
2003. 3 4 1 Co n t e n t s 02 05 08 12 14 16 18 22 26 2 8 3 1 33 36 4 0 4 2 44 2003. 3 4 2 3 4 5 6 7 8 9 10 11 12 13 14 15 b o d y? 16 17 b o d y? 18 19 20 21 22 P h i l i p p i n e s 23 24 25 26 27 28
Microsoft PowerPoint - chap10_tree
Chap. 10 : Tree 2007 학년도 2 학기 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-
Microsoft PowerPoint - 26.pptx
이산수학 () 관계와그특성 (Relations and Its Properties) 2011년봄학기 강원대학교컴퓨터과학전공문양세 Binary Relations ( 이진관계 ) Let A, B be any two sets. A binary relation R from A to B, written R:A B, is a subset of A B. (A 에서 B 로의이진관계
State of Play - Video Insights Report_Korean_v2.key
,,, 2016 7 ,,,..,,,.,. TV,. Google 2014 4 2015 4 DBM(DoubleClick Bid Manager) DFP(DoubleClick for Publishers). 2 ,,,. Ad Age 100 85% DBM(DoubleClick Bid Manager). 2015 DFP(DoubleClick for Publishers) TV
2 247, Dec.07, 2007
247, Dec.07, 2007 2 247, Dec.07, 2007 3 247, Dec.07, 2007 4 247, Dec.07, 2007 5 247, Dec.07, 2007 6 247, Dec.07, 2007 7 247, Dec.07, 2007 8 247, Dec.07, 2007 9 247, Dec.07, 2007 USD 980 EUR 1,400 970 USD
슬라이드 1
2012 월간계획표 2012.01 January memo 1 2 3 4 5 6 7 8 9 10 11 12 13 D-300 14 15 16 17 18 19 20 21 22 23 설날 1.1 24 25 26 27 28 29 30 31 January 12.26~01.01 12.29 12.26 12.30 12.27 12.31 12.28 01.01 January 01.02~01.08
슬라이드 1
CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터
Microsoft PowerPoint - lec07_tree [호환 모드]
![Microsoft PowerPoint - lec07_tree [호환 모드]](/thumbs/82/84829941.jpg "Microsoft PowerPoint - lec07_tree [호환 모드]")
Tree 2008학년도 2학기 kkman@sangji.ac.krac kr -1- 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 -2- 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조. ~ 정렬된배열 탐색은빠르지만
슬라이드 1
Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음
Microsoft PowerPoint - 제8장-트리.pptx
제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,
제 9 장 우선순위 큐
제 9 장 우선순위큐 Copyright 007 DBLAB, Seoul National University 한쪽끝과양쪽끝우선순위큐 우선순위큐 (priority queue) - 각원소가연관된우선순위를갖고있는원소들의모임 최소우선순위큐에서의연산 - SP: 최소우선순위를가진원소의반환 - SP: 임의의우선순위를가진원소의삽입 - SP3: 최소우선순위를가진원소의삭제 최대우선순위큐에서의연산
Microsoft Word - IO_2009_메모리반도체.doc
메모리 반도체 SemiconductorMemory Chips 2009.1 평가1실 조수희 애널리스트 7872321 suhee.cho@kisrating.com 평가1실 박춘성 연구위원 7872341 cspark@kisrating.com 평가1실 손재형 실장 7872250 jaihyoung.son@kisrating.com Summary 공급과잉 상태가 지속되는
슬라이드 1
6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,
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
¼Ł¿ï¸ðµåÃÖÁ¾
Fashion Fashion Blue ocean Passion Chance Contents Blue ocean Fashion Passion Contents Chance Fashion Blue ocean Blue ocean 003 Blue ocean 004 Fashion Blue ocean 005 Blue ocean http://blog.naver.com/klcblog?redirect=log&logno=90041062323
당신이 꿈꾸던 채널, CONTENTS 채널파워 데이터로 살펴보는 Buying Point 특별분석 : 빅데이터로 분석한 당신이 몰랐던 당신이 꿈꾸던 채널, - 채널파워 - 데이터로 살펴보는 Buying Point - 특별분석 : 빅데이터로 분석한 당신이 몰랐던 02 06
당신이 꿈꾸던 채널 당신이 꿈꾸던 채널, CONTENTS 채널파워 데이터로 살펴보는 Buying Point 특별분석 : 빅데이터로 분석한 당신이 몰랐던 당신이 꿈꾸던 채널, - 채널파워 - 데이터로 살펴보는 Buying Point - 특별분석 : 빅데이터로 분석한 당신이 몰랐던 02 06 당신의 브랜드 가치를 올려줄 프로그램 - 유아/주부타깃 최고 광고효과,
.......... ...... 28.. ....
Industrial Trend Industrial Trend > Part. Set (2013.10.30) 24 2013 NOV DEC. vol. 28 (2013.11.05) (2013.11.15) Display Focus 25 Industrial Trend (2013.11.22) 26 2013 NOV DEC. vol. 28 (2013.11.28) (2013.11.25)
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
05_tree
Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical
v 이원탐색트리 (binary search tree) u 인덱스를조직하는한가지방법 u 이진트리 (binary tree) 유한한수의노드를가진트리 공백 (empty) 이거나루트와두개의분리된이진트리즉, 왼쪽서브트리 (left subtree) 와오른쪽서브트리 (right su
6장인덱스구조 v 인덱스 (index) u 특징 화일의레코드들에대한효율적접근을위한조직 < 키값, 레코드주소 ( 포인터 )> 쌍으로구성 u 종류 키값의유형에따른인덱스 기본인덱스 (primary index) : 키값이기본키인인덱스 보조인덱스 (secondary index) : 기본인덱스이외의인덱스 화일조직에따른인덱스 집중인덱스 (clustered index) :
레이아웃 1
대한위장관기질종양연구회 01 GIST 06 02 11 03 Imatinib 14 04 05 06 07 Sunitinib 32 40 44 48 GIST 6 01 7 GIST Guide book GIST 8 01 9 GIST Guide book GIST (CT) MRI FDG-PET 10 02 11 GIST Guide book 12 02 (Imatinib)
Ch.1 Introduction
Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2 트리자료구조를사용하는이유?
????좔??
WhitebookVol.2 KUSSO 2010 KU Social Service Organization 2 CONTENTS 1 2008.12.23~2009.11.30 2,768 22,509 2 2009.12.01~2010.11.30 3,011 67,002 Total 5,779 89,511 2, (2010 11 30) () 2010.01.10-01.17 21 64
Microsoft Word - 20150811201049900_1
Company Report 215.8.12 CJ E&M (1396) 기대보다 좋았고 앞으로도 좋을 듯 미디어/엔터 What s new? Our view 투자의견: BUY (M) 목표주가: 12,원 (M) 주가 (8/11) 81,5원 자본금 시가총액 1,937억원 31,567억원 주당순자산 42,468원 부채비율 49.26% 총발행주식수 6일 평균 거래대금 38,732,89주
untitled
World Report 2010 Inside K-sure Biz and Life 2010 11.12 164 World Report 2010 06 12 18 22 26 Inside K-sure 28 34 40 46 50 58 62 Biz and Life 64 66 Global Standard 68 70 Green Economy 72 Rival Game 74
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 으로분할
Microsoft Word - 20160318180453480_6
Sector Report 2016.03.23 인터넷 인터넷/게임 기업 1분기 실적 및 주가 전망 인터넷 (OVERWEIGHT) What s new? Our view 종목 투자의견 목표주가 (원) NAVER BUY (M) 800,000 (M) 카카오 BUY (M) 140,000 (M) 엔씨소프트 BUY (M) 320,000 (U) 컴투스 BUY (M) 180,000
목차 ⅰ ⅲ ⅳ Abstract v Ⅰ Ⅱ Ⅲ i
11-1480523-000748-01 배경지역 ( 백령도 ) 에서의 대기오염물질특성연구 (Ⅲ) 기후대기연구부대기환경연구과,,,,,,, Ⅲ 2010 목차 ⅰ ⅲ ⅳ Abstract v Ⅰ Ⅱ Ⅲ i 목차 Ⅳ ii 목차 iii 목차 iv 목차 μg m3 μg m3 v 목차 vi Ⅰ. 서론 Ⅰ μm μg m3 1 Ⅰ. 서론 μg m3 μg m3 μg m3 μm 2
¹é¼Ł sm0229-1
2006 SK Community Relations White Book 2006 SK Community Relations White Book 2006 SK Community Relations White Book CONTENTS 004 CEO 인사말 006 발간사 008 1부 SK 행복 다이어리 010 SK 행복 다이어리 034 더 큰 행복 을 만들어가는 SK
08장.트리
---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조
*논총기획(1~160)
n i j z ij z ij Y i X i i a ij j i a ij =z ij /X j j i i j z ij W j X j j r ij j i X e H I-A e -1 H A e H A H H X H H e V e H A e v m i M i X i m i =M i / X i X R e H H H I-R e -1 H H mi-a -1 m H M e m
Chapter 08. 트리(Tree)
윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예
입학사정관제도
자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1 8 장트리 소프트웨어학과원성현교수 93 1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy)
슬라이드 1
CHAP 7: 트리 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 회사의조직 파일디렉토리구조 결정트리 ( 예 ) 골프에대한결정트리 트리의용어 노드 (node): 트리의구성요소
IR컬럼 착시현상 때문이라고 할 수 있다. KOSPI 지수의 변화 율이나 KOSPI 지수 대비 상대적인 변동폭으로 측정한 최근 우리나라 주식시장의 주가변동성은 1980년 이후 최저 수준에 근접한 정도로 낮아졌다. 우리나라 주가변동성, 글로벌 시장보다 빠르 게 감소 19
2016. 2 통권 제185호 발행일 : 2016년 2월 1일 / 발행인 : 이호철 / 편집인 : 강홍기 / 발행처 : 한국IR협의회 / TEL 02-6922-5000 / 제작처 : 한아름인쇄 ⅠContentsⅠ IR컬럼 01 _ IR컬럼 변동성 컸던 한국 주식시장, 저위험 저수익 시장으로 03 _ CEO인터뷰 변동성 컸던 한국 주식시장, 저위험 저수익 시장으로
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
Microsoft Word - 091202_김형준_동부책략_final.doc
東 部 策 略 일본 동부책략 2009년 12월 2일 케리트레이드에 불을 지핀 일본의 新 양적완화 정책 일본은행이 국채, 회사채, CP등을 담보로 134조원의 자금을 공급하는 新 양적완화 정 책을 발표했다. 이는 주식시장에 긍정적인 작용과 함께 KRW/USD가 1,150원 아래로 하락하는 모멘텀으로 작용할 수 있는 요소이다. 따라서, 위험선호 현상 강화와 KRW/USD
쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table
쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table http://academy.hanb.co.kr 6장. 해시테이블 테이블 Hash Table 사실을많이아는것보다는이론적틀이중요하고, 기억력보다는생각하는법이더중요하다. - 제임스왓슨 - 2 - 학습목표 해시테이블의발생동기를이해한다. 해시테이블의원리를이해한다. 해시함수설계원리를이해한다. 충돌해결방법들과이들의장단점을이해한다.
쉽게 배우는 알고리즘 강의노트
쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고,
슬라이드 1
CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템
#111-131 ¸®´õ½ÊÆ÷Ä¿½º_07-2
CHURCH GROWTH CHURCH GROWTH CHURCH GROWTH CHURCH GROWTH CHURCH GROWTH CHURCH GROWTH CHURCH GROWTH CHURCH GROWTH 112 118 122 127 132 June 2012 113 114 July 2012 July 2012 115 116 July 2012 July 2012 117
슬라이드 1
CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)
제 1 장 기본 개념
이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)
歯데일리20011106.PDF
/ CJ VON IT IT - - YBM B&F IT S/W & SVC IT H/W - EG YNK - IT CBF TG WB - - - TPC KTF LG - - - IT- - CJ39 LG ENG SBS YTN SCN IT-S/W & SVC- IT-S/W & SVC- - ILI IT-S/W & SVC- 3SOFT - - - - IT- - IT-S/W&SVC-
FUTURES MARKET OUTLOOK&STRATEGY SAMSUNG FUTURES MONTHLY No. 15 / 216. 6. 29 7 브렉시트, 긴호흡으로접근하기 1 2 3 4 5 6 7 8 9 1 11 12 1 14 15 16 17 18 19 2 21 23 15 /() () 125 12 12 99 6 96 93 9 15Y.11 15Y.12 16Y.2
Microsoft Word - 20121030140354943_0.doc
Sector Report 212.11.14 통신서비스 213년 통신 전망: LTE의 결실을 수확하는 해 통신/휴대폰 Analyst 최남곤 2-377-3549 Research Associate 김 솔 2-377-3496 213년의 화두는 LTE의 수익화, 뉴미디어의 확장 지속 등으로 전망됩니다. 상대적으로 비중을 늘려야 할 종목은 LTE에서 좋은 성과를 보이고
쉽게배우는알고리즘 5 장. 검색트리 IT COOKBOOK 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 한빛미디어 1
쉽게배우는알고리즘 5 장. 검색트리 htt://academy.hanb.co.k 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 - 2 - 한빛미디어 1 학습목표 검색에서레코드와키의역할을구분한다. 이진검색트리에서의검색 삽입 삭제작업의원리를이해한다. 이진검색트리의균형이작업의효율성에미치는영향을이해하고, 레드블랙트리의삽입
원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를
리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은
Microsoft Word - KIS_Touchscreen_5Apr11_K_2.doc
산업분석 Report / 터치스크린 211. 4. 5 비중확대(신규) 종목 투자의견 목표주가(원) 멜파스(9664) 매수(-) 67,( ) 일진디스플레이(276) 매수(신규) 14,5(-) 에스맥(9778) 매수(신규) 18,(-) 이엘케이(9419) 매수(-) 27,( ) 삼성전자 태블릿 PC 공급업체에 주목 터치스크린 산업 올해 9% YoY 성장 비중확대
OCW_C언어 기초
초보프로그래머를위한 C 언어기초 4 장 : 연산자 2012 년 이은주 학습목표 수식의개념과연산자및피연산자에대한학습 C 의알아보기 연산자의우선순위와결합방향에대하여알아보기 2 목차 연산자의기본개념 수식 연산자와피연산자 산술연산자 / 증감연산자 관계연산자 / 논리연산자 비트연산자 / 대입연산자연산자의우선순위와결합방향 조건연산자 / 형변환연산자 연산자의우선순위 연산자의결합방향
슬라이드 1
CHAP 7: 트리 yicho@gachon.ac.kr 1 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 2 2 회사의조직 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산
北 韓 및 共 産 圈 接 觸 交 流 를 通 한 政 治 心 理 의 展 關 方 向 國 土 統 - 綜 이 報 告 書 는 國 土 統 一 院 73 年 度 下 半 類 學 術 f 役 에 關 한 畢. 終 報 告 書 로 理 出 합니다 l 9 7 3 년 il원 긴 硏 究 機 關 京 鄕 諒 間 社 安 保 統 - 硏 究 委 員 會 硏 漆 養 員 責 任 者 : 료 國 植 委 員
완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에
1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에대하여 AB=BA 1 가성립한다 2 3 (4) 이면 1 곱셈공식및변형공식성립 ± ± ( 복호동순 ), 2 지수법칙성립 (은자연수 ) < 거짓인명제 >
3542 KS Figure 1 원/엔 환율 추이 Figure 2 라인 2Q ~ 3Q15 매출 breakdown (KRW/JPY) 13 12 12 (KRW bn) 3 25 Total: 229 Total: 254 11 FX 11 11 1 1 2 15 1 84 91 (+9%
Company update Korea / Internet & Game 9 September 215 BUY 목표주가 현재주가 (8 Sep 215) 72, 원 461,5 원 Upside/downside (%) 51.7 KOSPI 1,883.22 시가총액 (십억원) 15,641 52 주 최저/최고 466, - 834, 일평균거래대금 (십억원) 73.18 외국인 지분율
11장 포인터
Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함
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
歯자료
To Shareholders & Investors KTF 21 Contents 1 KTF+KTM ( : ) FY21 FY2 (%) I. 789,14 142,62 453.4% 1. PCS 3,986,78 3,271,77 21.8% PCS 2,91,193 2,349,386 23.5% 941,6 873,57 7.8% 111,665 29,191 282.5% 31,62
FUTURES MARKET OUTLOOK&STRATEGY SAMSUNG FUTURES MONTHLY No. 153 / 216. 9. 28 1 재정으로가는길 1 2 3 4 5 ? 6 7 8 9 12 13 14 15 16 17 18 19 2 21 22 23 25 /() () 15 125 12 121 99 117 96 113 93 19 9 15 (%) 16Y.2
Microsoft PowerPoint Relations.pptx
이산수학 () 관계와그특성 (Relations and Its Properties) 2010년봄학기강원대학교컴퓨터과학전공문양세 Binary Relations ( 이진관계 ) Let A, B be any two sets. A binary relation R from A to B, written R:A B, is a subset of A B. (A 에서 B 로의이진관계
Microsoft PowerPoint - 자료구조2008Chap07
제 7 장트리 7.1 트리의정의 1 Tree 비선형구조, 다차원적구조 원소마다다음에여러개의원소가존재 하나이상의노드로구성된유한집합 정의1 : 루트 (root) 라는특별한노드를가지는사이클이존재치않는그래프 (acyclic graph) 정의 2 : 하나이상의노드로구성된유한집합 루트 (root) 라는특별한노드존재 나머지노드들은다시각각의트리이면서교차하지않는분리집합 (disjoint
1 (Page 3)
2008 SEP OCT DRB Magazine 2008 SEP OCT DRB Magazine Contents September / October 2008 4 DRB DO YOUR BEST 5 6 DRB DO YOUR BEST 7 8 DRB 1 2 3 4 5 6 7 8 DO YOUR BEST 9 10 DRB DO YOUR BEST 11 12 DRB DO YOUR
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. 부-노드,
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 관계성립
이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2
제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.
Microsoft PowerPoint Index Structures.ppt
자료처리 () 26 년봄학기문양세강원대학교컴퓨터과학과 강의 강의내용 Binary Trees (Ch. 6 in 화일구조 ) B-tree, B*-tree, Trie (Ch. 6 in 화일구조 ) B + -tree (Ch. 7 in 화일구조 ) Indexed Sequential File (Ch. 7 in 화일구조 ) Page 2 색인, 인덱스 (Index) 특징
(Hyunoo Shim) 1 / 24 (Discrete-time Markov Chain) * 그림 이산시간이다연쇄 (chain) 이다왜 Markov? (See below) ➀ 이산시간연쇄 (Discrete-time chain): : Y Y 의상태공간 = {0, 1, 2,..., n} Y n Y 의 n 시점상태 {Y n = j} Y 가 n 시점에상태 j 에있는사건
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
Daewoo Daily (YoY,%) 40 30 20 10 0-10 -20 IT IT -30-40 99 00 01 02 03 04 05 WTI WTI Compliance Notice GLOBAL BATTERY (3,350, 3,450, 3,275, 3,440, +150) ne July August September October November December
자연채무에대한재검토 1. 서론 2. 선행연구 9 Journal of Digital Convergence 214 May; 12(5): 89-99
종합주가지수 서울지역아파트가격 전국주택매매가격지수 경기선행지수의상관관계와선행성분석 최정일 *, 이옥동 성결대학교경영대학 *, 성결대학교부동산학과 ** ** 요약주식시장에서종합주가지수를부동산시장에서서울지역아파트가격과전국주택매매가격지수를선정하여경기 선행지수와함께각지표들사이의상관관계를찾아보았다 또한각지표들사이의흐름을서로비교하여선행성이 성립되는지도살펴보았다본연구의목적은종합주가지수와서울지역아파트가격전국주택매매가격경기선행지수의
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,
책임연구기관
2009. 2. 책임연구기관 - i - - ii - - iii - - iv - 6.3.1 Sample Collection and Analysis 161 6.3.1.1 Sample Collection 161 6.3.1.2 Sample Analysis 161 6.3.2 Results 162 6.3.2.1 Dalian 162 6.3.2.2 Xiamen 163 6.3.3
Microsoft Word - 2014Outlook_증권업_editing_final_f.docx
1 Outlook 1 증권 산업전망 Overweight 증권/은행/지주 1. 11. 7 Analyst 박선호 -9-7 Sunho.park@meritz.co.kr RA 은경완 -9-97 Kyungwan.eun@meritz.co.kr Top Pick 대우증권() Buy, TP 1,원 투자포인트 I. 수익구조 개선 당위성 증대: 이제는 생존의 문제이다 1. 문제의
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 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조.