[point]

해당 노드에서 직접 바라보는 부모노드와의 거리보다 다른 연결로 들어온 경로의 거리가 더 적다면

적은 거리로 온 노드를 부모로 바라본다

시작 A

모든 노드는 A 를 가르키고 (parent)

직접 가르키지 못하는 노드들은 무한대로 거리를 설정한다

1.A 를 처음 방문하고 방문하지 않은 최소 비용으로 연결된 노드에 대해서 탐색을 시작한다

2. 그래서 처음 C 를 방문하게 된다

(노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 )

3. C 를 살펴보면 C 는 D 와 연결 되어 있고 D 는 A 를 가르키고 있다

그런데 A에서 C 그리고 C 에서 D 로 가는 비용이 3 이고 A 에서 D 로 가는 비용이 2 총 3 이기 때문에

D 가 더 빨라 D 가 가르키는 부모와 distance를 바꾸지 않아도 된다

[반복..] 인접한 것과 방문은 다른 것

4. 노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 (D)

5. D 와 인접한 G 와 F 노드가 있는데

먼저 F 를 보면 F의 비용은 무한대 이기 때문에 D 에서 F 로 누적된 6 만큼 이동 하는 것이 더 빠르기 때문에

(F A 무한대) 를 (F D 6) 으로 바꿔준다

G 도 무한대 비용인데, D 에서 G 로 가는 누적된 6 이 더 작음으로

(G A 6) 을 ( G D 6 ) 으로 바꿔준다 (이렇게 parent 를 세팅해나간다)

6. 다시 노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 이번에는 (E) 가 선택 된다

반복...

결과

최종적으로 Vertex 가 바라보는 Parent 로 연결되는 선을 연결해주면 위 그림처럼 나오고

최단 경로는 시작점 A 에서부터 모든 점에 대한 최단 거리를 연결해 놓은 형태가 됨으로

A 가 아닌 어떤 노드에서 부모를 따라 가면 어떤노드에서 A 까지 가는 최단 경로가 나온다

Find - 어떤 원소가 어떤 집합에 포함되는지 아닌지를 판별

Union - 서로 다른 두개의 집합을 하나의 집합으로 합병

=> 상향식 트리구조로 구현 하는 것이 효율적이다

상향식트리구조 : 위에서 아래로 내려오는 구조가 아닌 아래에서 위로 올라가는 구조

일반적으로 알고 있는 하향식 트리구조는 부모가 자식들만큼의 포인터 개수를 가지고 있어야 하지만

상향식은 자식이 부모를 가르키는 구조이므로 각 노드는 하나의 포인터만 가지고 있으면 된다

그러므로 어느 집합에 포함된 노드의 parent 를 계속 따라가다보면 최종 root 인 어느 집합인지를 알 수 있게 된다

(각 root 집합 명)

MCST [Minimum Cost Spanning Tree]

신장트리(Spanning Tree) : 모든 정점(노드)을 방문하는 트리

트리 : 사이클이 없는 그래프를 말한다

그런데 간선에 비용이 있다 => 모든 정점을 방문하면서도 간선의 비용의 합이 최소인 트리를 신장트리라 한다

MCST = Minimum cost spanning tree

최소비용 신장트리로 알려진 알고리즘 들에는

1. 우선순위 탐색

2. Kruskal

3. Sollin

4. Prim

etc...

[1,2 가 성능이 좋다]

최소비용신장트리 - 우순순위 검색 에 의한 방법

( PrioityQueue 가 필요 ( PrioityQueue 는 힙으로 만든 것이 적절하다 Heap 은 O(logN)의 성능을 갖는다) )

* 비용을 우선순위로 둔다

모든 노드를 연결하는데 가장 최소의 비용으로 모든 노드를 연결하는 방법

간선 자체를 우선순위로 보고 비교한다

[C++ 알고리즘 참고]

[최단경로찾기 ]

A 부터 Z 까지 가는 길 중에 각 길마다 비용이 있고 가장 적은 비용으로 Z 까지 가는 비용을 얻기 위한 방법

* 누적으로 최단 경로를 구한다

먼저

출발점이 A 라면 A 와 인접한 것들을 우선순위 큐에 넣고 ( 이때 우선순위 큐에는 가작 작은 값이 최 상단에 위치하게 한다)

p 큐 가장 위에 있는 것을 뽑아와서 선을 연결 한다

뽑아온 노드의 인접 노드를 다시 p큐에 넣는다

이때!! 큐에 넣기전 현재 도착 노드가 p큐에 있는지 보고 p큐에 도착 노드가 있다면 이제까지 누적해온 경로의 길이를

비교해봐서 p큐보다 값이 작다면 기존 p큐에 있는 노드를 지우고 누적값이 적은 노드값으로 대체한다

- 최소 비용으로 모든 정점을 연결하는 방법

insert : 삽입을 하는 동작에서만의 시간

remove : 삭제를 하는 동작에서만의 시간

O(1) = 상수시간

[ArraySequenceMap] = 배열 => 검색이 O(N) 이 걸리는 이유는 첫번째 부터 찾을때까지 각 배열에 대해 맞는 것을 찾으려니 선형적으로 걸린다

[ListSequenceMap] = 리스트

BinMap(Binary) =이분검색

=> 트리를 이용하지 않는다!!!

=> 자료집합은 정렬 되어 있어야 한다, 정렬이 되어 있는 상태에서만 작동 가능

=> 삽입될때 만약 배열에 자료들에 배열에 들어가 있는 상태라면 정렬된 상태를 유지하기 위해서 들어갈 이후의 값들이 모두 뒤로 이동 되어야 한다

itpMap(interpolation) = 비례식에 의한 찾기 방식으로 검색은 자료가 선형적으로 있을때 빠른 속도를 보인다 , 수치자료에서만 사용 가능

하지만 O(loglogN) 삽입삭제는 역시 느리다

BinTreeMap(바이너리트리맵)

=> 이진 트리를 이용한 검색방법이다

=> 균형이 맞으면 O(logN) 의 성능을 보이지만 삽입시 균형이 맞지 않으면 한쪽으로 치우치는 최악인 경우 O(N) 의 성능을 보인다

=> chain 은 중복처리를 리스트에서 하기 때문에 저장공간이 자료수보다 큰 필요는 없다

[HashMap,ChainMap 은 상수 시간에 찾기 삽입, 지우기가 끝난다]

=> 관건은 해쉬 펑션을 어떻게 정의 하느냐 이고, 보통 Hash 는 입력 자료수의 2배 만큼의 공간으로 잡을때 성능이 좋다

HashMap(정적인 상황에 적합)

ChainMap (연결 법) => 해쉬 테이블에 이중리스트로 연결하여 데이터를 추가( 동적인 상황에 적합) , 최신 데이터를 리스트의 앞에 넣어줌으로서

노드의 뒤쪽으로 이동하는 시간을 줄일 수 있다

(=>chainmap 은 중복된 값을 리스트에 넣는 것이므로 값을 최근 헤드에 연결된 것을 리턴해 주면 됨으로 검색도 상수시간이다)

[radix tree,radix trie 둘다 자료가 비트로 표현될 수 있어야 한다]

이진트리에서의 한쪽으로 치우치는 현상을 방지된 구조가 된다 => 비트에 의해 좌,우가 결정 됨으로

