해시란?

해시란 탐색, 삽입, 삭제를 모두 O(1) 기대 시간에 수행할 수 있도록 해 주는 기법입니다.
해시는 해시 테이블을 통해 구현되며 해시 테이블은 b개의 버킷 과 버킷 내에 s개의 사전쌍들로 이루어 집니다.
여기서 해시함수 h는 키 값을 특정 홈 주소로 사상 시키는 함수로써 주로 제산 함수 등이 사용됩니다.

h(k) = 0 ~ (b-1)

위 식에서 h(k)를 해시 혹은 홈 주소 라고 부릅니다.

이상적인 조건 하에서 모든 사전쌍들이 모두 홈 버킷에 저장됩니다.

이런 해시 테이블에 있는 쌍의 수를 n 개라 하고, 가능한 전체 키의 총 개수를 T라 할때

키 밀도 = n/T

위 식이 성립합니다.

이러한 해시 함수는 여러 개의 키를 하나의 버킷에 사상시키게 되기 때문에
h(k1) = h(k2) 가 되는 k1과 k2가 존재하게 되고 이 경우 k1과 k2를 h에 대한 동거자라고 부릅니다.

오버플로우 란 어떤 쌍을 삽입 시 홈 버킷이 넘치는 경우를 말합니다.

정적 해싱

오버플로우 처리방법에는 개방 주소법과 체인법 이 있으며, 개방 주소법 에는 선형 조사법, 이차 조사법, 재해싱, 임의 조사법이 있습니다.

오버플로우 처리법

개방 주소법

선형 조사법

체인법

선형 조사법을 비롯한 개방 주소법에서는 키를 탐색 할 때 서로 다른 해시 값을 가진 키들과 일일히 비교를 수행하기 때문에 효율이 매우 떨어집니다.
이와 달리 체인법 에서는 ht[i] 가 버킷 i에 연결된 체인들 중 첫번째 블록을 가리키고 있기 때문에, 연결된 체인 내에서만 탐색을 수행하면 되어 속도가 빠릅니다.

동적 해싱

재조정을 한 번 할 때마다 오직 하나의 버킷만 재조정함

디렉터리 사용 동적 해싱

디렉터리 미사용 동적 해싱

스택을 활용한 수식의 계산

모든 프로그래밍 언어는 연산 순위를 결정해야한다.
일반적으로 실생활 에서는 x+y 와 같이 연산자를 피연산자 사이에 작성하는 중위 표기법(infix notation) 을 사용하지만, 컴퓨터의 컴파일러는 후위 표기법(postfix notation) 으로 코드를 변환하기에 컴퓨터의 연산과정을 이해하기 위해서 후기 표현법 에 대해 익숙해질 필요가 있습니다.

후위 표기식 연산법

1. 연산자를 만날때까지 피연산자를 스택에 저장
2. 연산자를 만나면 연산에 필요한 만큼만 스택에서 가져와 실행하여 연산결과를 다시 스택에 저장

중위 표기식을 후위 표기식으로 고치는 법

1. 식을 모두 괄호식으로 고침
2. 연산자를 모두 해당하는 오른 괄호랑 대체
3. 모들 괄호를 삭제

• 그래프 추상 데이타 타입
• 그래프 표현법
• 그래프의 기본 연산
  • 깊이 우선 탐색(DFS)
  • 너비 우선 탐색(BFS)
  • 신장 트리(spanning tree)
• 최소 비용 신장 트리
  • Kruskal 알고리즘
  • Prim 알고리즘
• 최단 경로와 이행적 폐쇄
  • Dijkstra 알고리즘, 하나의 출발점에서 모든 목표점: 음이 아닌 간선 비용의 경우

그래프 추상 데이타 타입

가령 여러 지점과 그 지점들을 잊는 길들 처럼 현실 세계의 많은 문제들은 그래프 라는 개념을 통해 해결될 수 있습니다.

그래프 G 는 2개의 집합 V와 E로 구성됩니다. V는 공집합이 아닌 정점(Vertice) 들의 유한 집합이며, G는 정점 쌍들의 집합으로 이러한 쌍을 간선 이라 합니다. V(G) 와 E(G)는 각 각 정점과 간선들의 집합을 의미합니다. 그래프는 정점에서 특정 정점으로 가는데에 방향의 개념이 존재하는 경우와 존재하지 않는 경우로 나눌 수 있으며, 이렇게 정점에서 정점으로 이동시 방향이 있는 경우를 방향 그래프(directed graph) 라고 하며, 방향이 없는 경우 무방향 그래프(undirected graph) 라고 합니다.

