코코야이야기

레드-블랙 트리 (Red-Black Tree) - 2-3-4 트리를 표준 이진 트리로 표현하는 방법 - 노드당 추가로 1 비트가 더 필요함 - 블랙 링크는 보통의 노드이고, 3-노드와 4-노드는 레드 링크로 연결된 이진 트리로 표현 성질 - 루트나 외부 노드는 모두 블랙 - 루트에서 외부 노드까지의 경로 상에는 2개의 연속된 레드 노드가 포함되지 않음 - 루트에서 각 외부 노드까지의 경로에 있는 블랙 노드의 수는 모두 같음 - 동일한 키를 가지는 레코드는 노드의 왼쪽과 오른쪽에 모두 올 수 있음 - 동일한 키가 여러 개 있을 때 주어진 키를 갖는 모든 노드를 찾는 것이 어려움 4-노드의 분할 4-노드의 분할 (회전 필요) 단일 회전 이중 회전 구축 과정 키(2, 1, 8, 9, 7, 3, 6, 4, 5)..

2-3-4 트리 (2-3-4 Tree) 이진 탐색 트리(1개의 키, 2개의 링크)에서 발생하는 최악의 상황을 방지하기 위해 다음과 같이 자료구조를 변경 - 트리에 있는 하나의 노드가 하나 이상의 키를 가질 수 있음 - 3-노드(2개의 키, 3개의 링크)와 4-노드(3개의 키, 4개의 링크)를 허용 - 트리의 균형에 대해 신경 쓰지 않아도 완벽한 균형 트리가 만들어 짐 분할 과정 1. 루트가 4-노드인 경우 - 세 개의 2-노드로 변환 - 루트의 분할은 트리의 높이를 하나 증가시킴 2. 부모가 2-노드인 4-노드의 경우 - 중간 키를 부모로 보내여 3-노드에 연결된 두 개의 2-노드로 변환 3. 부모가 3-노드인 4-노드의 경우 - 4-노드에 연결된 두 개의 2-노드로 변환 4. 4-노드가 2-3-4 트리..

이진 탐색 트리 (Binary Search Tree) - 작은 키를 가지고 있는 모든 레코드는 왼쪽 부분트리에 있음 - 같거나 큰 키를 가지고 있는 모든 레코드는 오른쪽 부분트리에 있음 탐색 과정 - 루트와 주어진 키를 비교 - 키가 루트보다 작다면, 왼쪽 부분트리로 이동 - 키가 루트와 같다면, 종료 - 키가 루트보다 크다면, 오른쪽 부분트리로 이동 * 트리를 중위 순회하면 데이터를 정렬하는 효과가 있음 예시 성능 특성 - N개의 임의의 키로 이루어진 이진 탐색 트리를 탐색하고 삽입하는 연산은 평균적으로 logN 회의 비교 필요 - 최악의 경우 N 개의 키를 가진 이진 탐색 트리를 탐색하는데 N 회의 비교 필요 >> 키가 정렬되거나 역순으로 정렬된 순서로 삽입 >> 최초 비어 있는 트리에 키들이 A Z..

히프 정렬 (Heap Sort) 히프(heap)를 이용해 정렬 (히프 : 우선순위 큐의 일종) - 정렬할 원소를 모두 공백 히프에 하나씩 삽입 - 한 원소씩 삭제 →제일 큰 원소가 삭제됨 - 이 원소를 리스트의 뒤에서부터 차례로 삽입 - 오름차순으로 정렬된 리스트를 생성 히프 구성 방법 - 상향식(bottom-up) : 정렬할 배열을 완전 이진 트리라고 간주하고, 인덱스가 N/2인 노드부터 차례대로 인덱스를 감소시키면서 히프 구조로 변환 - 하향식(top-down) : 공백 히프에 차례대로 한 원소씩 삽입하여 히프를 구성 상향식 히프 구성 수행 과정 성능 특성 - 제자리 정렬이지만 불안정적 - N 개의 원소를 정렬하는데 N logN 단계가 필요함 - 입력 배열의 순서에 민감하지 않음 - 내부 루프가 퀵 ..