그래서 검색,삽입,삭제 가 O(logN) 의 성능을 보인다

Radix Tree => 모든 노드가 정보노드

Radix Trie => 정보노드는 leaf 에, 내부(중간)노드는 분기노드

[B-Tree : 하나의 노드에 여러개의 자료가 들어 갈 수 있으면서 균형을 맞추는 구조]

O(logN) 의 성능을 보인다

[RB-Tree : 벨런슬르 자동으로 맞춰주면서 이진트리 구조의 형태를 지닌다]

find 도 O(logN) 이며 insert ,remove 도 O(logN) 이지만 실제 다른 logN 의 성능을 가진 것보다 상당히 빠른 속도를 보인다

검색 : 이진트리 검색과 동일

삽입 : 칼라상향변환 + 회전

삭제 : 칼라하향변환 + 회전

으로 이루어진다

[모든 벨런스 트리는 기본적으로 중복이 불가능하다]

chain, 이나 hash 가 가장 빠르다

Red Black Tree 의 특징 : 2-3-4 트리를 Binary Tree 로 표현 한것

(2-3-4 트리는 3차 B-Tree 와 돌아가는 것이 동일하다)

먼저 2-3-4 트리를 알아야 하는데

노드의 자식이 2,3,4 개가 존재 할 수 있다고 하여 2-3-4 트리이다

A 를 가지고 있는 노드는 2개의 자식을 갖는다

A B 를 가지고 있는 노드는 3개의 자식을 갖는다

A B C 를 가지고 있는 노드는 4개의 자식을 갖는다

Red Black 트리는?

2-3-4 트리를 이진트리로 나타낸 것

그림에서 2노드 인 경우 A 를 검정색 A 노드로 표현

3노드 인 경우 B 를 빨강으로 내리거나 A 를 빨강으로 내려 표현

4노드의 경우 B 를 제외한 양쪽을 빨강으로 내려 표현

Red-Black 트리에서는 이렇게 자식으로 내리지만 2-3-4 트리에서는 하나의 노드로써 결합의 의미를 갖는다

2-3-4 트리를 보면 B-Tree 의 형태 임을 알 수 있다( 동작도 동일하다 )

즉 B-Tree 를 이진 트리 형태로 바꾼것!!!

이진트리와 동일하게 부모노드의 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다

Root 에서 Leaf 로 가는 경로의 검정노드의 수는 모두 같다 => B-Tree 에서 빨강이 자식으로 확장된 형태이므로

원래 B 트리는 모든 자식의 레벨이 같다, 그래서 확장된 빨강 노드를 제외하면 루트에서 자식까지 가는 검정노드의 수는 갖게 된다

색변환 (color flip)

상향 색변환 : 빨강을 위로 올림 => 검정색의 자식의 두개의 빨강 노드일경우 부모를 빨강으로 바꾸고 두 자식을 검정색으로 바꾸는 것

하향 색변환 : 위에 있는 빨강을 자식을 빨강으로 바꾸는 것 -> 부모는 검정이 된다 (상향 색변환과 반대)

회전 : 이진트리의 규칙을 깨지 않고 트리를 재구성 하는 방법(우회전, 좌회전) => 좌우의 트리 높이를 맞추는 방향으로 회전함=>AVL Tree 의 기본 동작

이렇게 분할 하는 이유는 자료를 삽입하기 위함 ( 트리의 균형을 깨지 않고 )

(노드안에 자료가 3개면 => 4노드)

위 그림이 상향식 변환 ( 위의 그림에서 녹색 부분이 B-Tree 의 설명 아래 있는 것이 RB-Tree )

루트는 원래 검정이라 빨간색으로 자식을 내리건 안내리건 간에 Root 는 검정색이된다

루트가 검정색

pivot 은 회전의 축이 된다

회전하면서 자식들의 위치는 이진트리의 부모의 왼쪽은 작고 오른쪽은 큰 순서를 유지하기 위한 순서대로 구성해준다

- 트리에서는 노트의 끝을 노드로 표현하지 않고 0 로 표현 할 수 있다

- RedBlack 을 표현하기 우해 bool red; 로 표현 한다

- RB 트리도 기본적으로 중복을 허용하지 않는다( list 등으로 노드에서 중복을 허용하는 구조로 만들 순 있다)

[RB-Tree 검색]

검색 알고리즘은 이진 트리와 동일하다( 키 값으로 비교하여 왼쪽, 또는 오른쪽으로 이동 )

[RB-Tree 삽입]

single rotation, double rotation 으로 이루어진다

구조는 이진트리와 동일하기 대문에 노드 순서 규칙은 동일

균형을 맞추기 위해 색변환 -> 노드 분할, 결합등을 하게 된다

=> 이때 빨간노드가 연속되는 상황이 벌어질 수 있는데 이때의 균형을 맞추기 위해 Rotation 을 한다

=> 자료를 삽입할때 부모가 빨간노드이면 Rotation 을 한번 한 후 삽입 한다

right rotation, left rotation => single rotation

right rotation 한다음 left rotation , left rotation 한다음 right rotation => double rotation

[Single rotation]

1. 상향색 조정을 했을때 빨간 노드가 연달아 나타나게 되는 상황이 발생되면

2. 회전을 하면서 노드의 색깔이 변경되고, 그럼으로서 노드의 균형을 맞춘다

회전시키기 위해선 t, p, gp(부모의 선조), ggp 의 4개가 있어야 한다

그림상 B-Tree 부분 에서(각 이미지의 아래에 그려진 트리) 노드안의 자료가 3개일때 분할하는 모습을 볼 수 있다(이것이 rotation 의 회전과 동일)

[double rotation]

left-right rotation 그림중에서 1번 을 보면 single rotation 에서와는 달리 두개 연달아 나오는 레드 노드 위로의 선이 반대인 것을 볼 수 있는데

이때는 두번 회전으로 노드를 정리해줘야 한다 => double rotation

1.상향 색조정을 아래에서 한번 하게 되면 레드 노드가 연달아 나오게 된다

2.Right-left rotation 에서 보면 C 를 pivot(중심)으로 해서 한번 회전 하면 선이 펴지게 된다 => 색변환 일어나지 않는다

3. 그다음 C 가 회전 되어진다 => single rotation 처럼 회전 => 색변환이 일어난다

[키값에 의한 회전]

왼쪽 상단 그림을 보면 G 를 키 값으로 주고 E 에서 G 쪽으로 향하는 방향으로 회전을 시켜주고

3번째 그림에서는 E 값을 키 값으로 놓고 E 에서 C 의 방향으로 회전을 하게 된다

pivot, child, gchild 는 아직 정해지지 않은 각 노드 포인터

*회전 호출시 pivot 을 정하고 넘겨준다

gchild 를 키값으로 하여 gchild 에서 child 의 방향으로 회전

회전의 방향 = 키값(노드안의 데이터)

회전의 위치 = pivot( pivot 의 왼쪽 또는 오른쪽 노드에 의해서 child 가 결정된다 )

child 와 키 값에 의해서 gchild 가 결정되면서 회전하게 된다

pivot 과 키값(gchild)의 비교에 의해서 child 가 가르킬 노드를 정해준다

child 와 gchild 의 위치관계를 pivot 과 키값에 의해 따져서 회전시켜준다