여기서 정점에 연결된 간선의 수를 차수 라고 하며, Euler는 각 정점의 차수가 짝수 인 경우에만 임의의 정점에서 출발하여 각 간선을 단 한 번씩만 거치고 출발한 정점으로 되돌아오는 길이 있음을 보였으며, 이를 오일러 행로(Eulerian Walk) 라 부릅니다.

그래프 표현법

무방향 그래프의 간선 (u, v)
방향 그래프의 간선 <u, v>

그래프의 기본 연산

깊이 우선 탐색(DFS)

위처럼 인접 리스트 표현법의 경우 간선의 횟수 만큼만 탐색이 진행되므로, O(e) 의 복잡도를 가진다.
하지만 인접 매트릭스 표현으로 표현한 경우 각 정점마다 다른 정점들과 비교해야 하므로 O(n^2) 의 복잡도를 가진다.

너비 우선 탐색(BFS)

시간 복잡도: O(n^2)

신장 트리(spanning tree)

신장 트리란 G의 간선들로만 구성되고 G의 모든 정점을 포함하는 트리를 말합니다.
신장 트리를 만들기 위해서는 DFS 혹은 BFS를 모두 이용할 수 있으며, DFS를 이용하여 만들어진 신장트리를 깊이 우선 신장 트리(depth first spanning tree) 라 하고, BFS를 이용하여 만들어진 신장 트리를 너비 우선 신장 트리(breath first spanning tree) 라 부릅니다.

최소 비용 신장 트리

가중치가 부여된 무방향 그래프의 신장 트리의 비용은 신장 트리를 구성하는 간선들의 비용의 합이 됩니다. 여기서 최소 비용 신장 트리 란 최저의 비용을 갖는 신장트리를 의미합니다.

이 경우 다음의 조건을 만족해야 합니다.

1. 그래프 내에 있는 간선만을 사용해야 한다.
2. 정확히 n-1개의 간선만을 사용해야 한다.
3. 사이클을 생성하는 간선은 사용하면 안된다.

Kruskal 알고리즘

Prim 알고리즘

최단 경로와 이행적 폐쇄

현대의 많은 지도 시스템들은 임의의 두 특정 지점 사이의 경로를 탐색하는 많은 시스템 중의 일부입니다. 경로 탐색 시스템은 일반적으로 주나 전국의 도로 시스템을 표현하기 위하여 그래프를 이용합니다. 이러한 문제에서 도시 A에서 도시 B로 가려는 운전자는 다음과 같은 사항들이 궁금할 것입니다.

1. A로 부터 B로 가는 길이 있는가?
2. A로부터 B로 가는 길이 2갱 이상이라면, 어느 길이 최단으로 가는 길인가?

Dijkstra 알고리즘, 하나의 출발점에서 모든 목표점: 음이 아닌 간선 비용의 경우

다이크스트라 알고리즘

m-원 탐색트리란 무엇인가?

B-트리를 배우기 전에 그 근본 개념이 되는 m-원 탐색트리에 대해 알아봅시다.
기존의 이진 탐색트리 에서 균형 이진 탐색트리인 AVL 트리의 경우 n 개의 노드에 대해서 깊이가 최소 logn에 가깝기 때문에, 실제 시스템에서 AVL 구조로 저장된 데이터에 접근하기 위해서는 만약 모든 노드가 다른 메모리 안에 들어 있다면 최악의 경우 logn번 만큼 메모리 혹은 디스크에 접근을 해야 했습니다.

이렇게 수 차례에 걸쳐 메모리 혹은 디스크에 접근하는 것은 치명적인 탐색 시간 상승을 야기했고, 이에 탐색 트리의 높이를 줄여 탐색시간을 줄이기 위한 많은 노력들이 있었고, 이를 위해서는 필수적으로 트리의 차수가 증가 해야 했습니다. m-원 탐색트리는 m개의 차수를 가지는 노드들로 구성된 트리이며, 실제로는 트리 노드들이 하나의 캐시 블록이나 디스크 블록을 체울 수 있는 가장 큰 차수를 사용하고 있습니다.

m-원 탐색트리의 정의는 다음과 같습니다.

m-원 탐색트리의 정의

m-원 탐색트리의 예시

B-트리란?

B-트리는 이러한 m-원 탐색트리의 일종이며 다음과 같이 정의됩니다.

차수가 m인 B-트리의 정의

B-트리의 예시

B-트리의 삽입

B-트리의 삭제