자연 합병 정렬 (Natural Merge Sort) - 주어진 배열 속에 이미 순서에 맞는 원소로 된 부분 배열, 즉 런(Run)만을 합병. - 두 개의 런이 결정되면 합병이 수행된다. 예를 들어 배열 [6, 7, 8, 3, 4, 1, 11, 12, 13, 2]에서 런 [6, 7, 8]과 런 [3, 4]가 먼저 합병되면 [3, 4, 6, 7, 8]이 되고 런 [1, 11, 12, 13]과 런 [2]가 합병되면 [1, 2, 11, 12, 13]이 된다. 마지막으로 런 [3, 4, 6, 7, 8]과 [1, 2, 11, 12, 13]이 합병되면 [1, 2, 3, 4, 6, 7, 8, 11, 12, 13]이 된다. 소스 코드 1. #include #include using namespace std; const..

합병 정렬 (Merge Sort) - 두 개의 정렬된 화일을 하나의 큰 정렬된 화일로 합병함 - 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘임 - 두 부분배열의 크기가 동일하도록 분할함 성능 특성 - 최악의 경우에도 N 개의 원소를 가진 화일을 정렬하는 N logN 에 비례하는 시간이 소요됨 - 순차적 방식에 의해 데이터를 접근함 - 연결 리스트와 같이 순차 접근이 유일한 접근 방법일 경우 사용 가능 - N 에 비례하는 추가 기억장소가 필요함 - 안정적이지만 제자리 정렬은 아님 - 최악의 경우 시간 복잡도 O(N logN) - 입력 배열에 민감하지 않음 수행 과정 퀵 정렬과 비교 퀵 정렬 : 정복-분할(conquer-and-divide) - 순환 호출이 이루어지기 전에 대부분의 작업이 수..

중간 값 분할 - 분할 원소를 선택할 때 왼쪽, 가운데, 오른쪽 원소 중 값이 중간인 원소를 선택 - 왼쪽, 가운데, 오른쪽 원소를 정렬한 후 가장 작은 값을 a[l], 가장 큰 값을 a[r], 중간 값을 a[r-1]에 넣고, a[l+1], …, a[r-2]에 대해 분할 알고리즘을 수행 특징 - 최악의 경우가 발생하는 확률을 낮추어 줌 - 경계 키(sentinel key)를 사용할 필요가 없음 - 전체 수행 시간을 약 5% 감소시킴 소스 코드 #include #include #include using namespace std; const int N = 10000000; const int TRUE = 1; const int FALSE = 0; int a[N+1]; inline void swap(int a[..

작은 부분화일 부분화일의 크기가 일정 크기 이하로 작아지면 삽입 정렬 수행 “if (r > l)” - “if (r - l a[i+1]) Sorted = FALSE; if (!Sorted) break; } if (Sorted) cout

스택을 이용한 순환제거 소스 코드 #include #include #include using namespace std; const int N = 10000000; int a[N+1]; const int TRUE = 1; const int FALSE = 0; inline void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } void CheckTime(int a[], int n) { int i, Sorted; Sorted = TRUE; for (i = 1; i a[i+1]) Sorted = FALSE; if (!Sorted) break; } if (Sorted) cout r-i) { st...

퀵 정렬 (Quick Sort) - 1960년 C.A.R. Hoare에 의해 개발 - 분할 정복(divide and conquer) 기법을 사용한 정렬 방법의 하나 - 현재 가장 광범위하게 쓰이는 정렬 알고리즘 - 퀵 정렬의 성능을 개선하려는 시도가 있었지만 큰 성과를 거두지 못함 특징 - 평균적으로 아주 좋은 성능을 가짐 - 약간의 작은 스택만 있으면 별도의 메모리를 요구하지 않음 - 불안정적인 제자리 알고리즘 - N 개의 원소를 정렬하는데 평균적으로 N logN 의 연산속도를 가짐 기본 알고리즘 1. 배열 a[l : r] a[r]을 피봇(pivot)으로 선정 2. 피봇을 기준으로 a[]의 원소들을 두 개의 파티션(partition)으로 분할 - 분할 후 피봇은 a[i]에 들어가게 되는데, 이곳은 정렬..