먼저 우리가 흔히 아는 특수문자는 반각문자 입니다. (키보드에 존재하는 특수문자 !@#$% 등등) 전각문자는 윈도우 한자 키를 사용하여 생성된 특수문자입니다. (123abc?!등등)

전각문자를 사용해도 표현은 되지만 문자 사이의 간격이 반각보다 커서 가독성 문제나 123과 같은 숫자가 전각일 경우, 문자로 인식되는 것등의 문제가 있습니다. 

따라서 파이썬에서 전각문자를 반각문자로 변경하는 방법은 아래와 같습니다.


# 전각문자
full = '!'
# 반각문자
half = '!'
# 전각문자와 반각문자의 차이
diff = '0xfee0'
# 전각문자 블랭크
blank = '0x3000'

# 16진수인 ascii code
hex_ascii_full = ord(full)
hex_ascii_half = ord(half)
hex_ascii_diff = int(diff, 16)
hex_ascii_blank = int(blank, 16)

# 16진수 형태의 string
hex_full = hex(hex_ascii_full)
hex_half = hex(hex_ascii_half)
hex_blank = hex(hex_ascii_blank)

# 전각일 경우 전각 기준인 값을 차감해 반각으로 변경
if hex_ascii_full >= hex_ascii_diff:
    result = hex_ascii_full - hex_ascii_diff
# 빈칸이 전각일 경우는 위 공식에 어긋나므로 강제로 반각형태의 빈칸을 지정
elif hex_ascii_full == hex_ascii_blank:
    result = hex_blank


assert chr(result) == '!'


파이썬3은 string이 전부 unicode입니다. 따라서 ord() 함수를 사용하여 문자열을 아스키코드로 변환할 수 있습니다. (= Hexadecimal Ascii Code) 다음 변환된 아스키 코드를 hex()로 감싸면 원하는 유니코드표(=16진수)의 값을 확인할 수 있게 됩니다. 이러한 작업을 한 다음, 비교문을 통해 0xfee0 값 보다 큰 값은 전부 전각문자이므로 16진수 형태의 문자와 차를 구하게 되면 반각문자를 구하게 될 수 있습니다. 계산된 전각문자는 16진수이므로 내장함수인 chr() 함수를 사용해 우리가 알고있는 문자로 변환을 하면 끝입니다. 

만약 반각 → 전각 문자로 변경하고자 하면 0xfee0 값 보다 작은 값을 찾아, 더해주면 됩니다.


삽질

코드는 다른 언어에 비해 간단하다고 할 수 있는데 가장 기본인 파이썬3의 모든 string이 unicode이다 이 부분을 까먹으면 혼돈에 빠지게 됩니다.


1. 먼저 첫 번째로 한 삽질은 str.encode('unicode_escape') 를 사용해 문자를 unicode 형식으로 변경할 수 있습니다. 하지만 변경된 문자는 b'\\uac00' 와 같은형식으로 바이트 타입입니다. 혹시나 해서 바이트 타입을 벗기면 \uac00 와 같은 string 타입이 나오게 됩니다.. 만약 반각일 경우는 \u가 없는 바이트 타입이 나오게 됩니다. 이러한 방식은 전각 ↔ 반각 변경에 전혀 쓸 수 없습니다. (하려면 할 순 있지만 코드가 방대하고 어려워지게 됩니다.)

2. 두 번째로는 바이트로 변경하여 전각문자와 반각문자의 차이값인 0xfee0 만큼 빼려고 시도했습니다. 하지만 바이트는 더하거나 뺄 수없고 시프트로 자리값을 밀어야 합니다. 이 방법 또한 구현하기 복잡하고 디버깅이 어려워 바로 포기했습니다.



간단한 문제를 다양한 방법으로 삽질을 통해 해결하긴 했지만 가장 기본인 파이썬3의 모든 string이 unicode이다 가 제일 중요합니다.

Heap Sort

Heap

Tree에서의 Heap을 사용 (Max Heap 또는 Min Heap)

  • 따라서 complete binary tree 임
  • Max Heap일 때 parent node는 child node(subtree)의 key보다 무조건 큼
  • binary search tree가 아님
  • Tree의 Heap은 정렬을 위함이 아닌 Insert와 Delete를 위함
  • Max(Min) Heap의 내용은 Heap 에서 확인



1. Max(Min) Heap을 만든 다음 모든 데이터를 넣음

2. (Max Heap이라 할 때) 만든 heap tree에서 root node를 지우고 정렬하고자 하는 list에 지운 root node를 넣음

3. (Max Heap이라 할 때) heap tree를 재조정해서 루트를 결정한 다음, 다시 루트를 지우고 list에 해당 값을 넣음

4. 이 방식을 트리가 없어질 때 까지 진행

퍼포먼스

시간복잡도는 O(nlog₂n)

  • n은 트리의 노드 개수

Heap tree의 전체 높이가 log₂n(완전 이진 트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 Heap tree를 재구성하는데에 log₂n 만큼 소요됨

insertion 또는 deletion 하는 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 소요됨


저장공간이 적게 필요

  • Heap tree를 구성하는 공간만 필요함 (+ 정렬된 값을 저장하는 리스트)

빠르고 저장공간이 적게 필요하기에 임베디드 시스템에 유용

Quick Sort

정렬하고자 하는 값 중, 1개를 선택하고 선택된 값을 기준으로 작으면 왼쪽, 크면 오른쪽으로 나눈 다음 2개로 분할한 리스트에서 각 정렬한 후 합침.

  • 위와 같이 분할 후, 합치는 방식으로 divide and conquer 라고 부름

    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현

  • merge sort와 다르게 리스트를 균등하지 않게 분할함

Quick Sort 종류

  • Plain Quick Sort
  • Quick sort with randomized pivot
  • In-place quick sort


1. 정렬하고자 하는 리스트에서 값 1개를 선택 (선택한 값을 pivot이라 부름)

  • 보통 정렬하고자 하는 리스트의 가장 왼쪽, 중간 또는 가장 오른쪽을 선택

2. 다음 pivot을 중심으로 pivot 보다 작으면 왼쪽 pivot 보다 크면 오른쪽으로 분류 (divide)

3. 분류를 한 다음, 왼쪽과 오른쪽으로 분류된 값들 중, 각각 가장 왼쪽에 있는 수를 다시 pivot으로 잡고 다시 분류를 함.

  • 만약 수가 변하지 않으면 다음 수를 pivot으로 잡음
  • 가장 왼쪽에 있는 수가 바뀌었을 시, 해당 수를 pivot으로 잡고 다시 정렬

4. 더이상 정렬할 값이 없으면 분류한 값을 새로운 리스트에 담고 종료

예시


예시2


예시3

항상 마지막의 수를 선택

아래와 같은 방식이 in-place quick sort로 추가적인 저장공간이 필요없음

  • in-place : 입력된 리스트 내부에서 정렬이 일어남

예시4

상세 예시

6 3 8 7 9 2 1 5


pivot은 P, 왼쪽에서 시작하는 값은 L, 오른쪽에서 시작하는 값은 R이라 가정

L은 P보다 큰 값이 나올때까지 오른쪽으로 이동

R은 P보다 작거나 같은 값이 나올때까지 왼쪽으로 이동

L이나 R이 위 공식이 성립한다면 해당 값에 멈춤

  • L과 R이 전부 멈췄을 때 위치를 변경

R의 인덱스가 L보다 작아질 경우 P와 R 값의 위치를 변경

L과 R이 동일한 인덱스에 있을 경우, P와 R 값의 위치를 변경

pivot을 리스트의 가장 왼쪽 값을 선택하는 경우

1. 초기 값 세팅

6, 3, 8, 7, 9, 2, 1, 5

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 8, 7, 9, 2, 1, 5

PL R

3. 두 값의 위치 변경

6, 3, 5, 7, 9, 2, 1, 8

PㅤㅤL ㅤㅤ R

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 9, 2, 1, 8

PL R

5. 두 값의 위치 변경

6, 3, 5, 1, 9, 2, 7, 8

PㅤㅤㅤL R

6. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 1, 9, 2, 7, 8

Pㅤㅤㅤㅤ L R

7. 두 값의 위치 변경

6, 3, 5, 1, 2, 9, 7, 8

Pㅤㅤㅤㅤ L R

8. 해당 위치부터 다시 2번내용

6, 3, 5, 1, 2, 9, 7, 8

Pㅤㅤㅤㅤ R L

9. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

2, 3, 5, 1, 6, 9, 7, 8

ㅤㅤㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 양쪽 리스트에서 다시 P를 선택하여 재진행 (왼쪽 먼저 진행)

2, 3, 5, 1, 6, 9, 7, 8

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

2, 3, 5, 1, 6, 9, 7, 8

P LR

3. 두 값의 위치 변경

2, 1, 5, 3, 6, 9, 7, 8

P LR

4. 해당 위치부터 다시 2번내용 수행

2, 1, 5, 3, 6, 9, 7, 8

P RㅤL

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

1, 2, 5, 3, 6, 9, 7, 8

P


1. P의 위치가 변경 () 되었으므로 P의 양쪽 리스트에서 다시 P를 선택하여 재진행

  • 왼쪽에 값이 1개밖에 없으므로 오른쪽만 진행

1, 2, 5, 3, 6, 9, 7, 8

P R

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 5, 3, 6, 9, 7, 8

P R

L

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 9, 7, 8

P



1. 처음 pivot을 6으로 잡았을 때 기준으로 왼쪽은 모든 정렬이 완성됐으므로 오른쪽 진행

1, 2, 3, 5, 6, 9, 7, 8

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 9, 7, 8

PㅤㅤR

ㅤㅤ L

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 8, 7, 9

P



P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

1, 2, 3, 5, 6, 8, 7, 9

P R

L

1. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 8, 7, 9

P R

L

2. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 8, 9

P


Quick Sort 완성

1, 2, 3, 5, 6, 7, 8, 9

pivot을 리스트의 중간 값을 선택하는 경우

1. pivot을 리스트의 인덱스 중간으로 선택

6, 3, 8, 7, 9, 2, 1, 5

L ㅤPR

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 8, 7, 9, 2, 1, 5

L PR

3. 두 값의 위치 변경

6, 3, 5, 7, 9, 2, 1, 8

ㅤ ㅤ L PR

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 9, 2, 1, 8

P LR

5. 두 값의 위치 변경

6, 3, 5, 7, 1, 2, 9, 8

ㅤㅤㅤㅤP LR

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 1, 2, 9, 8

ㅤㅤㅤㅤP ㅤ R L

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

6, 3, 5, 2, 1, 7, 9, 8

ㅤㅤ ㅤㅤㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • pivot을 리스트의 인덱스 중간으로 선택

6, 3, 5, 2, 1, 7, 9, 8

L PㅤR

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 5, 2, 1, 7, 9, 8

L ㅤ PㅤR

3. 두 값의 위치 변경

1, 3, 5, 2, 6, 7, 9, 8

L ㅤ PㅤR

4. 해당 위치부터 다시 2번내용 수행

1, 3, 5, 2, 6, 7, 9, 8

PR L

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

1, 3, 2, 5, 6, 7, 9, 8

ㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • pivot 5의 우측 리스트는 값이 1개이므로 왼쪽만 진행

1, 3, 2, 5, 6, 7, 9, 8

L P R

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 3, 2, 5, 6, 7, 9, 8

P R

ㅤL

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 9, 8

P


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • 좌측의 경우 1, 2인데 1에 P와 R이 동일한 위치가 되므로 변경되는 값은 없음

1, 2, 3, 5, 6, 7, 9, 8

P L

R


1. 처음 pivot을 7으로 잡았을 때 기준으로 왼쪽은 모든 정렬이 완성됐으므로 오른쪽 진행

1, 2, 3, 5, 6, 7, 9, 8

P R

ㅤL

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 7, 9, 8

P R

ㅤL

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 8, 9

P


Quick Sort 완성

1, 2, 3, 5, 6, 7, 8, 9

pseudo code

위 예시를에 해당하는 코드 컨셉

int partition(int list[], int low, int high )
{
	int left, right; int pivot; int pivot_item;
	pivot_item = list[low];
	pivot = left = low;
	right = high;

	while ( left < right ) {
		/* Move left while item < pivot */ 
		while( list[left] <= pivot_item ) left++; 
		/* Move right while item > pivot */ 
		while( list[right] > pivot_item ) right--; 
		if ( left < right ) swap(&list[left],&list[right]);
	}
	
	/* right is final position for the pivot */
	list[low] = list[right];
	list[right] = pivot_item;
	
	return right;
}

퍼포먼스

시간복잡도는 O(n·log₂n) - worst case 제외

  • list의 개수인 n 번만큼 비교 x log₂n 실행

    log₂n 번 만큼 어떻게 실행?

    Quick Sort는 리스트를 반으로 쪼개나가는 형식. 최대 degree는 2라고 볼 수 있어서 binary tree라 볼 수 있다.

    더이상 쪼갤 수 없는 크기만큼 쪼갠다면 node는 1개만 가지게 되므로 위 그림처럼 트리의 높이만큼 실행이 됨. 따라서 트리의 높이 공식인 log₂n 번 만큼 쪼개 나간다는 것을 알 수 있음.

    n 번 만큼 어떻게 비교?

    위의 각 트리의 depth마다 리스트의 크기인 n번 만큼 비교가 일어남.


    따라서 n·log₂n


  • 시간복잡도가 worst case에서는 O(n²)까지 발생함

문제점


위와 같이 이미 정렬된 상태에서 가장 왼쪽의 값을 pivot으로 잡으면 시간복잡도가 O(n²)이 발생

  • O(n²)이 나오는 경우는 리스트에서 pivot을 가장 왼쪽이나 오른쪽을 잡을 때 발생함

해결책

  • 최악의 경우를 피하기 위해 pivot을 랜덤하게 선택
  • 3개의 pivot을 고른 후, median (중앙값)을 사용
  • Insertion Sort를 사용하여 확인
    • Insertion Sort는 규모가 작고 거의 정렬이 다된 리스트에서 효율적으로 동작

Merge Sort

Quick Sort와 마찬가지로 divide and conquer 


  • split: 주어진 리스트를 두개의 서브 리스트로 완벽하게 쪼갬
  • merge: 두개의 서브리스트를 정렬된 리스트에 합침


예시

예시2

상세 예시

6 5 3 1 8 7 2 4


Split


Merge

1. 6과 5를 비교하여 작은 수를 왼쪽, 큰 수를 오른쪽에 배치하여 길이가 2인 리스트에 저장

2. 나머지 값들도 동일하게 생성


3. [5, 6] 과 [1, 3] 에서 각 리스트의 값을 비교하여 작은 순서대로 길이가 4인 리스트에 저장


4. 나머지 리스트인 [7, 8] , [2, 4]도 동일한 로직으로 적용 

5. 두 리스트에 대해 위의 로직을 적용

6. 정렬 완성


퍼포먼스

O(nlog₂n) 만큼의 속도가 나옴

  • 리스트 내 키의 개수 n * 리스트를 쪼갠 뒤, 합치는 비용 log₂n

    log₂n 번 만큼 어떻게 실행?

    merge sort에서 split은 단순히 반씩 쪼개기 때문에 값의 비교나 각 단계별 비교한 값의 이동 연산이 수행되지 않음


    Merge Sort는 리스트를 반으로 쪼개나가는 형식. 최대 degree는 2라고 볼 수 있어서 binary tree라 볼 수 있다.

    더이상 쪼갤 수 없는 크기만큼 쪼갠다면 node는 1개만 가지게 되므로 위 그림처럼 트리의 높이만큼 실행이 됨. 따라서 트리의 높이 공식인 log₂n 번 만큼 쪼개 나간다는 것을 알 수 있음.

    n 번 만큼 어떻게 비교?

    위의 각 트리의 depth마다 리스트의 크기인 n번 만큼 비교가 일어남.


O(n)개의 저장공간이 필요함

merge sort는 stable sort라고 볼 수 있음

병렬처리가 가능함

external sorting에 적응력이 높음

어레이에 있는 키의 개수 n과 쪼개고 다시 합치는 데에 log₂n만큼 든다.

Stable Sort

서브로 정렬한 결과의 순서가 뒤바뀌지 않을 때 stable sort라 함

  • merge sort, insertion sort, bubble sort

다시 말해 {key:value} 쌍의 값들이 있을 때, 같은 키 값을 가지는 2개 이상의 데이터를 정렬할 때, 기존의 순서가 바뀌지 않으면 stable 이라 하고 아니라면 unstable이라 함

웹 페이지에서 특정 데이터의 정렬된 결과를 항상 동일하게 보여줘야 한다고 할 때, unstable sort는 보여주는 데이터와 연관 없는 데이터가 추가되어도 웹페이지를 새로고침 했을 때 순서가 계속 바뀔 수 있음.

예시


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17

대부분 정렬의 시간복잡도는 O(n·logn)와 O() 사이임

특별한 경우 O(n)까지 가능


Internal sorting - main memory 에서 일어나는 정렬

External sorting - secondary storage(하드디스크) 에서 일어나는 정렬

Bubble Sort

이웃되는 값끼리 비교하여 자리를 변경해나가는 방식

기본적으로 O(n²). 이미 정렬이 되어 있을 경우는 O(n)

예시

예시2

Selection Sort

array에서 가장 큰 수를 찾은 다음, 찾은 수를 어레이의 맨 끝인 n자리에 놓는다.

다음 큰수를 찾은 다음, 어레이의 n-1자리에 넣는다. 이때 찾은 수와 해당 자리에 있는 수의 자리를 바꾼다.

O(n²)의 performance가 나옴

  • bubble sort와 똑같이 O(n²)이지만 bubble sort에 비해 값의 교환 수가 적음

이미 정렬이 되어 있어도 O(n²)임

예시

예시2

Insertion Sort

새로운 키를 넣을 때, 정렬을 하고 있는 어레이에서 자신이 어디에 들어가야 할지 결정한 다음 맞는 자리에 넣는다.


performance: O(n²) 이미 모든 키가 정렬되어 있으면 O(n)

짧은 list에서 단순하고 좋음.
이미 부분적으로 정렬이 되어 있는 경우에 좋다

예시

예시2

Selection Sort vs Insertion Sort

Selection Sort는 정렬되어있지 않은 수를 전부 확인 해 가장 큰 수를 찾아야 함

  • 정렬이 전부 되어 있어도 모든 수를 비교

Insertion Sort는 정확한 위치에 들어가는 것을 결정하기 위해 정렬 중인 어레이를 확인 해야 함

  • 필요한 값만 읽고 정렬된 리스트에서 비교

n개의 element가 있다고 가정할 때, Selection은 n번만 쓰면 됨. 뒤에서부터 쓰기 때문에 어레이의 key들이 이동할 필요가 없지만, Insertion은 key들이 전부 이동할 수도 있기 때문에 write가 더 많이 일어남

  • 예를 들어, 2 3 4 5 1 의 값을 Insertion Sort로 정렬한다고 하면, 마지막 1을 정렬하기 위해 2 3 4 5 의 값이 한 칸씩 이동해야함

만약 write비용이 비쌀 경우 (예를 들어, flash memory) Insertion Sort보단 Selection Sort이 더 좋음

요약

  • bubble, selection, insertion sort의 시간복잡도 worst case는 O(n²)
  • 만약 전부 정렬된 리스트를 비교한다면 bubble, insertion sort는 O(n)이지만 selection은 여전히 O(n²)


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17

Preorder

  • Visit the root.
  • Visit the left-subtree.
  • Visit the right-subtree.

Inorder

  • Visit the left-subtree.
  • Visit the root.
  • Visit the right-subtree.

Postorder

  • Visit the right-subtree.
  • Visit the left-subtree.
  • Visit the root.

Breadth First Search(BFS) or Level order traversals

  • starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

Depth First Search(DFS)

예시


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17

Spanning Tree

N개의 노드들의 connected graph에서 얻을 수 있음

  • depth-first traversal 또는 breadth-first traversal 을 통해 확인
  • N개의 node와 N-1개의 edges로 된 Tree
  • cycle은 그래프로부터 제거됨 - 한번 방문한 노드는 다시 방문하지 않기에 cycle이 생길 수 없음

한개 이상의 spanning tree는 같은 그래프에서 구할 수 있음

추가정보

그래프가 connected 일 때, dfs나 bfs는 암묵적으로 그래프 G의 edge를 두개의 집합으로 분리

  • T(for tree edges): edge의 집합으로 사용되거나 search 도중에 방문
  • N(for nontree edges): 남아있는 edge의 집합
  • T의 edge는 G의 모든 vertex들을 포함하는 트리를 형성

요약

  • Spanning Tree는 G의 edge로만 구성되며 G안의 모든 vertex들을 포함하는 트리
  • 다시말해, 정점집합 v를 그대로 두고 (각 점들을 움직이지 않고) 간선(link)를 v-1개(v개의 link로 연결하면 cycle이 생김)만 남겨 트리가 되도록 만든 것.

Spanning Tree의 이점

  1. spanning tree에 nontree edge를 추가한다면 cycle이 됨

  2. spanning tree는  V(G’) = V(G) 이고 G’는 connected 와 같은 G의 minimum 그래프 G’임

  3. |E(G’)| = n - 1 이라면 |V(G)| = n 임
    • edge를 최소한으로 사용하므로 minimum cost spanning tree 이다.

예시

Depth-First Traversal Search

Breadth-First Traversal Search

Minimum Spanning Tree

N 개의 노드들의 weighted connected 그래프에서 얻을 수 있음

총 weighted가 최소한인 spanning tree

일반적으로 unique가 아님

minimum-cost 문제를 모델링하고 해결하는데 사용됨

어느 노드에서 시작하느냐에 따라 결과가 달라질 수 있음

추가정보

weighted undirected 그래프의 spanning tree 비용

  • spanning tree 안에 있는 edge의 cost(weight)의 합
  • 최소비용의 spanning tree
  • KruskalPrimSollin 알고리즘이 대표
  • greedy method: 단계적으로 최적의 해결책을 구성하고, 어떤 기준을 사용하여 각 단계에서 최적의 결정을 내림

spanning tree는 최소비용을 기준

  • 그래프 안에 있는 edge만을 사용
  • 정확하게 n-1 개의 edge를 사용
  • cycle을 유발할 수 있는 edge는 사용하지 않을 수 있음

요약

  • 각 연결한 link의 edge가 가장 작은 신장트리를 말한다.
  • 여기에 prim's, kruskal's, sollin's algorithm이 대표적이고 이 알고리즘들은 전부 greedy method이다. greedy 방법은 현재의 상황에서 자신이 최선의 선택을 하는 방법을 사용한다.

Prim 알고리즘

  1. 그래프의 node에서 시작
  2. 모든 인접한 node들을 계산
  3. 최소한의 edge의 weight를 선택
  4. 선택된 인접한 노드에서 계속 시작
    • 선택되지 않은 모든 edge를 계산
    • 새로 인접한 모든 edge들을 계산
    • 최소한의 weight를 가진 edge를 선택. 단 cycle은 피함
  5. 그래프의 모든 node들을 포함할 때까지 진행하고 모든 노드는 1번만 방문하도록 고려

추가정보

단일 vertex를 포함하는 T 라는 트리에서 시작

T ∪ {(u,v)}가 트리(cycle은 안됨)가 되도록 T의 최소비용인 edge(u,v)를 추가하고 T가 n-1 edge를 포함할 때까지 이 단계를 반복

알고리즘의 각 단계에서 선택되는 edge의 집합

  • prim 알고리즘은 나무를 형성하고 kruskal 알고리즘은 숲을 형성

요약

  • 어느 한 점을 선택해 해당 점에서 갈 수 있는 최소의 edge를 결정한 다음 잇는다이은 다음 두 점에서 갈 수 있는 최소의 edge를 다시 결정해 잇고 이러한 방식으로 모든 vertex를 이을 때 까지 한다.

예시

위와 같은 그래프를 prim알고리즘을 사용하여 탐색

B-D의 edge를 선택할 경우, cycle이 되기 때문에 선택하지 않음

예시2


위와 같은 그래프를 prim알고리즘을 사용하여 탐색

Kruskal 알고리즘

prim 알고리즘과 다르게 어느 한 vertex를 선택하지 않고 전체 link의 edge중 가장 작은 edge를 찾아 잇는다그 다음 가장 작은 edge를 이어가는 방식

예시

위와 같은 그래프를 kruskal 알고리즘을 사용하여 탐색

Dijkstra 알고리즘

source에서 destination 까지 최단거리는 무엇일까?

Dijkstra 알고리즘은 단일 출발지에서 그래프 이론 안에 있는 가장 짧은 경로 찾기 문제를 해결하는 알고리즘

directed와 undirected 그래프 모두 작동하지만 모든 edge는 양수의 weight를 가져야 함

접근법: greedy 알고리즘

Input: Weighted 그래프 G={E,V} 와 출발지 vertex v∈V이고 모든 edge는 양수

Output: 주어진 출발지 vertex v∈V 에서 다른 모든 vertex까지의 최단 경로 길이 (또는 최단 경로 그 자체)


출발점에서 모든 목적지까지의 가장 짧은 경로를 탐색 - greedy 알고리즘

  • 양수의 edge 비용만 탐색: Dijkstra 알고리즘
  • 음수를 포함한 모든 edge 비용을 탐색: Bellman-ford 알고리즘
  • 모든 pair의 가장 짧은 경로 탐색 (dynamic programming): floyd 알고리즘

기본컨셉

edge가 양수인 길을 선택


(A,B)  (A,C) 이므로 (A,B) 선택

(A,B,C)  (A,C), (A,B,D) 이므로 (A,B,C) 선택

(A,B,D)  (A,B,C,E), (A,B,C,F), (A,B,C,G) 이므로 (A,B,D) 선택

위와 같은 방법으로 A에서 모든 vertex까지의 모든 경로를 찾을때까지 반복

기본컨셉설명

  1. S는 가장 짧은 경로를 가지는 v0을 포함하는 vertex들의 집합을 나타내도록 함
  2. S가 아닌 w의 경우, dist[w]는 v0에서 출발해 S의 vertex들을 지나고 w로 끝나는 최단 경로의 길이라고 나타냄
  3. S 안에 있지 않은 vertex u를 찾을 수 있고 dist[u]는 minimum이고 S안에 u를 추가함
  4. 경로를 적절하게 유지


해당 알고리즘의 시간복잡도는 (|V|2)

예시

A 에서부터 시작

요약

  • 시작점에서 모든 도착점까지 가장 짧은 path의 cost를 찾는 알고리즘.


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15

Graph

트리는 그래프의 특수한 케이스

그래프는 다양한 문제를 모델링 하는 것과 문제를 해결하기 위해 알고리즘을 고안하는데 유용


용어

vertex, vertices(vertex의 복수형): 트리의 Node와 동일개념

  • root node와 leaf node가 아닌 모든 노드

edge: 트리의 link와 동일개념

  • undirected edge ( = undirected graph)
  • directed edge ( = directed graph)
    • 단방향, 양방향
    • in-degree (해당노드로 들어오는 방향성 있는 edge), out-degree (해당노드에서 나가는 방향성 있는 edge)
  • weighted edge ( = (directed or undirected) weighted graph)
    • 서울 - 제주도 와 서울 - LA의 weight는 다름

정의1

graph G=(V,E)


V(G): empty가 없는 vertex들의 유한한 집합

  • v1, v2, ..., vi, vj, ... ∈ V(G)

E(G): empty가 가능한 유한한 edge들의 집합

  • (vi, vj) ∈ E(G) 이면 vi, vj ∈ V(G)

undirected graph

  • (vi,vj) = (vj,vi)

directed graph ordered

  • <vi,vj> ≠ <vj,vi>

집합의 표현 예시

V(G1) = {0,1,2,3}; E(G1) = {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}

V(G2) = {0,1,2,3,4,5,6}; E(G2) = {(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}

V(G3) = {0,1,2}; E(G3) = {<0,1>,<1,0>,<1,2>}

예시

상세

degree (of a vertex): vertex에 인접한 edge의 수

in-degree (of a vertex v): 방향성 있는 edge가 vertex를 향하고 있는 edge의 수

out-degree (of a vertex v): 방향성 있는 edge가 vertex에서 나가고 있는 edge의 수

그래프 제한사항

vertex에 edge가 없거나 자기자신을 가리키는 edge는 없음

하나의 vertex에서 다른 vertex를 연결하는 edge가 중복인 경우는 없음 (<=> multigraph)

정의2

  • subgraph: 그래프의 한 부분

  • connected graph: 모든 vertex가 연결된 그래프

  • disconnected graph: 한개의 vertex라도 연결되어 있지 않는 그래프

  • adjacent nodes: 인접한 vertex간 연결되어 있는 node 관계

  • complete (connected) graph: 모든 vertex가 adjacent node로 표현이 가능한 그래프. 전부 연결되어 있으므로 connected graph임

예시

정의3

  • path: vertex X에서 vertex Y까지 가는 edge의 연결된 경로
    • 아래 그림에서 A에서 D까지 가는 경로는 (A,B), (B,C), (C,D) 이므로 length=3임
  • cycle: 출발한 노드 다시 도착할 수 있는 구조
    • 아래 그림에서 ABCDA는 cycle 구조
  • cyclic graph: cycle 구조가 존재하는 그래프
  • acyclic graph: cycle 구조가 존재하지 않는 구조 (=tree)

예시

그래프 표현방식

Adjacency Matrix

(n x n) 2차원 배열 - (vertex)(edge)로 표현

  • n은 그래프 안에 존재하는 노드의 개수

만약 v1가 v2가 adjacent하다면 1로 표현하고 그렇지 않으면 0으로 표현




예시

장점

공간절감

방향성이 없는 그래프일 때, 공간의 절반을 절약할 수 있음

저장할 때, 위 또는 아래의 삼각형모양의 데이터만 저장하면 됨

방향성이 없는 그래프일 때, vertex i의 degree를 구하는 공식은  임

그래프 탐색방법

그래프에서 모든 vertex를 방문하는 방법은 아래와 같음

  • depth-first traversal
  • breadth-first traversal

Depth-First Traversal

  1. 한 노드에서 더이상 새로운 인접한 노드가 없을 때까지, 인접한 노드를 재귀적으로 방문하는 방법
  2. 재귀적으로 실행한 다음, 뒤로 돌아갈 때, 다음 새로운 인접한 노드를 재귀적으로 방문
  3. 처음 시작한 노드에서의 인접한 노드를 재귀적으로 전부 방문했다면 종료

방문 순서의 방법은 preorder tree traversal 과 유사


재귀적으로 실행되는 순서는 stack을 사용하여 구현하면 쉽다!

adjacent matrix로 구현한다고 하면 시간복잡도는 O(n2)임

예시


방문경로

Breadth-First Traversal

  1. 시작노드에서 인접한 노드를 한번 방문함
  2. 그 다음, 한번도 방문하지 않은 모든 인접한 노드를 방문
  3. 모든 노드를 방문했다면 종료

방문 순서의 방법은 level-order tree traversal 과 유사함

queue를 사용하여 구현하면 쉽다!

adjacent matrix로 구현한다고 하면 시간복잡도는 O(n2)임

예시

방문경로

'공부 > 자료구조' 카테고리의 다른 글

트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13

비트코인과 이더리움 블록 비교

비트코인의 블록은 헤더와 바디로 나누어 볼 수 있습니다. 이더리움도 비트코인의 블록구조와 크게 다르진 않지만 블록의 헤더부분에 uncle_list와 stack_trace 라는 값이 추가되어 있는 형태입니다.


  • uncle list: 비트코인의 이전블록을 이더리움에서 parent 블록이라고 말하기 때문에 생긴 용어. stale 블록을 uncle 블록이라 칭함 (자세한 설명은 아래에서)

비트코인과 이더리움 블록헤더 비교


비트코인이더리움
블록해시hashstate_root
이전 블록해시prev_lbockparent_hash
거래관련된 루트해시mrkl_root

TRIEHASH(transaction_list)

TRIEHASH(uncle_list)

TRIEHASH(stack_trace)

난이도bitsdifficulty
타임스탬프timetimestamp
넌스noncenonce
그외 데이터

size

ver

n_tx

extra_data

(block) numbber

coinbase address (채굴주소)

.... 등등

비트코인과 블록헤더의 구조는 거의 유사하나 블록해시를 구할 때, 몇 가지 항목이 더 추가됨

  • uncle_list, stack_trace, extra_data 등등

이더리움 블록 구성

위에서 비트코인과 간략하게 비교했으니 이제 이더리움만 자세하게 파봅시다.



https://etherscan.io/block/5529581 해당 주소에서 이더리움의 블록정보를 확인한 정보입니다.


이더리움의 코드(GO)를 보면 아래와 같이 블록과 블록헤더가 struct로 선언되어 있습니다.

블록

// Block represents an entire block in the Ethereum blockchain.
type Block struct {
	header       *Header
	uncles       []*Header
	transactions Transactions
	// caches
	hash atomic.Value
	size atomic.Value
	// Td is used by package core to store the total difficulty
	// of the chain up to and including the block.
	td *big.Int
	// These fields are used by package eth to track
	// inter-peer block relay.
	ReceivedAt   time.Time
	ReceivedFrom interface{}
}

블록헤더

// Header represents a block header in the Ethereum blockchain.
type Header struct {
	ParentHash  common.Hash    `json:"parentHash"       gencodec:"required"`
	UncleHash   common.Hash    `json:"sha3Uncles"       gencodec:"required"`
	Coinbase    common.Address `json:"miner"            gencodec:"required"`
	Root        common.Hash    `json:"stateRoot"        gencodec:"required"`
	TxHash      common.Hash    `json:"transactionsRoot" gencodec:"required"`
	ReceiptHash common.Hash    `json:"receiptsRoot"     gencodec:"required"`
	Bloom       Bloom          `json:"logsBloom"        gencodec:"required"`
	Difficulty  *big.Int       `json:"difficulty"       gencodec:"required"`
	Number      *big.Int       `json:"number"           gencodec:"required"`
	GasLimit    uint64         `json:"gasLimit"         gencodec:"required"`
	GasUsed     uint64         `json:"gasUsed"          gencodec:"required"`
	Time        *big.Int       `json:"timestamp"        gencodec:"required"`
	Extra       []byte         `json:"extraData"        gencodec:"required"`
	MixDigest   common.Hash    `json:"mixHash"          gencodec:"required"`
	Nonce       BlockNonce     `json:"nonce"            gencodec:"required"`
}

블록헤더 설명

  • ParentHash : 부모 블록의 해시값
  • UncleHash : 현재 블록의 엉클 블록들의 해시값
  • Coinbase : 채굴 후 해당 트랜잭션의 수수료를 받을 계정 주소
  • Root: 계정의 상태정보가 모여있는 머클 패트리시아 트리의 루트 노드 해시값
  • TxHash: 블록의 모든 트랜잭션에 대한 머클트리의 루트노드 해시값
  • ReceiptHash: 블록 내 모든 트랜잭션에 대한 receipt들의 머클트리의 루트노드 해시값
  • Bloom: 로그 정보를 사용하는데 사용하는 32바이트 블룸필터
  • Difficulty: 블록 난이도로 이전블록의 난이도와 타임스탬프로 계산
  • Number : 현재 블록번호
  • GasLimit: 블록당 지급가능한 최대 가스 총합
  • GasUsed: 블록내 트랜잭션에 사용된 가스의 총합
  • Time : 블록의 최초 생성시간
  • Extra : 블록의 기타정보
  • MixDigestNonce : 작업증명에서 해시값을 계산하는데 충분한 계산횟수를 보장하기 위해 사용하는 값


Root, TxHash, ReceiptHash는 머클트리의 각 노드를 해시한 최종 루트해시값에 해당하고 나머지 값들은 각각 하나의 상수로 볼수 있습니다.


제네시스 블록

제네시스 블록은 블록의 첫번째에 위치하는 최초 블록을 말하며 블록번호 0번에 해당되고 어떤 트랜잭션도 포함되지 않습니다.

// Genesis specifies the header fields, state of a genesis block. It also defines hard
// fork switch-over blocks through the chain configuration.
type Genesis struct {
	Config     *params.ChainConfig `json:"config"`
	Nonce      uint64              `json:"nonce"`
	Timestamp  uint64              `json:"timestamp"`
	ExtraData  []byte              `json:"extraData"`
	GasLimit   uint64              `json:"gasLimit"   gencodec:"required"`
	Difficulty *big.Int            `json:"difficulty" gencodec:"required"`
	Mixhash    common.Hash         `json:"mixHash"`
	Coinbase   common.Address      `json:"coinbase"`
	Alloc      GenesisAlloc        `json:"alloc"      gencodec:"required"`
	// These fields are used for consensus tests. Please don't use them
	// in actual genesis blocks.
	Number     uint64      `json:"number"`
	GasUsed    uint64      `json:"gasUsed"`
	ParentHash common.Hash `json:"parentHash"`
}

제네시스 블록 설명

  • Alloc : 일정량의 이더를 초기 계정에 할당할때 사용하는 값으로 채굴작업 없이 초기 일정량의 이더를 발생하여 ICO를 통해 판매하는데 사용할수 있음
  • Coinbase : 채굴 후 보상코인을 수령할 주소인데 제네시스 블록에서는 채굴이 일어나지 않기에 어떠한 값을 할당해도 상관없음
  • Nonce : mixhash와 함께 채굴 시에 사용되는 값, 8바이트
  • Mixhash : Nonce와 함께 채굴 시에 사용되는 값, 32바이트
  • Difficulty : 채굴시의 목표값
  • ExtraData : 32바이트 옵션항목
  • GasLimit : 블록의 최대 가스량
  • ParentHash : 이전 부모블록의 해시값, 제네시스블록은 부모가 없기 때문에 0으로 할당
  • TimeStamp : 블록의 생성시간

이더리움 블록체인과 채굴

비트코인: 거래(이체) 데이터 저장방식 (거래정보만 블록에 저장)

이더리움: 계정 데이터 저장방식 (모든 계정정보를 저장)

  • 계정의 balance등의 정보를 직접변경
  • patricia tree를 사용하여 저장 데이터의 용량을 줄임


위와 같이 이더리움 블록체인은 비트코인과 유사하나 다른점이 존재합니다. 비트코인과는 달리 이더리움 블록은 transaction list와 가장 최근의 상태(state) 복사본을 가지고 있다는 것입니다. 이외에도 블록의 넘버와 difficulty 또한 블록 내에 저장됩니다. 기본적인 이더리움 블록 검증 알고리즘은 아래와 같습니다.


  1. 참조하고 있는 이전 블록이 존재하는지와 유효한지 확인
  2. 현재 블록의 타임스탬프가 참조하고 있는 이전 블록의 타임스탬프보다 크고 현 시점을 기준으로 15분 후보다 작은 값인지 확인
  3. 블록 넘버, difficulty, 트랜잭션 루트, uncle 루트, gas limit등이 유효한지 확인
  4. 블록에 포함된 작업 증명이 유효한지 확인
  5. 위 그림의 S[0] 이 이전 블록의 마지막 상태(state)라고 가정
    1. TX를 현재 블록의 n개의 트랜잭션 리스트라고 가정하고 0 부터 n-1에 대해, S[i+1] = APPLY(S[i], TX[i]) 로 설정했을 때, 어플리케이션이 오류를 반환하거나, 이 시점까지 블록에서 소모된 총 gas가 GASLIMIT를 초과하면 오류를 반환
  6. 채굴자에게 지불된 보상 블록을 S[n] 덧붙인 후 이것을 S_FINAL 이라 가정
    1. 상태 S_FINAL의 머클 트리 루트가 블록 헤더가 가지고 있는 최종 상태 루트와 같은지를 검증. 이 값이 같으면 그 블록은 유효한 블록이고 다르면 유효하지 않은 것으로 판단

이러한 접근은 모든 상태를 각 블록에 저장할 필요성 때문에 매우 비효율적인 것처럼 보이지만, 실제로는 효율성의 측면에서는 비트코인과 비교할만 합니다. 그 이유는 상태가 트리 구조로 저장되고, 모든 블록 후에 단지 트리의 작은 부분만이 변경되기 때문입니다. 보통 인접한 두 개의 블록간에는 트리의 대부분의 내용이 같아서 한번 데이터가 저장되면 포인터(서브트리의 해쉬)를 사용하여 참조될 수 있기 때문입니다. 패트리시아 트리(Patricia tree)로 알려진 이러한 종류의 특별한 트리는 머클 트리 개념을 수정하여 노드를 수정할 뿐만 아니라, 효율적으로 삽입되거나 삭제하여 이러한 작업을 수행할 수 있도록 해줍니다. 또한, 모든 상태 정보가 마지막 블록에 포함되어 있기 때문에, 전체 블록체인 히스토리를 모두 저장할 필요가 없어지게 됩니다. 이러한 방법으로 비트코인에 적용된 기술과 비교하면 5~20배의 저장 공간 절약의 효과가 생깁니다.

물리적인 하드웨어 관점에서 볼 때, 컨트랙트 코드는 “어디에서" 실행되는가 하는 의문이 쉽게 들 수 있습니다. 컨트랙트 코드를 실행하는 프로세스는 상태 전환 함수 정의의 한 부분이고, 이것은 블록 검증 알고리즘의 부분이므로, 트랜잭션이 블록 B에 포함되면 그 트랜잭션에 의해 발생할 코드의 실행은 블록 B를 다운로드 하고 검증하는 모든 노드들에 의해 실행됩니다.

엉클블록

동시에 블록이 생성되어 전파되는경우 블록의 유효성 검증은 통과되었지만, 블록의 난이도가 상대적으로 낮아 블록으로 채택되지못한 블록을 엉클블록이라고 합니다. 엉클블록이 많아지만 다음과 같은 문제가 발생합니다.

  1.  엉클블록에 포함된 트랜잭션은 처리가 되지않기 때문에 트랜잭션처리의 지연문제가 발생
  2. 엉클블록은 체인에 연결되지않기 때문에 엉클블록을 발견하는데 사용된 컴퓨팅파워가 낭비되는 문제가 발생
  3. 엉클블록이 생성된 후 다음 블록이 생성되면 평균 블록 생성시간이 늘어나 블록생성 난이도가 낮아지기 때문에 네트워크 보안수준을 떨어뜨리게 됨

이더리움은 이러한 문제를 고스트 알고리즘을 사용하여 해결하였습니다. 고스트 알고리즘은 다음 번에 설명하겠습니다.


BST에서 위와 같은 Skewed Tree의 경우 복잡도가 O(n)이 나오는 한계점을 해결하기 위해 AVL Tree가 고안됨. AVL 은 해당 자료구조를 만든 사람의 앞글자를 하나씩 따서 만든 것(..)

AVL Tree 예시

AVL Tree

Not AVL Tree

용어

  • 노드의 height: h
  • balance factor: bf (왼쪽 서브트리의 height - 오른쪽 서브트리의 hegiht)
  • empty height: -1

특징

  • AVL 트리는 BST이면서 동시에 균형을 유지하고 있음
  • 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 (왼쪽과 오른쪽 서브트리의 height 계산 결과가 1, 0, -1 이외라면 해당 트리는 AVL 트리가 아님 - 만약 height가 없는 경우는 -1)
    • 즉, 모든 노드들은 balance factor 를 알고 있음
  • 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장

문제는 이러한 균형을 맞추려 하다 보니 유지하는 방법이 복잡함. 예를 들어, 노드 삽입이나 삭제로 인해 왼쪽과 오른쪽 서브트리의 height의 계산결과가 2, -2가 나온 경우, 트리를 rotation 시켜줘야 함


rotation에는 2가지 관점이 있는데 AVL 트리를 height balance로 유지하는 것과 binary search tree로 유지하는 관점이 있음. 관점은 나뉘어 있지만 가장 중요한 것은 rotation 시키면서 트리의 height를 낮춰야 복잡도가 줄어듦

rotation의 방법은 4가지로 1번만 rotation 시키는 LL, RR와 2번 rotation 시키는 LR, RL이 존재.


Single Rotation

LL (Right)


왼쪽은 차이가 2이고 오른쪽은 0이므로 왼쪽이 무너진 경우. 이 경우는 오른쪽으로 트리를 회전시켜주면 해결

RR (Left)


왼쪽은 차이가 0이고 오른쪽은 2이므로 오른쪽이 무너진 경우. 이 경우는 왼쪽쪽으로 트리를 회전시켜주면 해결

Double Rotation

위에서 본 LL, RR과는 달리 방향이 일정하지가 않기 때문에 첫 회전에서는 LL 또는 RR로 방향을 맞춘 다음 다시 회전시켜 높이의 균형을 유지시켜줌

RL (Right & Left)


가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 RR의 형태를 이루기 때문에 자리를 바꾼 후, RR 로 회전을 한번 더 시킴.

LR(Left & Right)

가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 LL의 형태를 이루기 때문에 자리를 바꾼 후, LL 로 회전을 한번 더 시킴.

장단점

  • 검색, 삽입, 삭제 모두 O(logN)이며 항상 균형을 맞춤
  • 프로그래밍하기가 어렵고 디버깅 또한 어려움.
  • 위 검색, 삽입, 삭제가 빠르긴 하지만 균형을 맞추는데에 시간이 듦
  • 대규모 tree를 이룬 후 검색하는 것은 DB에서 주로 발생하는데 DB는 이미 B-Tree 자료구조를 사용 중임


'공부 > 자료구조' 카테고리의 다른 글

Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01

Binary Search Tree(BST - 이진검색트리) 는 비어있거나 아래의 속성을 만족하는 binary tree 입니다. 자세하게 Binary Search (이진 검색)과 Linked List를 결합한 자료구조입니다. 이진 검색의 검색능력을 유지하면서 빈번한 값의 삽입, 삭제가 가능하도록 고안되었습니다. 이진검색의 경우 검색에 소요되는 시간복잡도는 O(log₂n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. linked list의 경우 자료 입력, 삭제에 필요한 시간복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 복잡도가 발생합니다.

정의

  1. 각각의 모든 node 들의 key는 중복된 값이 아님 (unique)
  2. 기존의 binary tree는 순서가 없지만 BST는 순서가 존재
  3. parent node의 왼쪽은 부모보다 작은 값이고 오른쪽은 부모보다 큰 값임
  4. 왼쪽, 오른쪽의 서브 트리또한 BST임

Search

  1. 찾고자 하는 Key와 root node값이 같으면 성공
  2. Key가 root node 값보다 작다면 (key < root node) 왼쪽의 sub tree로 이동
  3. Key가 root node 값보다 작다면 (key > root node) 오른쪽의 sub tree로 이동
  4. 1~3번 반복
  5. 만약 조건에 맞는 데이터가 없으면 실패 (tree에 값이 존재하지 않는 경우)


위 그림에서 120 값을 찾는 예시입니다. 

  1.  root node(=100)와 찾고자 하는 값 (=120) 비교
  2. root node보다 찾고자 하는 값이 더 크므로 (100 < 120) 오른쪽 subtree로 이동
  3. 오른쪽 subtree의 노드값(=150)과 찾고자 하는 값(=120)과 비교
  4. 찾고자 하는 값이 더 작으므로 (150 > 120) 왼쪽 subtree로 이동
  5. 120값이므로 검색 성공


Insert

값을 삽입하고자 하거나 찾고자 하는 값이 없을 경우 루트노드에서 시작, 값을 비교해가면서 tree의 가장 마지막까지 간 다음 값을 입력

예시

위 그림에서 80을 넣고자 하면 아래와 같은 위치에 삽입


Delete

  1. 첫 단계는 지우고자 하는 값이 해당 tree에 있는지 search
  2. 지우고자 하는 값이 leaft node(가장 마지막)에 위치해있으면, 그냥 지우면 됨
  3. internal node라면 다음과 같이 분기가 됨
    1. 지워야 하는 node가 child node를 1개 가지고 있는 경우, internal node를 지운 후 해당자리에 child node를 옮김
    2. 지워야 하는 node가 child node를 2개 가지고 있는 경우, 왼쪽의 subtree에서 가증 큰 노드 또는 오른쪽 subtree에서 가장 작은 노드를 옮김

예시

50 (leaf node) 삭제


75 (internal node 이며 1개의 child node 존재) 삭제


150 (internal node 이며 2 child node 존재) 삭제

1. 왼쪽의 subtree에서 가장 큰 노드를 이동


2. 오른쪽 subtree에서 가장 작은 노드를 이동



internal node이며 child node를 2개 가지고 있는 경우 삭제하는 방법은 2가지가 있지만 여기서 조건적으로 효율적인 방법이 존재.

1, 2번의 방법 중 트리의 height를 줄일 수 있는 방법을 채택하는 것이 향후 트리 검색의 속도를 향상시킬 수 있음

복잡도

BST는 검색, 삽입, 삭제 모두 O(h)임. h는 BST의 높이(height)

BST에서는 inorder(LVR) 검색 방식을 사용

BST는 평균(최상) 시간복잡도가 O(log₂n)이지만 최악의 경우 O(n)임. (skewed tree이면 node의 수만큼 시간이 소요됨)

  • tree가 complete binary tree거나 full binary tree이면 O(log₂n), skewed tree이면 O(n)

위 O(N)의 경우때문에 노드가 얼마 되지 않아도 검색속도가 나오지 않을 가능성이 존재함. 이 때문에 AVL Tree가 고안됨


'공부 > 자료구조' 카테고리의 다른 글

Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
  • Heap은 Complete Binary Tree를 기본으로 가지는 자료구조
  • 일반적으로 array로 구현하는 것이 좋음
  • Heap 은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨
  • 시간복잡도: O(log₂N)
  • Heap은 다음과 같은 속성(property)를 만족함
    • A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립
  • 종종 priority queue를 보충하는대에 사용

종류

max heap: root노드가 가장 큰 수

min heap: root노드가 가장 작은 수

Max Heap

부모노드의 키가 자식노드의 키보다 항상 큼


Node Insertion

max heap에서 노드 추가는 말단의 맨 오른쪽의 leaf node에 자리를 하나 만들고 해당 노드에 값을 대입한 다음 parent node와 값을 비교하며 자리를 바꿔 나감. (root node 까지)

Node Deletion

max heap에서 노드 삭제는 항상 루트노드를 지움. 그 다음 complete binary tree를 유지하기 위해 tree를 재조정함. 말단의 맨 오른쪽 노드를 지운 다음, 루트 노드 자리에 옮기고 child node와 비교해 자리를 바꿔나감.


Max Heap에서 노드 추가, 삭제는 모두 트리의 depth만큼 걸림 -> O(log₂N)

Min Heap

부모노드의 키가 자식노드의 키보다 항상 작음



키의 대소관계는 오로지 부모노드와 자식노드 간에만 성립되며, 형제(sibling) 사이에는 대소관계가 정해지지 않음

Priority Queue

일반적인 queue는 FIFO 이기 때문에 먼저 들어온 데이터가 먼저 나가지만, priority queue는 우선순위가 높은 데이터 먼저 나감

새로운 노드가 삽입되면 우선순위에 맞는 위치에 삽입 (enqueue)

제거할 때는 우선순위가 가장 높은 맨 앞의 노드를 삭제 (dequeue)



'공부 > 자료구조' 카테고리의 다른 글

AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30

+ Recent posts