키가 x인 노드를 삭제하려고 할 때, x가 리프가 아닌 노드 z에서 발견될 경우, z에서 x가 차지하던 자리는 B-트리의 리프 노드로 부터 적당한 키로 채워진다. 가령 x가 그의 i번째 키라고 하면, E_i는 서브트리 A_i 내의 가장 작은 원소 혹은 서브트리 A_(i-1)의 가장 큰 원소로 채워질 수 있습니다. 여기서 삭제되는 리프노드 p에 대해 다음의 4가지 경우가 존재합니다.

CASE1

p 또한 루트노드인 경우
삭제 후 리프에 적어도 키가 하나 남아있다면 삭제 후 저장하고, 없다면 공백트리가 됩니다.

CASE2

삭제 후 p가 적어도 [m/2]-1 개의 원소를 가지고 있는 경우 즉, 최소 원소 개수가 만족되는 경우
그대로 삭제를 진행

CASE3 회전

p가 [m/2]-2개의 원소를 가지며, 인접한 형제노드 q가 적어도 [m/2]개 원소를 가지는 경우. 즉, p가 삭제 후 최소 키보다 적은 키를 가지고 있고 형제 노드는 최소 키 이상의 키를 가지고 있는 경우
다음과 같이 회전 을 진행합니다.

CASE4 병합

p가 [m/2]-2개의 원소를 가지고 있고, 가장 가까운 형제노드 q가 [m/2]-1개의 원소를 가지고 있는 경우. 즉, p가 삭제 후 최소 키보다 적은 키를 가지고 있고 형제 노드도 딱 최소 키만을 가지고 있는 경우
p,q와 p,q 중간 원소 E_i를 하나의 노드로 병합 합니다.

개요

컴퓨터 안에는 수십 수만가지의 데이터 들이 있으며, 이러한 수많은 데이터들을 잘 정리하고 보관하는 것은 빠른 데이터 찾기와 데이터 추가 및 삭제 등의 작업의 효율에 매우 큰 영향을 미친다. 때문에 컴퓨터의 많은 자료들을 효율적으로 분류하고 원하는 자료를 찾고 추가 하기 위해서는 ‘정렬’에 대해 알아야 할 필요가 있다.

본 강의에서 리스트 란 하나 이상의 필드로 된 레코드의 집합이라는 의미로 사용하며, 이때 코드를 서로 구별하기 위해 사용되는 필드를 키 라고 한다.

일반적인 자료의 탐색 방법

흔히 리스트를 탐색하는 가장 직관적인 방법은 앞에서 부터 차례대로 비교하면서 자료를 분류하는 것이다.
프로그래밍에서 for 문을 사용하여 리스트의 제일 앞에서 부터 뒤까지 훑어 가면서 equal 문을 통해 데이터를 찾는 작업은 매우 흔한 프로그래밍의 구현이다.

이렇게 어떤 리스트의 왼편에서 오른편으로 차례대로 데이터를 찾는 것을 순차 탐색 이라고 한다.

다음 C 언어로 순차탐색 프로그램을 구현한 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>
using namespace std;

struct Element
{
  public:
    string key;
};

int seqSearch(Element elements[], string key)
{
    int i;
    int count = sizeof(*elements) / sizeof(elements[0]);
    cout << "address of the elements: " << elements << endl;
    cout << "count is: " << count << endl;
    for (i = 0; i < count; i++)
    {
        if (elements[i].key == key)
        {
            return i;
        };
    };
    return 0;
};

int main(void)
{
    Element element1 = {"123"};
    Element element2 = {"namhoon"};
    Element elements[] = {element1, element2};
    int result = seqSearch(elements, "namhoon");
    cout << result;
}

위 프로그램을 살펴보면 for 문을 돌면서 n 개의 레코드를 탐색하는 평균은 (n+1)/2 이므로, O(n)의 시간복잡도를 가진다.

만약 어떤 리스트가 정렬된 순차 리스트라면 이런 순차 탐색 말고 이원 탐색 을 사용하여 자료를 찾을 수 있으며 이 경우 시간 복잡도는 O(logn) 이다.

정렬의 종류

삽입 정렬

i 개의 정렬된 레코드에 새로운 레코드를 끼워넣어 i+1 개의 정렬된 레코드 리스트를 만드는 정렬 방법이다.

아래 프로그램은 C로 구현한 insert 함수이다.

정렬된 리스트 a[1:i] 에 e 원소를 집어넣어 a[1:i+1]의 리스트를 만들어 내는 함수이다.