if (key > child->data || key == child->data)

Rotate left

else

rotate right

// key == child->data 일때도 오른쪽인 이유는 나중에 내부노드 삭제를 할때 루트보다 바로 큰 노드와 바꿔치기 하여 루트를 삭제 하기 위한

처리와 맞춰주기 위함 즉 삭제시 루트에서 오른쪽으로 한번간 후 왼쪽으로 계속가서 루트보다 바로 큰 노드를 찾기 위한 오른쪽 탐색을

하는 처리와 맞춰주기 위함이다

끝난 후 변견된 트리의 pivot 의 자식을 설정해 주어야 하는데

gchild 가 상단으로 올라감으로 gchild 를 pivot 의 자식으로 주어야 한다

그런데 왼쪽으로 줄것인지 오른쪽으로 줄것인지를 결정하기 위하여

key 와 pivot->data 의 비교로 위치를 결정한다

[insert ]

삽입시 자식노드 둘다 레드이면 칼라상향조정

칼라 조정후 부모가 레드면 회전

회전하려고 할때 노드 연결이 단방향이 아니고 꺽여 있으다면 double rotation

t,p,gp,ggp 의 관계를 살펴본다

if( p->red ){

if( value > gp-data != value > p->data )

rotation(value, gp);

t= rotation(value,ggp);

t->Red=true;

}

마지막 하단에 노드를 삽입할때도 그때의 부모가 레드면 로테이션( or double rotation) 후 삽입

회전이 다 된후 노드가 맞는 위치에 삽입된다

그래서 좌우 트리가 두배 이하로 유지가 된다

[delete]

C++ 알고리즘 참고

delete 에서 color demotion 이 나온다, 왜냐하면 삭제시 노드가 아에 없어지면 자식을 갖지 못하는 상화이 벌어 질 수 있으므로

쉽게 위해 하기 위해서는 B-Tree 로 전 후를 만들어 본 다음 만든 트리를 Red-Black 트리로 변행해 본다음

바뀐것들으 알아보는 것

[Red-Black 트리 분석]

트리의 높이

black height => black 노드로 이루어진 레벨의 개수

둘다 black 노드의 높이는 2 이다 , black height

black height 는 2 인데 개수는 왼쪽이 3개, 오른쪽이 15개

N+1 = 노드개수(3)+1 은

s^B <= N+1 <= 4^B (B = black height)

왼쪽은 H(Height) = B(Black Height) = 2

오른쪽은 H(Height) = 2B(Black height) = 4

O(logN) 의 성능을 보인다 => 성능이 좋다

Balanced Tree : 스스로 균형을 유지하는 트리

A 를 찾기 위해서 균형이 안맞으면 느릴 수 있다

균형이 안맞으면 링크드 리스트처럼 검색성능을 보인다

위 그림은 트리를 회전함으로써 이진트리의 규칙을 유지하면서 트리의 높이를 낮추는 방법을 보여준다

RB Tree & B Tree 의 방법에 AVL Tree 가 포함된다

하나의 노드에 여러개의 노드가 들어올 수 있다

M 차 => 한 노드에 자료가 가장 많이 들어간 수의 차수를 말한다

이 그림에서 M = 5차 > v,w,x,y,z

B - Tree 규칙.1

1. 노드의 자료수가 N 이라면 , 그 노드의 자식의 수는 N+1 이어야 한다 => left, right 가 있어야 하므로

자료수 = (노드 안에 있는 자료의 개수)

2. 각 노드의 자료는 정렬된 상태여야 한다 --> 방향으로

3. 노드의 자료 D_k 의 왼쪽 서브트리는 D_k 보다 작은 값들이고

D_k 의 오른쪽 서브트리는 D_k 보다 큰 값들이어야한다

( 이진트리에서 부모보다 왼쪽은 작은 트리, 오른쪽은 부모보다 큰 트리를 말한다 )

ex) 그림에서 C의 왼쪽은 C 보다 작은 A,B 이고, D,E 는 C 보다는 큰지만 F 보다는 작은 자료이다

B - Tree 규칙.2

1. Root 노도는 적어도 2개 이상의 자식을 가져야 한다.

2. Root 노드를 제외한 모든 노드는 적어도 floor(M/2) [<= 내림] 개의 자료를 가지고 있어야 한다.