index 역할을 하는 i가 점차 작아지면서 a[i].key가 e.key 보다 큰 경우 한칸씩 우측으로 밀어내고, a[i].key가 e.key 보다 작아지는 i 값에서 a[i+1]에 e를 넣어준다.

1
2
3
4
5
6
7
8
9

void insert(element e, element a[], int i){
  a[0]=e;
  while(e.key<a[i].key){
    a[i+1] = a[i];
    i--;
  }

  a[i+1] = e;
}

아래 함수는 insert 함수를 활용하여 삽입정렬을 하는 프로그램이다.

1
2
3
4
5
6
7

void insertionSort(element a[], int n){
  int j;
  for(j=2;j<=n;j++){
    element temp = a[j];
    insert(temp, a, j-1);
  }
}

병합정렬(Merge Sort)

병합정렬은 입력 리스트를 길이가 1인 n 개의 정렬될 서브트리로 간주하는 것으로 시작합니다.

아래 merge 함수는 두개의 서로 다른 리스트를 병합하는 것을 보여줍니다.

merge sort 의 각 단계는 O(n) 의 시간이 걸리고 logn 번의 단계가 적용되므로 O(nlogn) 의 복잡도를 가집니다.

Time Complexity: O(nlogn)

또한 각 병합과정에서 새로운 배열이 필요하므로 inplace sort가 아니다.

퀵 정렬(Quick Sort)

퀵 정렬은 앞서 살펴본 정렬법 중에서 가장 좋은 평균 성능을 가지고 있다.
퀵 정렬의 순서는 먼저 피벗 레코드를 선택하여 피벗의 왼쪽에는 레코드 키들이 피벗의 키보다 작거나 같고 피벗의 오른쪽에는 레코드 키들이 피벗의 키보다 크거나 같도록 하는 방법을 사용한다. 최종적으로는 피벗의 왼쪽에 있는 레코드들과 피벗의 오른쪽에 있는 레코드들이 서로 독립적으로 정렬이 된다.

다음은 퀵 정렬을 수행하는 프로그램이다.
i와 j가 각각 왼쪽과 오른쪽에서 가운데 방향으로 진행하며, a[i].key는 pivot 보다 커질 때까지 a[j].key는 pivot 보다 작아질 때 까지

1
2
3
4
5
6
7
8

void quickSort(element a[], int left, int right){
  int pivot,i,j;
  pivot = a[left].key;
  do{
    do j++;while(a[i].key<pivot);
    do j--;while(a[j].key>pivot);
  }
}

히프정렬

히프 정렬에서는 최대 길이 [log_2(n+1)] 을 가지고 adjust를 n-1번 호출한다.

즉, O(nlogn) 이다.

버블 정렬

선택 정렬

히프(heap)란?

히프는 우선순위 큐를 구현하는 데 자주 사용된다. 우선순위 큐에서는 우선순위가 가장 높은(또는 낮은) 원소를 먼저 삭제한다.
히프에 대한 설명을 하기 전에 최대 트리와 최소 트리에 대한 설명을 먼저 진행한다.

최대 트리 란 각 노드의 키 값이 그 자식의 키 값보다 작지 않은 트리이며,
최소 트리 란 각 노드의 키 값이 그 자식의 키 값보다 크지 않은 트리를 말한다.

여기서 최대 히프 란 최대 트리이면서 완전 이진트리이며, 최소 히프 란 최소 트리이면서 완전 이진트리를 의미한다.

이러한 최대 히프 및 최소 히프에서는 부모를 쉽게 찾아 삽입이 가능하다.

히프의 생성은 C를 통하여 다음과 같이 구현한다.

1
2
3
4
5
6
7
8
9

#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n==MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)
typedef struct{
  int key;
  } element;

element heap[MAX_ELEMENTS];
int n=0;

최대 히프에서의 삽입

최대 히프에서 원소를 삽입하는 경우 추가되는 원소가 가장 아래부터 루트 쪽으로 올라가는 bubbling up 기법이 사용된다.
다음은 최대 히프에서의 원소의 삽입을 구현한 C 프로그램이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENTS 200 /*최대 히프 크기 +1*/
#define HEAP_FULL(n) (n == MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)

typedef struct element{
  int key;
}element;

element heap[MAX_ELEMENTS];
int n=0;

void push(element item, int *n)
{
  int i;
  if(HEAP_FULL(*n)){
    fprintf(stderr, "The heap is full. \n");
    exit(EXIT_FAILURE);
  }
  i = ++(*n);
  while ((i != 1) && (item.key > heap[i/2].key)){
    heap[i] = heap[i/2];
    i /= 2;
  }
  heap[i] = item;
}
int main()
{
    struct element node1 = {7};
    struct element node2 = {16};
    struct element node3 = {49};
    struct element node4 = {82};
    struct element node5 = {5};
    struct element node6 = {31};
    struct element node7 = {6};
    struct element node8 = {2};
    struct element node9 = {44};
    push(node1, &n);
    push(node2, &n);
    push(node3, &n);
    push(node4, &n);
    push(node5, &n);
    push(node6, &n);
    push(node7, &n);
    push(node8, &n);
    push(node9, &n);
    for(int k=1;k<10;k++){
        printf("%d ",heap[k].key);
    }
    return 0;
}

최대 히프에서의 삭제

최대 히프에서 원소의 삭제는 제일 위에서 이루어 진다.
먼저, 키값이 가장 큰 원소를 삭제하고 마지막 원소를 제거하고 두 자식 노드중 큰 값이 위로 올라가고 아래를 메꾸는 방식으로 진행된다.
최대 히프의 삭제를 구현한 프로그램은 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

element pop(int *n)
{
  int parent, child;
  element item, temp;
  if(HEAP_EMPTY(*n)){
    fprintf(stderr, "The heap is empty\n");
    exit(EXIT_FAILURE);
  }

  item=heap[1];
  temp = heap[(*n)--];
  parent = 1;
  child = 2;
  while(child <= *n){
    if((child < *n) && (heap[child].key < heap[child+1].key))
      child++;
    if(temp.key > heap[child].key) break;
    heap[parent] = heap[child];
    parent = child;
    child *= 2;
  }
  heap[parent] = temp;
  return item;
}

B - 히프

B - 히프란 최소 트리의 집합이다.

• 트리(tree)란?
• 이진 트리
  • 이진 트리 순회
  • 예제
• 스레드 이진 트리
• 이원 탐색 트리(BST, Binary Search Tree)
  • 이원 탐색트리의 탐색
  • INSERTION IN BST
  • DELETION IN BST
• 선택 트리
  • 승자 트리
  • 패자 트리
• 분리 집합의 표현
• 이진 트리의 개수 계산
• AVL 트리
  • AVL 트리에서의 삽입

트리(tree)란?

트리 구조란 정보의 항목들이 가지로 연결될 수 있게 데이터가 조작되는 것이며, 가계표, 족보, 왕조의 나열 등에서 쉽게 찾아볼 수 있다.
가계표를 예를 들어 설명을 하면 최 상단에 조부모님이 계시고 그 아래로 아버지와 어머니, 동생 친척들이 쭉 나열이 되는데, 이러한 조직 체계를 트리를 통해 나타낼 수 있다.

트리 구조에서 노드 란 각 항목들을 의미하며 한 정보 아이템에서 다른 노드로 뻗어진 가지를 포함한 개념이다.
각 노드는 아래로 계속해서 가지를 뻗어나갈 수 있는데, 한 노드에서 뻗어져 나간 가지들(서브트리) 의 수를 그 노드의 차수 라고 부른다.
또한, 차수가 0인 노드를 리프 혹은 단말 노드 라고 부르며, 뻗어나간 구조의 상위의 노드를 아래 노드의 부모(parent) 라 하고 아래 노드를 상위 노드의 자식(child) 이라고 부른다. 또한 한 노드에서 뻗어져 나온 병렬관계의 노드를 서로의 형제(sibling) 이라고 부른다.

특정 노드의 차수와 구분하여 트리의 차수 트리에 있는 노드의 최대 차수를 말한다.

이진 트리

다시 가계표의 예를 들면 한 부모 밑에는 수많은 자식들이 생길 수 있으나, 컴퓨터가 이를 처리하는 시점에서 특정 부모노드 아래에 숫자를 알 수 없는 자식들이 존재하게 된다면 포인터 필드가 가변적이기에 효율적으로 메모리를 사용할 수 없다. 이 때문에 일정한 크기의 노드를 사용하기 위한 트리의 표현법이 나타나게 되었고, 한 노드가 가지만을 가지도록 만들어진 트리를 이진 트리 라고 한다.

제일 위의 노드(root)로 부터 2배씩 증가하며 가지들이 뻗어나와 크리스마스 트리 형태를 띄는 형태를 이진트리라고 부르며 모든 노드들이 규칙적으로 2개씩 가지를 쳐 나가 각 층의 노드가 꽉꽉 들어차면 이를 포화 이진 트리 라고 한다.
깊이가 k인 포화 이진트리의 노드 수는 (2^k-1)개 이다.