( 위 그림에서는 노드들이 모두 적어도 2개 이상의 자료를 가지고 있다

3. 외부 노드(leaf node) 로 가는 경로의 길이는 모두 같다

4. 입력자료는 중복될 수 없다.( list 등을 같이 쓰면 중복을 허용 할 수도 있다 )

B-Tree 구조

시작을 나타내는 노드가 있는데 헤드에 대한 포인트 노드만 사용하고 끝은 0 로 처리 해서 만든다

끝을 NULL 로 처리 하는 것이 가능

[노드 안의 글자가 '키' 를 의미한다]

B-Tree 검색

루트에서부터 노드의 자료들과 찾을 값을 비교하여 노드가 찾을 것보다 작으면 왼쪽 크면 오른쪽으로 이동하면서 찾아간다

-노드내에서는 순차검색, 전체적으로는 트리검색

B-Tree 삽입

1.자료는 항상 leaf 노드에 추가된다 (leaf 노드의 선택은 삽입될 키의 하향 탐색에 의해 결정)

2. 추가될 leaf 노드에 여유가 있다면 그냥 삽입

3. 추가될 leaf 노드에 여유가 없다면 '분할' 하기

4. 삽입할 때 같은 키 값이 있으면 안됨으로 해당 노드에 삽입하기 전에 같은 값이 있는지 find 해봐야 한다

[루트노드 분할]

위 그림은 왼쪽은 Root(뿌리) 노드일경우에 가능한 경우이다

H 를 넣으려고 할때 노드를 3개로 분할 한 후 H 를 넣는 모습

Root 노드이기 때문에 floor(M/2) 와 관계 없이 G 가 하나로 존재 가능하다 G 가 루트가 되는 것

[일반노드 분할]

위 그림의 오른쪽이 일반노드에 대한 분할인데

만약 A B C D E 노드를 C 를 중심으로 분할 한다면 C 를 부모노드로 올려주고 C 를 기준으로

A B 를 왼쪽 D E 를 C 의 오른쪽 노드로 배치시켜서 분할 한다

(M 이 홀수 인 경우로 가정 =>

현재 차수 M = 5 로 가정 하였으므로 5/2=2 2개씩 나누어야 반씩 나눠 짐으로 왼쪽 두개,

오른쪽 두개 로 나눈다 3번째가 부모로 올라가는 형태 )

이때 부모로 올려야 하는 문제가 있는데 그것은 부모가 꽉찬 노드 일경우에 발생한다

이때는 부모를 분할 한 후 그다음 원래 분할 하려고 했던 노드를 분할 한다

분할 => split

* 삽입할때 현재 중간 노드들이 풀이면 M(차수) 만큼 풀이면 분할을 하고 그 위치에서 다시 삽입할 위치를 찾아간다 => 미리 분할 해 준다

- 마지막 leaf 노드까지 가서 마지막 leaf 노드가 풀이면 분할 후 삽입한다

[ 외부노드(leaf node) B-Tree 삭제]

삭제하고자 하는 자료가 있는 노드에 자료를 삭제 후 자료수가 M/2 이상이 되도록 보장해야 함

루트를 제외한 모든 노드는 M/2 보다 자료수가 많아야 한다, 이것이 보장 되어야 B-Tree 이다

이것의 해결 방법이 형제에게서 빌리기 VS 형제와 결합하기 이다

1. 빌리기 : 형제가 M/2 보다 맣은 자료를 가지고 있다면 빌려온다

2. 결합하기 : 형제에게서 빌릴 수 없다면=>M/2 보다 작다면 합친다

[형제에게서 빌리기] - Borrow key => 회전

왼쪽 그림은 B 를 삭제 하려고 하는데 A 하나 밖에 자료가 안남게 된다

그래서 D 를 빌려 올려고 하지만 D 를 A 노드 쪽으로 가져오면 부모인 C 와 순서(왼쪽이 작은쪽) 이 맞지 안으므로

D(형제) 를 부모 에게 주고 C 를 A 노드 쪽으로 주게 되면 => [자료를 돌리는 식]

B 를 삭제 할 수 있게 된다( 오타 : 그림상에서 D K 는 D G K 이다 )

이렇게 B Tree 의 규칙을 어기지 않고도 Balance 조정이 가능하다

[형제와 결합하기] - BindNode => 중간이 되는 부모 자료와 같이 결합하기

오른쪽 그림은 결합하기인데

B 를 삭제하기위해서 보면 A 가 있는 노드의 자료가 하나만 남기 때문에 그냥 지워선 안되고

D를 빌려오자니 D 와 함께 있는 E 가 하나만 남게 되어 빌려오는 상황도 여의치 안다

그래서 이때는 결합하기로 가야한다

먼저 A B 와 D E 중간에 위치한 부모의 C 를 아래로 내려서 그림과 같이 A B C D E 로 합친다 그 후 B 를 제거

[ 내부노드(leaf node가 아닌 ) B-Tree 삭제]

1.

i 를 삭제 하려고 할때 I 를 제거 하면 i 를 삭제하고 재 구성할 수 없으므로 대채하는 것으로 가야한다 => 키 순서상 재구성이 힘들다

이진트리와 동일하게 i 보다 바로 작은값 또는 i 보다 바로 큰 값으로 대채한 후 대채한 값을 삭제 하면 된다

Right Subtree 중 가장 작은 값인 J 로 i 대신 대채한 후 j 를 다시 삭제 하러 가면 된다

이때 j 를 삭제하기 위해 내려갈때 삭제시 M/2 이하인 노드는 형제에게서 빌리든지, 결합을 해야 한다

=> 삭제를 할때 부족한 노드가 있으면 안됨으로 balance 를 유지하기 위해

2. bindNode 를 할때 오른쪽 노드를 왼쪽으로 결합 하면 오른쪽 노드는 없어지게 되고 부모노드에 있는 자료중 하나가 아래려 내려 오게

되는데 이때 부모가 root 이고 부모의 자료 개수가 0 개가 된다면 합쳐진 왼쪽 노드를 부모노드로 해주면 된다

3. swap 루트에서 오른쪽으로 한번 이둥후 왼쪽으로 계속이동하면 I 보다 바로 큰 값을 찾을 수 있다

그 후 대채할 키를 다시 루트에서부터 삭제하는과정을 거치면 된다

이진트리의 경우 레벨(높이) 는 (log_2 N)+1 이하 이다 이때 밑이 2 인 것은 이진트리에서 자식은 2개씩 나갈수 있기 때문

B-Tree 의 경우 자식은 최소 M/2 개 이상이어야 함으로 밑이 M/2 이다

삽입/삭제/검색 성능 complexity 를 말할때는 굳이 밑을 쓰진 않는다 O(logN) 으로 성능이 좋다

-이진트리의 경우 평균 시간 복잡도가 nlogn 이며 최악의 경우 n 의 시간 복잡도를 갖는다

이를 보안할 것이 AVL-Tree, Red-Black Tree , B-Tree , Splay Tree 등이 있다

-최악의 경우가 없다

-차수가 높을 경우 노드내에서 순차검색대신 이분검색을 사용 하는 것도 속도를 높일 수 있는 방법이다

-모든 leaf 가 같은 레벨에 위치한다

tip : AVL Tree = leaf node 의 차이를 2 이하로 구성하는 트리 삽입시 이를 위반하면 자동 재구성한다

splay tree = 가장 최근에 사용된(삽입 삭제 검색) 노드를 루트로 항상 유지하는 트리이다

스케줄 알고리즘 등에서 LRU(Least Recently Used => 페이지교체 알고리즘) 같은 알고리즘을 구현하는데 적합

이진트리 형태로 구성

왼쪽노드는 키가 0 오른쪽 노드는 키가 1

서브트리는 루트의 왼쪽 하위는 0 오른쪽은 1 => 이진검색트리 특성과 유사하다

-각 트리의 레벨의 수치에 대한 비트수치를 적용

-왼쪽부터 오른쪽으로 비트가 증가하는 형태

Degenerated case = 한쪽으로 트리가 쏠리는 현상

같은 키를 넣으면 허용 않함

검색할때 최 하위 비트부터 동일한 비트인쪽으로찾아 검색해간다

즉 비트가 검색키이다

노드 삭제는 이진검색트리와 동일하게 삭제

삽입은 레벨에 따른 비트 검사를 통해 leaf 로 이동하여 leaf 에 추가한다

하위비트부터 살펴봐서 비트가 0이면 왼쪽으로 그다음 비트가 또 0 이면 다시 왼쪽으로 그다음 비트가 1 이면 오른쪽으로 이동

분기노드 = 네모 점 데이터는 없다

비트에 따라서 좌우를 판단하는 것은 동일하다

그래서 자료의 입력 순서와는 무관하다

키의중복은 허용되지 않는다( 중복을 허용하려면 링크드리스트를 이용 )

트리의 높이는 log_2(8) + 1 = 4, [8 leaf 노드 수]

자료는 2^M 개 입력될 수 있다, [m 은 키의 비트 개수 = 3]

trie : 키 비교를 한번만 한다 => 키비교가 복잡할때 사용되면 유용

삽입은 이전 값과 차이나는 비트까지만 분기를 하면서 노드를 하단에 위치하게 한다

차이가 나는 비트의 노드가 들어올때 분기 노드를 만들면서 노드는 가장 하위에 유지되도록 한다

C++ 알고리즘 참고

트리의 높이만큼 비교, 검색 하기 때문에 O(logN) 의 성능을 가진다

성능이 좋다

Radix Tree => 모든 노드가 정보노드

Radix Trie => 정보노드는 leaf 에, 내부(중간)노드는 분기노드

key 를 통해서 원하는 레코드를 가져온다

알고리즘 성능은 삽입,검색,삭제를 다 따져야 판단할 수 있다

array 는 무순서로 처음부터 끝까지 비교해가면서 찾아내는 방법

bin 은 자료가 들어올때 재 정렬 한다 => 재 정렬할때 삽입삭제는 느리지만 검색은 그만큼 빠르다

검색 알고리즘은 검색이 관건

- 이분검색의 경우 삽입할때 정렬해야 하기때문에 O(N) 삭제는 자식을 땡겨와야 하기 때문에 O(N)

검색은 좋은 성능인 lonN 을 보인다

내분검색의 검색은 loglogN 으로 성능이 좀 더 좋지만 실제 어느것이 빠를지는 해봐야 안다

결론적으로 순차검색 array, list 는 O(N) 으로 시간이 오래 걸린다 => 적은 자료집합에서는 사용할만지만

많아질경우 이분,내분으로 접근한다

선택정렬 : 최소값을 찾아서 제일 앞으로

삽입정렬 : 앞쪽에 데이터를 넣으면서 정렬을 시킨다 그래서 정렬된 =>이미 정렬된 부분에 이 값이 어디에 들어갈 것인가

버블정렬 : 인접한 값을 비교 교환

쉘 : 자료가 역순으로 정렬되어있어 속도가 많이 떨어지는 삽입정렬의 단점을 보완한 정렬 기법

추가 메모리 공간 소요가 없으면서도 정렬중에서도 속도가 빠르다

퀵소트 : 의 평균성능은 NlogN 이지만 최악의 경우 N^2 로 간다 => 추가 메모리를 비교적 필요로 하는 상황이 벌어진다

힙소트 : 최대값이 루트에 있다 , 추가 메모리를 필요하지 않는다 , => 힙소트 자체로 정렬 할 경우 NlogN 중에서는 비교적 조금 느린 성능을 보인다

특성을 잘 활용하는 것이 중요

병합정렬 : 순차적인 접근방식이라 순차적 접근방식에서 사용될만 한 방식=> stability 가 유지 되면서 추가 메모리가 필요 없다

Radix(기수) 들과 Distrubtion(분포수세기) 은 양의정수만을 또는 이진수를 정렬 할 수 있는 정렬 => 속도가 빠르다

http://blog.naver.com/kareons777/70075825158

// 렌더링 프레임수 계산
static DWORD FPS_Frames=0;
static float FPS_Num, FPS_LastTime=0;

if(FPS_Frames == 0) FPS_LastTime = (float)timeGetTime()/1000.0f;

float FPS_Time = (float)timeGetTime()/1000.0f;

if(FPS_Time - FPS_LastTime < 1.0f)
{ 
FPS_Frames++;
}
else
{
FPS_Num = FPS_Frames/((FPS_Time-FPS_LastTime));
FPS_Frames = 0;
FPS_LastTime = FPS_Time;
//FPS_Num 출력
}
timeGetTime()함수는 winmm.lib를 링크해야 합니다. 또한 #include <mmsystem.h> 해줘야 하고요.
이걸 함수로 뽑던지 그냥 랜더 함수에 넣어 주던지 하면 됩니다.

http://blog.naver.com/pluulove84/100058770623

다차원검색트리

KD-트리

- 이진검색트리를 확장한 것으로 k개(k≥2)의 필드로 이루어지는 키를 사용

- 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기한다

KD-트리 삽입

A(50, 50) → B(10, 70) → C(80, 85) → D(25, 20) → E(40, 85) → F(70, 85) → G(10, 60)

1. A(50, 50)이 루트 자리를 차지

2. B(10, 70)는 x값 10이 루트의 x값 50보다 작으므로 왼쪽 자식이 된다

3. C(80, 85)는 x값 80이 루트의 x값 50보다 크므로 오른쪽 자식이 된다

4. D(25, 20)는 먼저 x값 25가 루트의 x값 50보다 작으므로 루트의 왼쪽으로 가서 B(10, 70)를 만난다

    y값 20이 B의 y값 70보다 작으므로 B의 왼쪽 자식이 된다

5. E(40, 85)는 x값 40의 루트의 x값 50보다 작고, y보다 85가 B의 y값 70보다 크므로 B의 오른쪽 자식이 된다

6. F(70, 85)는 x값 70이 루트의 x값 50보다 크고, y값 85가 C의 y값 85와 같으므로 B의 오른쪽 자식이 되었다.

7. G(10, 60)는 x값 10이 루트의 x값 50보다 작고, y값 60이 B의 y값 70보다 작고,

    x값 10이 D의 x값 25보다 작으므로 D의 왼쪽 자식이 된다.

KD-트리 삭제

KD-트리 삭제

1. 자식이 없는 경우

 : 노드만 제거

2. 자식이 하나뿐인 경우

 : 자식이 둘인 경우와 같이 해결

 : 왼쪽 자식만 있는경우, 왼쪽 서브트리 중 노드 r에서의 분기에 사용한 필드 값이 가장 큰 노드를 찾아서 이동

3. 자식이 둘인 경우

 : 오른족 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드를 찾아서 이동

KDB-트리

KDB-트리의 노드의 종류

1. 영역 노드 : 복수 개의(영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드이다.

2. 키 노드 : 복수개의(키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드이다.

각 차원에서 범위가 주어지고 영역은 이들을 모두 만족하는 공간을 말한다.

KDB-트리의 키 검색

 : 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려가면 된다.

KDB-트리의 키 삽입

1. 삽입할 키가 속하는 리프 노드를 찾는다.

2. 해당 리프 노드가 키를 더 수용할 수 있는 공간이 있으면 (키, 페이지 번호) 쌍을 삽입하고 끝난다

3. 리프 노드가 키를 더이상 수용할 수 없을 경우, 형제 노드와 재분배할 수 있으면 재분배하고 작업은 끝난다.

4. 재분배가 불가능하면 리프 노드를 분할하여 두개로 만든다.

   → 이에 따라 부모 노드에 있던 한 영역이 두개로 나누어지므로(영역, 페이지 번호) 쌍이 하나 늘어난다.

   → 부모 노드가(영역, 페이지 번호)를 하나 더 수용할 공간이 있으면 작업은 끝이다.

   → 만일 부모 노드가 이것을 수용할 수 없으면 부모 노드를 분할 한다.

http://yeols.com/80075364360

기수 정렬(Radix Sort)

• 특수 정렬 알고리즘(기수 정렬, 계수 정렬) 중 하나.
  
  
• 특수 정렬 알고리즘
• 비교 정렬
• 두 원소를 비교하는 정렬의 하한선은 Ω(nlogn)
  
  " 최악의 경우 정렬 시간이 θ(nlogn)보다 더 빠를 수는 없는가? "
  
  
• 그러나 원소들이 특수한 성질을 만족하면 O(n)정렬도 가능하다.
• 기수 정렬
  - 원소들이 모두 k 이하의 자리 수를 가졌을 때 (k: 상수)
  
  
• 기수 정렬의 개념
• 입력이 모두 K 이하의 자리 수를 가진 특수한 경우에(자연수가 아닌 제한된 종류를 가진 알파벳 등도 해당) 사용할 수 있는 방법
  
  
  
• θ(n)시간이 소요되는 알고리즘
  
  
• 기수 정렬 수행 과정 #1
• 원소들의 일의 자리부터 비교 후 정렬, 다음은 십의 자리를 비교 후 정렬 ...

• 기수 정렬의 수행 과정 #2
• 정렬되지 않은[69, 10, 30, 2, 16, 8, 31, 22]의 자료들을 기수 정렬 방법으로 정렬하는 과정을 살펴보자.
• 키 값이 두 자리 십진수 이므로, 10개의 버킷을 사용하여 기수 정렬을 두 번 반복한다.

1. 초기 상태 : 큐(여러 개의 원소들이 일정한 순서로 나열된 자료 구조이며, 스택과는 달리 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있도록 되어 있음)를 사용하여 0부터 9까지 10개의 버킷을 만든다.

2. 키 값의 일의 자리에 대해서 기수 정렬 수행 [1단계]

- 정렬할 원소의 일의 자리 값에 따라서 순서대로 버킷에 분배 -

2. 키 값의 일의 자리에 대해서 기수 정렬 수행 [2단계]

- 버킷에 분배된 원소들을 순서대로 꺼내서 저장 -

3. 키 값의 십의 자리에 대해서 기수 정렬 수행 [1단계]

 - 정렬할 원소의 십의 자리 값에 따라서 순서대로 버킷에 분배 -

3. 키 값의 십의 자리에 대해서 기수 정렬 수행 [2단계]

 - 버킷에 분배된 원소들을 순서대로 꺼내서 저장 -

• 기수 정렬 알고리즘 분석
• 메모리 사용공간
• 원소 n개에 대해서 n개의 메모리 공간 사용
• 기수 r 에 따라 버킷 공간이 추가로 필요
  
  
• 연산 시간
• 연산 시간은 정렬할 원소의 수 n 과 키 값의 자릿수 d 와 버킷의 수를 결정하는 기수 r 에 따라 달라진다.
  - 정렬할 원소 n 개를 r 개의 버킷에 분배하는 작업 : (n+r)
  - 이 작업을 자릿수 d 만큼 반복
  
  
• 수행할 전체 작업 : d(n+r)
• 시간 복잡도 : O(d(n+r))

  [출처] 정렬 알고리즘 - 기수 정렬(Radix Sort)|작성자 열쓰

이진트리(바이너리트리)를 이용하여 검색하는 방법 O(logN) 의 성능 : 성능이 괜챃다

이진검색트리는 이진트리(바이너리트리)를 이용한 검색 방법

조건 Heap 은 부모노드가 두개의 자식노드보다 커야 하지만

1.이진검색트리는 부모노드는 왼쪽 sub-tree 의 모든 노드보다 크고

2.부모노드는 오른쪽 sub-tree 의 모든 노드보다 작아야 한다

재귀적으로 모든 조건을 만족해야 한다

그랫 In-Order Traversal 하면 정렬된 순서가 된다 (왼쪽 부모, 오른쪽 노드순으로 방문)

트리는 부모가 양 자식노드의 포인터를 가지고 있는 상태

검색

1.. 루트부터 검색 시작

2. 각 노드와 찾을 값을 비교해가면서 노드에서 좌측은 작고 우측은 큰것이기 때문에 키값이 같을때까지 비교를 반복해간다

=> 조건에 따라 자식 포인터를 타고 계속 내려간다 키를 찾을때까지

마지막 까리 노드까지 내려가서 찾지 못하면 fail

삽입

루트부터 비교를 하면서 새로운 노드는 항상 leaf 에 배치한다

(이때 트리 구조상 부모가 자식을 가르키고 있어야 함으로

포인터를 두개를 두어 이전 포인터 값을 유지하고 있어야 한다

하나는 현재 노드 하나는 이전노드를 가르키는 포인터)

또한 마지막 노드의 왼쪽 오른쪽에 들어가야 하므로

부모노드를 저장하고 있는 포인터가 P 였고 P 의 오른쪽에 노드가 추가 되어야 한다면

P 의 Right 에 노드 하나가 추가 되면서 추가된 노드 또한 아무것도 가르키고 있지 않은 포인터 두개(자식2개) 를 갖는 노드가 되어

추가 되어야 한다

삭제

삭제를 하고도 이진트리의 조건에 맞아야 한다

마지막 노드는 그냥 삭제 하면 되지만 중간에 잇는 노드를 삭제할때는

자신보다 작은 노드중 최대노드 또는

자신보다 큰 노드중 최소 노드를 선택

선택 방법은 부모 노드에서 왼쪽은 모두 부모모다 작은 것임으로

자신보다 작은 노드중 최대노드는 부모에서 왼쪽으로 한번갔다가 오른쪽으로 쭉 가는 순서

=>부모의 왼쪽 트리중에서(부모제외한) 중위순회를 해서 제일 마지막에 나오는 노드가 작은것중에 큰것

자신보다 큰 노드중 최소 노드는 부모를 제외한 오른쪽 노드트리에서 중위순회를 하여 가장 첫번째 나오는 것이

부모를 제외한 오른쪽 노드트리에서 가장 작은 값이다

...자식의 자식에 대한 처리 이하 생략..

이진 트리는 좌우로 균형이 맞을때 성능이 가장 좋다

입력 순서가 중요하다,

만약 정렬된 순서(순차 or 역순)로 입력이 될 경우 링크드리스트 처럼 입력이 될 수 있다 => 최악의 경우로 가게 된다

find, insert 최악의 경우 O(N), 균형이 맞으면 O(logN)

remove O(logN) => 삭제할때 insert 시 O(N)의 성능을 가져도 노드끼리의 포인터 연결이 간단해 짐으로 결론적으로 O(logN) 의 성능을 가짐

insert, find, remove 평균적으로는 O(logN) 의 성능을 갖는다

결국 트리의 균형을 맞추는 것이 중요하다 그래서 Balanced Tree 가 많이 연구됨

그래서 이진트리의 삽입을 개선한다

[이진트리 균형 맞추기]

정렬된 데이터를 배열로 가지고 있고 이것을 이진트리에 저장하려고 할때

트리를 중위순회 방식으로 순회하면서 트리를 생성할때 중위순회시 데이터를 노드에 저장하면 한쪽으로 치우친 형태가 아닌

균형이 맞는 balance 형태의 트리로구성할 수 있다

- 성능이 않좋을때 balance 로 균형을 한번 맞춰준다

중복키 문제

이진트리는 중복키에 대해서 제대로 처리 하지는 못하는데 이걸 해결 하기 위해 링크드 리스트와 바이너리 리스트를 결합해 해결한다

중복되는 키를 가지고 있는 노드에 대해서 링크드 리스트를 두어 링크드 리스트 뒤에 넣어주는 식으로 해놓고

키에 대해서 next 를 호출하면 중복된 키들의 첫번째에서 두번째로 이동하여 해당 데이터를 리턴

이진트리 특징

all nodes in left subtree < parent < all nodes in right subtree

성능이 트리의 균형에 좌우된다

n >= 1

F_n = F_{n-1} + F_{n-2}

F_1 = F_2 = 1

1 1 2 3 5 ....

F_1 F_2 F_3 F_n

n 은 피보나치 수열을 만드는 번째..

int fibonacci(int n){

if( n == 1 || n == 2)

return 1;

return fibonacci( n - 1 ) + fibonacci( n - 2 ) ; // 후위 순회와 유사하다 값을 나중에 리턴 함으로..

}

피보나치수열 참고

참고 : http://blog.naver.com/kwanskim?Redirect=Log&logNo=20110843012

자연계의 피보나치 수열  게시판  2010/08/02 05:30 http://blog.naver.com/kwanskim/20110843012

1. 문제의 크기는 점점 작아져야 한다.

2. 재귀호출이 끝나는 조건이 있어야 한다

Factorial 구하기

문제의 크기 감소 : N! = N*(N-1)!

종료조건 0! = 1

int factorial( int n )

{

if( n == 0 ) // 만약 n =0 을초기 값으로 입력 했으면 1 이 나오야 함으로....

return 1;

else

return n * factorial( n-1);

}

[트리순회는 재귀호출로 이해될 수 있다]

트리순회(Tree Traversal)

1. Pre-order Traversal

2. In-order Traversal

3. Post-order Traversal

4. Level-order Traversal

의 순회 방법들이 있는데 이러한 순회 방법이 있는 이유는

트리는 선형이 아닌 비선혀이기 때문에 모드 노드들을 거쳐가기 위한 방법이 필요하게 된다

그리하여 위와 같은 순회 방법이 나오게 되었다

( 반례 : list 의 경우 선형이기 때문에 특별한 노드를 거쳐가는 방법을 필요로 하진 않는다)

sub 트리 : 트리의 부분 집합 참고 : http://www.cyworld.com/sjh0628/6850615

서브트리는 자식을 하나라도 가지고 있는 노드가 있다면 그 노드를 중심으로 서브트라 볼 수 있다

전위순회 (Pre-order)

Pre-Order Traversal

1. Root 를 방문한다

2. 왼쪽 subtree를 방문한다

3. 오른쪽 subtree 를 방문한다

특징 : 루트가 가장 먼저 나온다

노드를 먼저 들린다, 그래서 Pre

PreOrderTraversal( Node* pNode ){

if( pNode != m_pNodeTail )

{

visit(pNode); // 해당 노드에서 왼쪽, 또는 오른쪽으로 갈지를 정하기 전에 해당 노드를 들린다

PreOrderTraversal(pNode->pLeft );

PreOrderTraversal(pNode->pRight );

}

}

tip : 노드와 처음 마주칠때 방문한다

중위순회 (in-order)

1. 왼쪽 Subtree 를 방문한다

2. Root 를 방문한다.

3. 오른쪽

특징 : 가장 왼쪽노드가 먼저 나온다

노드를 중간에 들린다, 그래서 In

InOrderTraversal( Node* pNode ){

if( pNode != m_pNodeTail )

{

InOrderTraversal(pNode->pLeft );

visit(pNode); // 왼쪽 먼저 트리를 찾아 갔다가 왼쪽이 없으면 방문하고 오른쪽을 가기 때문에 중위 순회

InOrderTraversal(pNode->pRight );

}

}

tip : 왼쪽으로 갔다가(왼쪽 끝까지 갔다가) 다시 올라올때 방문한다

후위순회 (post-order)

1. 왼쪽 subtree 를 방문한다.

2. 오른쪽 subtree 를 방문한다.

3. root 를 방문한다

특징

1. 가장 온쪽 노드가 첫번째 나온다

2.루트가 가장 나중에 나온다

노드를 마지막에 들린다, 그래서 Post

PostOrderTraversal( Node* pNode ){

if( pNode != m_pNodeTail )

{

PostOrderTraversal(pNode->pLeft );

PostOrderTraversal(pNode->pRight );

visit(pNode); // 왼쪽, 오른쪽 다 들린 후 마지막에 올라올때 들린다

}

}

tip : 현재 노드에서 오른쪽으로 갔다가 오른쪽 끝까지 간 후 다시 올라올때 방문한다

레벨순회 (Level-order)

특징 : 루트가 가장 먼저 나온다

큐를 이용

PreOrderTraversal( Node* pNode ){

ListQueue<Node*> queue;

queue.Put(pNode);

while( !queue.IsEmpty() ) // iteration

{

pNode = queue.Get();

if( pNode != m_pNodeTail )

{

visit(pNode);

queue.Put(pNode->pLeft );

queue.Put(pNode->pRight );

}

}

}

정리하면 A 에 딸려 있는 바로 아래 자식들을 큐에 순서대로 추가 한다( A를 큐에서 제거 후 B,C 추가)

순서적으로 B,C 의 순이니 추가된 B를 제거 후 B 의 바로 한칸 아래 자식들을 다시 큐에 추가 하면

C , D, E 의 순이 된다

그러면 다시 C 에 대한 자식 F 를 큐에 추가 하고 C 를 제거(즉 앞에 있는 것을 제거 하면

트리 각 레벨에서 왼쪽에서 오른쪽의 순으로 큐 뒤에 추가 하는 것이 된다

즉 큐에서 제거 되는 노드의 자식들을 큐 뒤에 추가 함으로써 위에서 아래로, 왼쪽에서 오른쪽으로의 노드를 순회 할 수 있게 된다

tip : 큐의 가장 처음 즉 queue.Get() 할때의 노드를 제거 하면서 제거되는 노드들의 자식(2개 또는 1개) 을 큐의 뒤에 추가해준다

자식을 추가 하기 전에 노드를 방문한다

생성자에서 헤드노드와 테일 노드를 만든다

파괴자에서는 추가된 노드를 모드 제거한 후 가상 노드(헤드, 꼬리) 를 제거한다

이중리스트 처럼 가상누드인 헤드와 테일 노드를 기준으로 이진트리를 생성한다

Tip 트리를 생성할때 Left, 또는 Right 중 가르키는 겂이 없을 때는 테일 노드를 가르키도록 한다

트리는 비선형 자료구조이다(선형이 아니다 )

Node( vertex) 와 Link(edge)로 구성됨

Node 는 정보(data)를 포함한다

Link는 두 Node 간의 연결을 나타냄

특징 :

Root 가 하나 존재 해야 한다 Root 는 최상의 Node

Root를 제외한 모든 Node 는 하나의 부모를 가져야 함

Node 는 여러개으 자식을 가질 수 있다

한 Node로 부터 다른 Node로 가는 경로는 유일해야 함

ex ) 윈도우 파일 구조( 윈도우 탐색기 )

leafNode

줄기의 끝 = 자식이 없는 노드 H,J,D,E,F,G , 최 하위 노드

Terminal node : 끝인 노드

Internal Node : Leaf Node 가 아닌 노드 , 즉 자식이 하나라도 있는 노드 B,C,I,A

sub tree : 트리의 부분 집합 {B,E,F,G} , {I,J} , {D}, ,

Path : 한 Node로 부터 다른 Node 로 가는 경로(중복없이 가능 경로)

만약 G와 C 가 연결 되어 있다면 G 에서 C 로 가는 경로가 한가지가 아닌 다른 경우의 수가 생김으로 그때는 트리가 되지 않느다

만약 연결됐다면 이때는 이것을 그래프 라고 한다

레벨(Level) : Root 에서 특정 노드로 가는 경로의 노드 수, 이때 Root 를 Level 1 로 친다

그래서 위 그래프의 레벨은 4 이다

최소공통선조(Least Common Ancedstors) ; 두 노드의 공통적인 선조중 가장 레벨이 높은 선조 노드

H,J 를 놓고 봤을때

H의 선조 = C,A

J 의 선조 = I ,C, A

공통 선조 C,A

가장 높은 선조는 Level 2 인 C 가 된다

이것이 중요한 이유는 경로는 항상 최소공통선조를 거쳐서 지나가기 때문!!!

자식 노드 : 자신의 아래에 연결되어 있는 노드 => C 의 자식 노드는 H,I

부모노드는 : 자신의 위에 있는 노드 =>I 의 부모는 C

조부모 : 자신의 부모의 부모노드 I 의 부모는 C , C의 부모는 A, 그래서 I 의 조부모 노드는 A 가 된다, J 의 조부모는 C

중위표기법 4+3 인 연산자가 중간에 있는 식을

먼저 후위 표기법으로 바꾼후 다음을 실행한다

1. Operand(숫자) 를 만나면 Operand를 Stack 에 PUsh

2. Operator 를 만나면 Stack 에서 Pop 을 두번해서 이 두 값으로 연산을 한 다음

연산된 결과를 다시 Stack에 Push 한다

3. 최종결과는 마지막에 Stack 에 남아 있는 값이다(마지막 연산된 결과를 PoP 하면 결과값)

연산자를 놓느 순서는

연산자 오른쪽에 먼저 그다음 연산자 왼쪽 순으로 놓는다

연산시 +,* 는 교환이 성립함으로 간단하게 한줄로 처리 할 수 있지만

/,- 는 교환 법칙이 성립하지 않음으로 Pop 을 할때 순서에 맞게끔 구성해야 한다

문자를 숫자로 바꾸는 것은 다음 링크를 참고 한다

계산기 : 수식을 입력받아 계산하여 출력한다

계산기를 만들려고 할때의 데이터들로 순회구조를 변환해 본다

operator +,-,*,/ 만 가능하다고 가정(사칙연산)

Operand : 연산자 양쪽에 있는 자료형

이때의 Operand 는 정수만 가능하다고 가정

* 중위 표기법 (Infix Notation) A + B

- 우선순위를 위해 괄호를 사용해야 함

*후위 표기법(Postfix Notation):

수식을 계산하기 위한 알고리즘이 단순!

- 괄호를 쓰지 않아도 연산 가능

AB+

*전위 표기법 (Prefix Notation)

- Operator 가 두 Operand 앞에 있음

+AB

중위를 후위 표기법으로 알고리즘을 풀기 위해 중위로된 식을 후위 표기법으로 변환 해야 한다

the way that 1. 중위 표기법에서 괄호가 씌워져 있는 경우에만

조건 A+B*C 에 대한 연산이 완전한 괄호로 되어 있어야 한다

ex) (A+(B*C))

알고리즘( 결과 저장소는 String 이라 가정 )

1. '(' 문자는 무시한다

2. Operand(숫자) 는 그대로 결과저장소에 추가( += )

-하나의 숫자(항) 이 입력되면 구분하기 위해 ' ' 을 추가로 입력해 준다

3. Operator(연산자) 는 Stack 에 PUsh 한다

- 저장소에 연산자를 저장할때 여산자와 구분을 하기 위해서 스택에서 빼오 연산자를 저장소에 넣은 후 ' ' 을 하나 연달아 넣어준다,

4. ')' 를 만나면 Stack 에서 Pop 하여 결과저장소에 추가 ( += )

the way that 2. 중위 표기법에서 괄호가 없는 경우

먼저 연산자 우선 순위를 정해야 한다

'(' : 0

+,- : 1

*,/ : 2

로 우선 순위를 매기고

큐, 환원큐 모두 양방향 리스트 또는 배열로 구현 할 수 있는데

*리스트로 짤 경우 양방향리스트로 구성해야 한다

배열로 하면 배열값을 밀어내야 하는 상황이 발생 함으로

양방향 리스트로 만드는 것이 일반적으로 효율적이다

환원큐가 비었을 때는 front == real 이며

꽉 찾을때는 하나의 공간을 두고 front 와 real 이 1 간격으로 배치하게 된다

real 에서 데이터 추가, front 에서 데이터 빼온다

real 에 추가시 현재 가르키고 있는 곳에 데이터를 추가 한 후 real++

front 에서는 현재 가르키고 있는 곳에서 데이터를 빼낸 후 front++

그냥 front의 값만 가져오려면 {리스트&배열}[ front ] 의 값을 가져오고

(+ 가 순방향이라고 가정했을때)

real 의 값만 가져오려면 {리스트&배열}[Dec(real-1 )] 을 가져오면 된다

환원큐의 인덱싱은 % 를 활용

m_size 가 배열 사이즈 만약 10 이라고 한다면

현재 가르키는 곳의 다음 번지를 알기 위하여

가르키는 곳 n 에 +1 을 한 후

전체 사이즈로 나누면 배열 사이즈 버위 내에서

순환하는 인덱스 번호를 얻어올 수 있다

감소 ( Dec() )는 (n-1) % m_size;

스택(배열)

데이터 집합을 배열에 저장

Top 의 위치를 저장하는 멤버 필요

생성자에서 디폴트 배열 크기를 정해준다

-특징

top 은 가장 최근 원소를 가르키는 것임으로 top 의 초기치는 -1 이 된다

배열에 가득 차면 에러를 반환하거나 더큰 배열로 옮기든가 해야 한다

스택(리스트:다일연결리스트)

단일 연결리스트 자체가 스택이다

연결리스트에 저장( 단순 연결 리스트로 구현 할 수 있다 )

add, remove

연결리스트 특성상 스택의 크기가 자유롭다

결론 :

일반적으로 리스트 스택을 많이 사용

 첫 노드부터 끝노드 까지는

반복문을 돌면서 레퍼런스로 넘어가는 다음 포인터를 넘어받아와 이 구문을 계속 돌리면 된다

끝에서 처음으로 가는 것은 이전의 노드를 얻어오는 함수를 호출하면서 포인터를 레퍼런스로 넘기면 된다

list == 이중리스트

*find( 값 )

값과 같은 값을 찾기 위해 위와 같은 조회 방식을 이용해 값을 비교해 가며 찾을 수 있다

Tip : 끝노드를 자기 자신을 가르키고 있으니 즉

tail 의 next 는 &tailNode 이니 디버그 상에서

어느 한 노드의 next 포인터를 따라가다보면 마지막엔 tail 노드의 주소 값이 계속해서 반복적으로 나타남을 알 수 있다

정의

- 양방향 연결 리스트

- Data 와 Next pointer, Prev Pointer 로 구성

헤더와 꼬리가 초기에 주어진다는 점은 단순연결 리스트와 동일

초기화는

헤더는 의 prev 는 자기자신 이고 next 는 테일을 가르킨다

테일에서는 next 가 자기자신을 가르키고 prev 가 헤드를 가르키도록 한다

각 노드에는 데이터를 답을 수 있는 templte< typename T > 인 T 로 정의 한다

Tip : insert 시 기준이 되는 노드와 멀리떨어져 있는 노드와 새로운 노드와의 연결을 먼저 연결한다

because 기준이 되는 노드와 새로운 노드를 먼저 연결하면 기존에 연결 되어 있던 노드의 포인터를 잃어버리기 때문

1. 삽입

이전 삽입 :

define void* POS

- 다음삽입( Insert Next) 도 InsertBefore 와 유사하게 마들어 질 수 있다

*삭제

이중리스트는 양쪽의 포인터 정보를 알기 때문에 자기 자신을 지울 수 있다

삭제할 노드의 양쪽 노드들이 삭제 할 노드를 가르키지 않고 기준 노드의 양쪽노드들을 서로가 가르키게 한다

그런 후 삭제기준 노드를 삭제