컴퓨터에서는 이러한 이진트리를 메모리에 저장할 방법을 찾게 되었고 최 상단 노드부터 차례로 메모리에 저장을 하게 되면 포화 이진트리가 아닌 대부분의 이진트리에서는 메모리 중간 중간이 비게 되어 효율적인 메모리 사용에 어려움을 겪게 되었는데, 이를 해결하기 위해 열결표현 방식을 사용하여 각 노드가 다른 노드의 링크를 연결하여 포인터를 들고 있는 방식으로 저장하게 되었다.

어떠한 트리도 이진 트리로 표현할 수 있다.

다음은 C 언어를 이용한 이진 트리의 구현이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <stdlib.h>
#include <stdio.h>
/*node 구조체로 *treePointer 라는 별칭 선언*/
typedef struct node *treePointer;
/*node 구조체를 선언한다.*/
typedef struct node{
  char data;
  treePointer leftChild, rightChild;
} node;

treePointer createNode(char newData)
{
  treePointer newNode = (treePointer)malloc(sizeof(node));
  newNode->leftChild = NULL;
  newNode->rightChild = NULL;
  newNode->data = newData;

  return newNode;
}

void inorder(treePointer ptr)
{
  if(ptr){
    inorder(ptr->leftChild);
    printf("%c", (*ptr).data);
    inorder(ptr->rightChild);
  }
}

/*추가된 노드를 출력하는 부분*/
int main()
{
    treePointer nodeA = createNode('A');
    treePointer nodeB = createNode('B');
    treePointer nodeC = createNode('C');
    treePointer nodeD = createNode('D');
    treePointer nodeE = createNode('E');
    treePointer nodeF = createNode('F');
    treePointer nodeG = createNode('G');
    treePointer nodeH = createNode('H');

    (*nodeA).leftChild=nodeB;
    (*nodeA).rightChild=nodeC;
    (*nodeB).leftChild=nodeD;
    (*nodeB).rightChild=nodeE;
    (*nodeD).rightChild=nodeG;
    (*nodeC).leftChild=nodeF;
    (*nodeF).rightChild=nodeH;
    inorder(nodeA);
}

이진 트리 순회

앞서 설명한 이진 트리를 조회하기 위해서 다양한 방법을 사용하는데, 한 노드에서 왼쪽으로 이동(L), 오른쪽으로 이동(R), 노드 방문(V) 의 순서에 따라 중위 순회, 후위 순회, 전위 순회로 구분한다.

먼저 전위 순회(preorder traversal) 는 이름 그대로 노드를 먼저 방문하는 경우 즉, VLR의 순서로 노드를 방문하는 경우이다.
후위 순회(postorder traversal) 은 노드를 제일 마직막에 방문하는 경우 즉, LRV의 순서로 노드를 방문하는 경우이다.
중위 순회 란 노드를 중간에 방문하는 경우 즉, LVR의 순서로 노드를 방문하는 경우이다.

중위 순회를 하는 경우를 C 코드로 나타내면 다음과 같다.

1
2
3
4
5
6
7
8

void inorder(treePointer ptr)
{
  if(ptr){
    inorder(ptr->leftChild);
    printf("%c", (*ptr).data);
    inorder(ptr->rightChild);
  }
}

위의 코드를 살펴보면 반복법이 아닌 순환법을 이용하여 즉, 스택의 도움 없이 순회를 진행하는데 이는 스택을 이용하여 스택에 노드를 저장하고 제거하는 방식으로도 순회가 가능하다. 이러한 순회를 반복적 중위 순회 라고 하며 이를 C 코드로 구현하면 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void iterInorder(treePointer ptr){
  int top = -1; /*스택 초기화*/
  treePointer stack[MAX_STACK_SIZE];
  for(;;){
    for(;node;node=node->leftChild)
      push(node);/*스택에 삽입*/

    node=pop();/*스택에서 제거*/
    if(!node)/*스택이 비어있는 경우 중지*/
      break;
    printf("%d", node->data);
    node=node->rightChild;
  }
}

예제

이진 트리에서 리프 노드의 수를 세는 C 함수를 작성하여라.

1
2
3
4
5
6
7
8
9
10
11
12

int totalCount=0;
void countLeaf(treePointer ptr){
  if(ptr&&(!(*ptr).leftChild)&&(!(*ptr).rightChild)){
    totalCount++;
    printf("\n리프 노드: %c, count:%d\n", (*ptr).data, totalCount);
  }
  if(ptr){
    countLeaf((*ptr).leftChild);
    printf("%c",(*ptr).data);
    countLeaf((*ptr).rightChild);
  }
}

스레드 이진 트리

2n개의 링크 중 n+1개가 null link 이므로 효율성이 떨어지는 문제가 생기게 되고 이를 해결하기 위해 null link에 포인터를 넣어 다른 노드의 링크를 거는 것을 스레드 라고 한다.

이원 탐색 트리(BST, Binary Search Tree)

이원 탐색 트리는 탐색, 삽입, 삭제 연산에 있어서 지금까지 공부했던 어떤 자료 구조보다도 성능이 좋다.
이원 탐색트리의 모든 원소는 키를 가지고 어떤 두 원소도 동일한 키를 갖지 않으며, 왼쪽 서브트리가 존재한다면 그 키들은 루트의 키보다 작고 오른쪽 서브트리가 존재한다면 루트의 키보다 크다. 또한, 왼쪽과 오른쪽 서브트리도 모두 이원탐색 트리이다.

이원 탐색트리의 탐색

탐색은 루트부터 시작하여 루트와 키 값이 같다면 탐색은 종료된다. 탐색하고자 하는 키 값이 루트의 키보다 작다면 왼쪽 서브트리를 탐색하고 크다면 오른쪽 서브트리를 탐색한다. 왼쪽과 오른쪽 서브트리는 모두 이원탐색 트리이므로 각각을 다시 탐색하는 순환 탐색 방식을 사용한다.

다음은 이원 탐색 트리의 순환적 탐색을 구현한 프로그램이다.

1
2
3
4
5
6
7

element * search(treePointer tree, int key){
  if(!root) return NULL;
  if(k == root->data.key) return &(root->data);
  if(k<root->data.key)
    return search(root->leftChild, k);
  return search(root->rightChild, k);
}

아래는 동일한 기능의 반복 함수로 구현한 프로그램이다.

1
2
3
4
5
6
7
8
9
10
11

element* iterSearch(treePointer tree, int k)
{
  white(tree){
    if(k==tree->data.key) return &(tree->data);
    if(k<tree->data.key)
      tree = tree->leftChild;
    else
      tree = tree->rightChild;
  }
  return NULL;
}

Time Complexity: O(h)

BST 에서의 찾는 시간은 찾고자 하는 노드의 높이만큼 분기를 수행하므로 O(h) 이다.

INSERTION IN BST

Time Complexity: O(h)

BST 에서의 삭제는 search 후에 단순 삽입으로 search 시의 time complexity와 같은 complexity 를 가진다.

DELETION IN BST

Time Complexity: O(h)

BST 에서의 삭제는 다음과 같이 진행된다.

1. BST에서 해당 노드를 찾음
2. 해당 노드를 삭제하고, maximum value in left subchild 로 대체 하거나 혹은 minimum in right subchild 로 대체한다.
3. 대체된 노드에 대한 삭제를 진행한다. 이 경우 해당 노드는 차수가 0이거나 혹은 1 이므로 삭제는 매우 간편하다.

위의 각 과정별로 시간 소모를 생각해 보면, 노드를 찾는데에 O(h), 삭제하고 서브 트리에서 값을 찾는데에 O(h) 삭제에 1 이므로 BST 에서 deletion 시에 time Complexity 는 O(h) 이다.

선택 트리

승자 트리

다음은 8개의 런(k=8) 을 가진 승자 트리의 개념도 입니다.

패자 트리

다음은 위의 승자 트리에 대응하는 패자 트리의 개념도 입니다.

분리 집합의 표현

이진 트리의 개수 계산

AVL 트리

AVL 트리란 균형 이진 트리의 한 종류이며, 이원 탐색트리가 항상 완전 이진트리로 유지되도록 한 트리입니다.

탐색, 삽입, 삭제 시간: O(logn)

AVL 트리에서 각 노드는 균형 인자(balance factor) 를 가지는데, 이는 왼쪽 트리의 높이에서 오른쪽 트리의 높이를 뺀 값으로 높이의 균형도를 나타냅니다.

balance factor = h_L - h_R

AVL 트리에서는 어떤 서브트리 T 에서도 BF(T) 의 절대값은 1 이하입니다.

AVL 트리에서의 삽입

LL rotation

RR rotation
LR rotation

• 1. 한쪽 끝과 양쪽 끝 우선순위 큐
• 좌향 트리
• 이항히프(B-Heap)

1. 한쪽 끝과 양쪽 끝 우선순위 큐

우선순위 큐(priority queue) 는 각 원소가 연관된 우선순위를 갖고 있는 원소들의 모임이다.
가령 시스템의 작업 우선도를 설정해 줄 때에는 작업들을 우선 순위에 따라 분류해야 하며, 2개의 서버로 이루어진 시스템의 경우에 하나의 시스템이 사고로 인해 종료되는 경우 반대쪽 서버로 그 작업 내역들이 병합되어야 하는데 이러한 경우 우선순위 큐를 통해 두 작업 리스트를 병합해야 한다.

이러한 우선순위 큐 한쪽 끝 우선순위 큐 와 양쪽 끝 우선순위 큐 가 있으며, 한쪽 끝 우선순위 큐는 최대 우선순위 큐 와 최소 우선순위 큐 로 나뉜다.

최소 우선순위 큐 에 의해 지원되는 연산은 다음과 같다.
SP1. 최소 우선순위를 가진 원소의 반환
SP2. 임의 우선순위를 가진 원소의 삽입
SP3. 최소 우선순위를 가진 원소의 삭제

이러한 우선순위 큐를 잘 표현하기 위한 고전적인 자료 구조로써 히프(heap) 를 사용한다.

양쪽 끝 우선순위 큐는 최소 우선순위 큐와 최대 우선순위 큐가 하나로 합해진 최소-최대 우선순위 큐이다.

실제 활용도 측면에서, 양쪽 끝 우선순위 큐는 네트워크 버퍼를 구현하는 데 사용되는데 네트워크 링크를 통해 전송되기를 원하는 패킷들을 가지고 있는 경우 가장 높은 우선순위를 가진 패킷이 전송되고 삭제 되는 최대 삭제 가 행해지는 반면, 네트워크 내의 다른 곳으로 부터 새로운 패킷이 도착하였는데 버퍼가 가득 차 있다면 우선 순위가 가장 낮은 패킷을 지우는 최소 삭제 가 일어나게 된다. 이처럼 작업 큐의 양쪽에서 삽입과 삭제가 가능한 큐를 양쪽 끝 우선순위 큐라고 부른다.

좌향 트리

좌향트리는 합병성 우선순위 큐의 효율적 구현을 제공한다.
좌향 트리의 종류에는 HBLT(Height Biased Leftist Tree)와 WBLT(Weight Biased Leftist Tree)가 있는데, 일반적으로 HBLT를 좌향트리하고 부른다.

이항히프(B-Heap)

좌향 트리에서 지원되는 것과 같은 기능을 수행한다. 개별적인 연산을 수행하는 데 걸리는 시간보다 우선순위 큐의 순차를 수행하는데 걸리는 시점에 관심이 있다.
이항 히프란 최소 트리의 집합이며, 최소 트리 가운데 최소값을 갖는 트리를 가리키는 하나의 포인터가 가르키게 된다.

• 개요: 시스템 생명 주기
• 포인터와 동적 메모리 할당
• 알고리즘 명세
• 데이터 추상화
• 성능 분석
  • 공간 복잡도
  • 시간 복잡도

개요: 시스템 생명 주기

포인터와 동적 메모리 할당

알고리즘 명세

데이터 추상화

성능 분석

본 강의의 목적 중 하나는 프로그램에 대한 평가 능력을 향상시키는 것이다.
프로그램의 판단함에 있어서 다양한 기준이 있지만, 크게는 컴퓨터와 상관 없이 시공간의 추산에 초점을 두는 성능 분석(performance analysis) 과 컴퓨터에 의존적인 실행 시간을 얻어내는 성능 측정(performance measurement) 이 있다.

이번 강의 에서는 성능 측정은 배제하고 성능 분석에 초점을 두어 강의를 진행하며 성능 분석은 다음의 두 복잡도로 분석을 진행한다.

1. 공간 복잡도
2. 시간 복잡도

공간 복잡도

공간 복잡도의 정의는 프로그램을 실행시켜 완료하는 데 필요로 하는 공간의 양으로, 실제 메모리를 차지하는 양을 나타낸다. 각 각의 변수가 얼마나 많은 메모리를 차지하는 지 등을 다루며 이러한 공간 복잡도는 고정 공간 요구 및 가변 공간 요구 로 나뉘게 된다.

고정 공간 요구
프로그램 입출력의 횟수나 크기에 관계없는 공간 요구를 의미한다.
가령 명렁어 공간, 단순 변수, 상수 고정 크기의 구조화 변수 등을 포함한다.

가변 공간 요구
해결하고자 하는 문제의 특정 인스턴스 I에 의존하는 크기를 가진 구조화 변수들을 위해 필요로 하는 공간이다.

시간 복잡도

컴파일 시간과 실행 시간을 합한 것이다.