트리
포인터를 이용한 이진 트리의 노드 생성
typedef struct node { // node라는 이름의 구조체 정의
struct node *left; // 노드의 왼쪽 자식을 가리키는 포인터
char data; // 노드에 저장될 데이터 (문자형)
struct node *right; // 노드의 오른쪽 자식을 가리키는 포인터
} node;이 코드는 이진 트리를 구성하는 노드를 정의한다. 각 노드는 왼쪽 자식, 데이터, 오른쪽 자식을 가진다. struct node는 자기 참조 구조체로, 같은 타입의 포인터를 멤버로 포함한다. 이 구조체를 사용해 이진 트리의 각 노드를 표현한다.
이진트리 전위 순회
void preorder(node* root) { // 이진 트리의 루트 노드를 가리키는 포인터를 매개변수로 받는 preorder 함수 정의
if (root != NULL) { // 루트 노드가 NULL이 아닌 경우
printf("%c ", root->data); // 루트 노드의 데이터를 출력
preorder(root->left); // 왼쪽 서브트리에 대해 전위 순회 재귀호출
preorder(root->right); // 오른쪽 서브트리에 대해 전위 순회 재귀호출
}
}이 코드는 이진 트리의 전위 순회를 수행하는 함수 preorder를 정의한다. 전위 순회는 루트 노드를 먼저 방문하고, 그 다음 왼쪽 서브트리, 마지막으로 오른쪽 서브트리를 순회한다. 함수는 재귀적으로 호출되어 트리의 모든 노드를 전위 순서대로 방문하고 출력한다.
이진트리 중위 순회
void inorder(node* root) { // node 타입의 포인터 root를 인자로 받는 inorder 함수 정의
if (root != NULL) { // root가 NULL이 아닐 경우 (트리가 비어있지 않은 경우)
inorder(root->left); // root의 왼쪽 자식에 대해 중위 순회 재귀 호출
printf("%c ", root->data); // root의 데이터 출력
inorder(root->right); // root의 오른쪽 자식에 대해 중위 순회 재귀 호출
}
}이 코드는 이진트리를 중위 순회하는 함수 inorder를 정의한다. 중위 순회는 왼쪽 자식을 방문, 현재 노드 처리, 오른쪽 자식을 방문하는 순서로 진행된다. 이 함수는 주어진 이진트리의 노드를 왼쪽 자식부터 오른쪽 자식까지 순서대로 방문하고 출력한다.
이진트리 후위 순회
void postorder(node* root) { // node 타입의 포인터 root를 인자로 받는 postorder 함수 정의
if (root != NULL) { // root가 NULL이 아닐 경우 (트리가 비어있지 않은 경우)
postorder(root->left); // root의 왼쪽 자식에 대해 후위 순회 재귀 호출
postorder(root->right); // root의 오른쪽 자식에 대해 후위 순회 재귀 호출
printf("%c ", root->data); // root의 데이터 출력
}
}이 코드는 이진트리를 후위 순회하는 함수 postorder를 정의한다. 후위 순회는 왼쪽 자식을 방문, 오른쪽 자식을 방문, 현재 노드 처리하는 순서로 진행된다. 이 함수는 주어진 이진트리의 모든 노드를 왼쪽 자식부터 오른쪽 자식, 그리고 부모 노드 순으로 방문하고 출력한다.
이진트리의 노드 삽입
node *insert(node *here, node *it) { // node 타입의 포인터 here와 it를 인자로 받는 insert 함수 정의
if (here == NULL) { // here가 NULL일 경우 (삽입 위치가 비어있는 경우)
return it; // 새 노드 it를 반환
} else if (it->data < here->data) { // 삽입할 노드의 데이터가 현재 노드의 데이터보다 작은 경우
here->left = insert(here->left, it); // 왼쪽 자식에 대해 재귀적으로 삽입 수행
} else { // 삽입할 노드의 데이터가 현재 노드의 데이터보다 크거나 같은 경우
here->right = insert(here->right, it); // 오른쪽 자식에 대해 재귀적으로 삽입 수행
}
return here; // 현재 노드 반환
}이 코드는 이진트리에 새로운 노드를 삽입하는 함수 insert를 정의한다. 이 함수는 이진트리의 특성을 유지하면서 적절한 위치에 새로운 노드를 삽입한다. 삽입할 노드의 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽에 삽입하는 방식으로 재귀적으로 처리한다.
이진트리의 노드 삭제
node *delete(node *root, char data) { // 이진트리에서 데이터 값을 갖는 노드를 삭제하는 함수
if (root == NULL) { // 현재 노드가 NULL이면 NULL을 반환
return NULL;
}
if (data < root->data) { // 삭제하려는 데이터가 현재 노드 데이터보다 작으면
root->left = delete(root->left, data); // 왼쪽 서브트리에서 데이터를 찾아 삭제
} else if (data > root->data) { // 삭제하려는 데이터가 현재 노드 데이터보다 크면
root->right = delete(root->right, data); // 오른쪽 서브트리에서 데이터를 찾아 삭제
} else {
// 삭제하려는 노드를 찾은 경우
if (root->left != NULL && root->right != NULL) { // 노드에 두 개의 자식이 있는 경우
node *temp = findMin(root->right); // 오른쪽 서브트리에서 최소값을 찾음
root->data = temp->data; // 찾은 최소값을 현재 노드에 복사
root->right = delete(root->right, temp->data); // 복사한 노드를 오른쪽 서브트리에서 삭제
} else { // 노드에 자식이 한 개 이하인 경우
node *temp = root; // 삭제할 노드를 임시로 저장
if (root->left == NULL) root = root->right; // 왼쪽 자식이 없으면 오른쪽 자식을 현재 노드로 설정
else if (root->right == NULL) root = root->left; // 오른쪽 자식이 없으면 왼쪽 자식을 현재 노드로 설정
free(temp); // 임시로 저장한 노드(삭제할 노드)를 메모리에서 해제
}
}
return root; // 변경된 트리의 루트 노드를 반환
}이 코드는 이진트리에서 특정 데이터 값을 갖는 노드를 찾아 삭제하는 함수다. 삭제할 노드가 자식이 없거나 한 개만 있는 경우, 쉽게 삭제할 수 있다. 하지만 두 자식이 있는 경우, 오른쪽 서브트리에서 최소값을 찾아 현재 노드와 교체한 후, 해당 최소값을 갖는 노드를 오른쪽 서브트리에서 재귀적으로 삭제한다.
이진트리의 노드 개수를 세는 연산
int get_nodeNum(node *root) { // 이진트리의 노드 개수를 반환하는 함수
if (root == NULL) { // 현재 노드가 NULL이면 0 반환
return 0;
} else {
return 1 + get_nodeNum(root->left) + get_nodeNum(root->right); // 현재 노드를 포함하여 왼쪽, 오른쪽 서브트리의 노드 개수를 합산하여 반환
}
}이 코드는 이진트리의 모든 노드의 개수를 세는 함수다. 현재 노드가 NULL이면 0을 반환하고, 그렇지 않으면 현재 노드를 포함하여 왼쪽과 오른쪽 서브트리의 노드 개수를 합산하여 반환한다. 이는 재귀적으로 트리의 각 노드를 방문하며 개수를 셈으로써 전체 노드 개수를 구한다.
이진트리의 잎 노드 개수를 세는 연산
int get_leafNum(node *root) { // 이진트리의 잎 노드 개수를 반환하는 함수
if (root == NULL) { // 현재 노드가 NULL
이면 0 반환
return 0;
} else if (root->left == NULL && root->right == NULL) { // 현재 노드가 잎 노드이면 1 반환
return 1;
} else {
return get_leafNum(root->left) + get_leafNum(root->right); // 왼쪽, 오른쪽 서브트리의 잎 노드 개수를 합산하여 반환
}
}이 코드는 이진트리의 잎 노드(자식이 없는 노드)의 개수를 세는 함수다. 현재 노드가 NULL이면 0을 반환하고, 잎 노드이면 1을 반환한다. 그렇지 않은 경우, 왼쪽과 오른쪽 서브트리의 잎 노드 개수를 재귀적으로 계산하여 합산한다. 이 함수는 트리의 각 노드를 방문하며 잎 노드인지 확인하고, 해당하는 경우에만 카운트를 증가시킨다.
스레드 트리
스레드 트리 포인터 필드 추가
typedef struct tfNode {
struct tfNode *left; // 왼쪽 자식 노드를 가리키는 포인터
struct tfNode *lthread; // 왼쪽 스레드를 가리키는 포인터
char data; // 노드에 저장된 데이터
struct tfNode *right; // 오른쪽 자식 노드를 가리키는 포인터
struct tfNode *rthread; // 오른쪽 스레드를 가리키는 포인터
} tfNode;이 구조체는 스레드 트리의 노드를 정의한다. 각 노드는 데이터를 저장하는 data 필드와 두 자식 노드를 가리키는 left와 right 포인터를 가지며, 스레드 트리의 특성상 lthread와 rthread라는 추가 포인터를 가진다.
스레드 트리 포인터 필드를 이용한 중위 순회 연산
void inorder(tfNode *startNode) {
tfNode *ptr = startNode;
while (ptr != NULL) {
printf("%c", ptr->data);
ptr = ptr->rthread;
}
}이 함수는 스레드 트리를 중위 순회하는 연산을 수행한다. 시작 노드부터 오른쪽 스레드를 따라가면서 노드에 저장된 데이터를 출력한다.
중위 순회 스레드 트리의 중위 순회 연산
typedef struct tfNode {
struct tfNode *left;
char data;
struct tfNode *right;
int threadFlag;
} tfNode;이 구조체는 중위 순회 스레드 트리를 위한 노드를 정의한다. threadFlag 필드는 오른쪽 포인터가 자식 노드를 가리키는지 스레드를 가리키는지를 나타낸다.
중위 순회 스레드 트리의 중위 순회 연산
tfNode* inorderStart(tfNode* ptr) {
if (ptr == NULL)
return NULL;
while (ptr->left != NULL)
ptr = ptr->left;
return ptr;
}
void inorder(tfNode *root) {
tfNode *ptr = inorderStart(root);
while (ptr != NULL) {
printf("%c", ptr->data);
if (ptr->threadFlag) // 오른쪽 포인터를 스레드로 사용함
ptr = ptr->right;
else
ptr = inorderStart(ptr->right);
}
}이 함수들은 중위 순회 스레드 트리를 중위 순회하는 연산을 수행한다. inorderStart 함수는 주어진 노드에서 가장 왼쪽에 있는 노드를 찾는다. inorder 함수는 이를 시작점으로 해서 중위 순회를 진행한다.
중위 순회 트레드 트리의 노드 삽입 연산
void insert(tfNode *x, tfNode *ttree) {
ttree->left = NULL;
ttree->right = x->right;
ttree->lthread = x;
ttree->rthread = x->rthread;
x->right = ttree;
x->rthread = ttree;
}이 함수는 스레드 트리에 새 노드를 삽입하는 연산을 수행한다. 새 노드는 x 노드의 오른쪽에 삽입되며, 스레드 관계를 적절히 조정한다.
중위 순회 스레드 트리의 노드 삽입시 노드 x가 잎인 경우
void insert(tfNode *x, tfNode *ttree) {
ttree->left = NULL;
ttree->right = x->right;
ttree->lthread = x;
ttree->rthread = x->rthread;
x->right = ttree;
x->rthread = ttree;
}이 함수도 앞서 설명된 insert 함수와 동일하다. 내부 노드에 새 노드를 삽입할 때의 처리 방식을 보여준다.
중위 순회 스레드 트리의 노드 삽입시 노드 x가 내부 노드인 경우
void insertInternal(tfNode *x, tfNode *ttree) {
tfNode *successor = x->right;
ttree->right = successor;
ttree->rthread = x->rthread;
x->right = ttree;
x->rthread = ttree;
if (!ttree->rthread) { // 만약 오른쪽 포인터가 스레드가 아니라면
tfNode *leftmost = inorderStart(successor); // 후속 노드의 가장 왼쪽 노드를 찾음
leftmost->left = ttree; // 후속 노드의 가장 왼쪽 노드의 왼쪽 포인터를 새 노드로 설정
}
}이 함수는 중위 순회 스레드 트리에 노드 x가 내부 노드일 때 새 노드 ttree를 삽입하는 연산을 수행한다. 새 노드는 x의 오른쪽 자식 노드로 삽입되며, x와 ttree 사이의 스레드 관계 및 ttree의 오른쪽 자식과의 관계를 적절히 조정한다. 이 때, ttree의 오른쪽 포인터가 스레드가 아닐 경우에는 후속 노드의 가장 왼쪽 노드의 왼쪽 포인터를 새 노드로 설정하여 스레드 관계를 유지한다.
힙
우선순위 큐의 데이터 삭제와 삽입
Delete_q() 에 의해 큐의 front 에 있던 T 이 삭제되면서， 나머지 데이터 중에서 가장작은 값인 ‘2’가다음 삭제 위치 즉，front가 가리키는 위치로 이동됨void Delete_q() { // 우선순위 큐에서 데이터를 삭제하는 Delete_q 함수 정의
// 큐의 front에 있던 T가 삭제되면서, 나머지 데이터 중에서 가장 작은 값인 '2'가 다음 삭제 위치 즉, front가 가리키는 위치로 이동됨
}이 코드는 우선순위 큐에서 가장 우선순위가 높은 데이터를 삭제하고, 남은 데이터 중에서 가장 우선순위가 높은 데이터를 큐의 front 위치로 이동시키는 기능을 수행한다.
void Delete_q(): 이 함수는 우선순위 큐의 가장 앞에 있는 데이터를 삭제하고, 그 다음으로 우선순위가 높은 데이터를 큐의 front 위치로 이동시킨다. 이 과정은 우선순위 큐의 정렬 상태를 유지하는 데 중요하다.
힙 추상자료형
// 힙 추상자료형 연산 정의
1 insert(element)::= 립에 데이터 삽입
2 delete()::= 힙(루트)에서 데이터 삭제
3 peek()::= 힙(루트)에서 데이터 읽어오기
4 isEmpty()::= 힙이 비었는지 확인
5 size()::= 힙에 저장한 데이터 개수 확인이 코드는 힙 추상자료형에서 수행할 수 있는 기본 연산들을 정의한다.
insert(element): 힙에 새로운 데이터를 삽입하는 연산이다.delete(): 힙의 루트 노드(최소값 혹은 최대값)에서 데이터를 삭제하는 연산이다.peek(): 힙의 루트 노드의 데이터를 읽어오는 연산이다.isEmpty(): 힙이 비어 있는지 확인하는 연산이다.size(): 힙에 저장된 데이터의 개수를 확인하는 연산이다.
힙의 노드 삭제
typedef struct heap { // 힙을 나타내는 구조체 정의
int heap[MAX_SIZE]; // 힙을 저장하는 배열
int size; // 힙의 현재 크기
} heap;
int min_heapDelete(heap *h) { // 최소 힙에서 노드를 삭제하는 함수 정의
int parent, child;
int data, temp;
if (h->size == 0) return -1; // 힙이 비어있는 경우 -1 반환
data = h->heap[1]; // 삭제할 데이터 (루트 노드)
temp = h->heap[h->size--]; // 힙의 마지막 노드
parent = 1;
child = 2;
while (child <= h->size) { // 자식 노드가 힙의 크기 이내일 때까지 반복
// 오른쪽 자식 노드가 왼쪽 자식 노드보다 작은 경우, child 증가
if ((child < h->size) && (h->heap[child] > h->heap[child + 1])) {
child++;
}
// 임시 저장된 마지막 노드가 자식 노드보다 작거나 같으면 반복 종료
if (temp <= h->heap[child]) {
break;
}
// 부모 노드에 자식 노드 할당
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
// 최종적으로 부모 노드 위치에 임시 저장 노드 할당
h->heap[parent] = temp;
return data; // 삭제된 데이터 반환
}이 코드는 최소 힙에서 노드를 삭제하는 기능을 수행한다. 삭제 과정에서 힙의 속성을 유지하기 위해, 힙의 마지막 노드를 루트로 옮기고, 힙을 재정렬한다.
int min_heapDelete(heap *h): 이 함수는 최소 힙에서 루트 노드를 삭제하고, 힙의 속성을 유지하면서 재정렬하는 기능을 수행한다. 삭제된 루트 노드의 값을 반환한다.
힙에서 삭제 (루트 노드 삭제)
data = h->heap[1]; // 힙의 루트 노드 값을 data에 저장
temp = h->heap[h->size]; // 마지막 노드 값을 temp에 저장
h->heap[1] = h->heap[h->size]; // 마지막 노드를 루트 위치로 이동
h->size--; // 힙의 크기를 1 감소
parent = 1; // parent를 루트 노드의 인덱스로 설정
child = 2; // child를 루트 노드의 왼쪽 자식 인덱스로 설정
while (child <= h->size) { // child 인덱스가 힙 크기 이하일 동안 반복
// 오른쪽 자식이 있고, 오른쪽 자식이 왼쪽 자식보다 작을 경우
if ((child < h->size) && (h->heap[child] > h->heap[child + 1])) {
child++; // 오른쪽 자식으로 이동
}
// 재배치할 노드(temp)가 자식 노드보다 작거나 같으면 중단
if (temp <= h->heap[child]) {
break;
}
// 부모 노드를 자식 노드로 이동
h->heap[parent] = h->heap[child];
parent = child; // 부모 위치를 현재 자식 위치로 업데이트
child *= 2; // 다음 자식 노드로 이동 (왼쪽 자식의 인덱스는 항상 2배)
}
h->heap[parent] = temp; // 최종 위치에 temp(원래 마지막 노드의 값) 저장
return data; // 삭제된 루트 노드의 값 반환이 코드는 힙 자료구조에서 루트 노드를 삭제하는 과정을 구현한다. 루트 노드의 값을 data에 저장하고, 마지막 노드를 루트 위치로 이동시킨 후, 힙의 크기를 줄인다. 그리고 힙 속성을 유지하기 위해 힙을 재구성한다. 이 과정에서 최소 힙(min heap)의 조건을 만족시키기 위해 부모 노드가 자식 노드들보다 항상 작거나 같도록 조정한다. 이러한 조정 과정을 "힙 다운(heap down)" 또는 "퍼콜레이트 다운(percolate down)"이라고 한다.
data = h->heap[1];: 삭제될 루트 노드의 값을 data에 저장한다.temp = h->heap[h->size];: 마지막 노드의 값을 temp에 저장한다.h->heap[1] = h->heap[h->size];: 마지막 노드를 루트 노드의 위치로 이동한다.while (child <= h->size) { ... }: 힙 속성을 유지하기 위해 마지막 노드의 값을 적절한 위치로 이동시킨다. 이때 오른쪽 자식 노드가 더 작으면 오른쪽 자식을 선택하고, 재배치할 노드(temp)가 자식 노드보다 작거나 같으면 재배치를 중단한다.h->heap[parent] = temp;: 재배치가 완료된 위치에 temp 값을 저장한다.return data;: 삭제된 루트 노드의 원래 값 반환한다.
마지막 노드를 루트로 이동
if((child < h->size) && (h->heap[child] > h->heap[child+1])) { // 현재 자식 노드의 인덱스가 힙 크기보다 작고, 현재 자식 노드의 값이 오른쪽 형제 노드보다 큰 경우
child++; // 오른쪽 자식으로 이동
}이 코드는 힙에서 부모 노드와 자식 노드를 비교하고, 필요한 경우 더 작은 오른쪽 자식 노드로 이동한다. 이는 최소 힙의 성질을 유지하기 위해 사용된다.
if((child < h->size) && (h->heap[child] > h->heap[child+1])): 자식 노드가 힙의 크기 내에 있고, 왼쪽 자식이 오른쪽 자식보다 큰 경우, 오른쪽 자식으로 이동한다.
마지막 노드를 루트로 이동
if(temp <= h->heap[child]) { // 임시 저장된 노드 값이 현재 자식 노드의 값보다 작거나 같은 경우
break; // 루프 중단
}
h->heap[parent] = h->heap[child]; // 부모 노드에 자식 노드의 값을 할당
parent = child; // 부모 노드 인덱스를 현재 자식 노드 인덱스로 업데이트
child *= 2; // 자식 노드 인덱스를 두 배로 증가시키기 (다음 자식 노드로 이동)이 코드는 최소 힙에서 임시 저장된 노드 값을 힙의 아래쪽으로 이동시키는 과정을 수행한다. 이는 힙에서 원소를 삭제하거나 힙을 재정렬할 때 사용된다.
if(temp <= h->heap[child]) { break; }: 임시 저장된 값이 현재 자식 노드의 값보다 작거나 같으면, 위치를 변경할 필요가 없으므로 반복을 중단한다.h->heap[parent] = h->heap[child]: 부모 노드 위치에 자식 노드의 값을 할당한다.parent = child; child *= 2;: 부모 노드의 인덱스를 현재 자식 노드의 인덱스로 업데이트하고, 자식 노드의 인덱스를 다음 자식 노드로 이동시킨다.
힙의 노드 삽입
void min_heapInsert(heap *h, int data) { // 최소 힙에 새로운 노드를 삽입하는 함수 정의
int i;
if (h->size + 1 > MAX_SIZE) return; // 힙의 크기가 최대치를 초과하면 함수 종료
i = ++(h->size); // 힙 크기를 하나 증가시키고, i에 할당
// 삽입할 노드가 부모 노드보다 작을 때까지 부모 노드와 교체
while ((i != 1) && (data < h->heap[i / 2])) { // i가 1이 아니고, 삽입할 데이터가 부모 노드보다 작은 경우 반복
h->heap[i] = h->heap[i / 2]; // 부모 노드의 값을 현재 노드로 복사
i /= 2; // 인덱스를 부모 노드의 인덱스로 업데이트
}
// 최종 위치에 새 데이터 삽입
h->heap[i] = data; // 삽입할 데이터를 최종 위치에 저장
}이 코드는 최소 힙 자료구조에 새로운 노드를 삽입하는 함수 min_heapInsert를 정의한다. 힙의 크기가 최대치를 초과하면 추가 작업을 중단한다. 새로운 데이터는 힙의 마지막 위치에 추가되고, 힙의 속성을 유지하기 위해 부모 노드와 비교하면서 필요한 경우 교체되며, 최종적으로 올바른 위치에 삽입된다.
void min_heapInsert(heap *h, int data): 이 함수는 주어진 최소 힙h에 새로운 데이터data를 삽입한다. 힙의 크기가 최대치를 초과하지 않도록 검사하고, 삽입된 데이터가 힙의 속성을 유지하도록 부모 노드와 비교하여 적절한 위치에 삽입한다. 이 함수는 최소 힙 구조를 유지하면서 새로운 데이터를 효율적으로 추가하는 데 사용된다.
마지막에 노드 삽입
while ((i != 1) && (data < h->heap[i/2])) {
h->heap[i] = h->heap[i/2]; // 부모 노드의 값을 현재 노드로 복사
i /= 2; // 인덱스를 부모 노드의 인덱스로 업데이트
}
h->heap[i] = data; // 삽입할 데이터를 최종 위치에 저장이 코드는 새로 삽입된 노드가 최소 힙의 속성을 만족할 때까지 부모 노드와 교체하는 과정을 수행한다. 삽입된 데이터가 부모 노드보다 작을 경우에만 반복적으로 부모 노드와 위치를 교체하고, 최종적으로 적절한 위치에 데이터를 삽입한다. 이 과정은 최소 힙의 속성을 유지하는 핵심 단계이다.
Bs, Splay, AVL, BB
BS트리를 위한 노드 정의
typedef struct BSTnode {
struct BSTnode* left; // 왼쪽 자식 노드를 가리키는 포인터
char key; // 노드의 키를 저장하는 문자형 변수
char content[10]; // 노드의 내용을 저장하는 문자 배열
struct BSTnode* right; // 오른쪽 자식 노드를 가리키는 포인터
} BSTnode;이 코드는 이진 탐색 트리(Binary Search Tree, BS 트리)의 노드를 정의한다. 각 노드는 왼쪽 자식, 키, 내용, 오른쪽 자식을 포함한다.
struct BSTnode: 이 구조체는 BS 트리의 개별 노드를 정의한다. 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 포인터와 노드의 키, 내용을 저장한다.
BS 트리의 중위 순회
void inorderBST(BSTnode* root) {
if (root != NULL) { // 현재 노드가 NULL이 아닌 경우
inorderBST(root->left); // 왼쪽 서브트리 중위 순회
printf("%c ", root->key); // 현재 노드의 키 출력
inorderBST(root->right); // 오른쪽 서브트리 중위 순회
}
}이 코드는 BS 트리를 중위 순회하는 함수를 정의한다. 중위 순회는 왼쪽 서브트리 방문, 노드 처리(출력), 오른쪽 서브트리 방문 순서로 진행된다.
void inorderBST(BSTnode* root): 이 함수는 주어진 BS 트리의 루트 노드에서 시작하여 트리를 중위 순회한다. 각 노드의 키는 방문 순서대로 출력된다.
BS 트리의 노드 탐색
BSTnode* searchBST(BSTnode* root, char key) {
if (root == NULL) { // 탐색 노드가 NULL일 경우
printf("Error: 값이 찾을 수 없습니다\n"); // 오류 메시지 출력
return NULL; // NULL 반환
}
if (key == root->key) { // 찾는 키가 현재 노드의 키와 일치할 경우
return root; // 현재 노드 반환
} else if (key < root->key) { // 찾는 키가 현재 노드의 키보다 작을 경우
return searchBST(root->left, key); // 왼쪽 서브트리에서 탐색 계속
} else { // 찾는 키가 현재 노드의 키보다 클 경우
return searchBST(root->right, key); // 오른쪽 서브트리에서 탐색 계속
}
}이 코드는 BS 트리에서 주어진 키를 가진 노드를 탐색하는 함수를 정의한다. 키 값에 따라 왼쪽 또는 오른쪽 서브트리로 이동하여 탐색을 진행한다.
BSTnode* searchBST(BSTnode* root, char key): 이 함수는 주어진 키를 가진 노드를 BS 트리에서 탐색한다. 찾는 키가 노드의 키보다 작거나 클 경우 각각 왼쪽 또는 오른쪽 서브트리에서 재귀적으로 탐색을 계속한다.
BS 트리의 노드 삽입
BSTnode* insertBST(BSTnode* root, char key) { // BS 트리의 루트 노드와 삽입할 키를 인자로 받는 insertBST 함수 정의
BSTnode* ptr; // 현재 노드를 가리킬 포인터 ptr 선언
BSTnode* newNode = (BSTnode*)malloc(sizeof(BSTnode)); // 새 노드를 위한 메모리 할당
newNode->key = key; // 새 노드의 key 필드에 인자로 받은 키 할당
newNode->left = newNode->right = NULL; // 새 노드의 left와 right 포인터를 NULL로 초기화
if (root == NULL) { // 트리가 비어있는 경우
root = newNode; // 새 노드를 루트로 설정
return root; // 수정된 루트 노드 반환
}
ptr = root; // 트리 탐색을 시작하기 위해 ptr에 root 할당
while (ptr) { // ptr이 NULL이 아닐 때까지 반복
if (key == ptr->key) { // 삽입하려는 키가 트리에 이미 존재하는 경우
printf("Error: 중복 값은 허용되지 않습니다\n"); // 에러 메시지 출력
return root; // 기존 루트 노드 반환
} else if (key < ptr->key) { // 삽입하려는 키가 현재 노드의 키보다 작은 경우
if (ptr->left == NULL) { // 현재 노드의 왼쪽 자식이 없는 경우
ptr->left = newNode; // 새 노드를 왼쪽 자식으로 연결
return root; // 수정된 루트 노드 반환
} else {
ptr = ptr->left; // 왼쪽 자식으로 이동
}
} else { // 삽입하려는 키가 현재 노드의 키보다 큰 경우
if (ptr->right == NULL) { // 현재 노드의 오른쪽 자식이 없는 경우
ptr->right = newNode; // 새 노드를 오른쪽 자식으로 연결
return root; // 수정된 루트 노드 반환
} else {
ptr = ptr->right; // 오른쪽 자식으로 이동
}
}
}
}이 코드는 BS 트리에 새로운 노드를 삽입하는 함수 insertBST를 정의한다. 함수는 루트 노드와 삽입할 키를 매개변수로 받아, 새 노드를 적절한 위치에 삽입한다. 중복된 키가 있을 경우 에러 메시지를 출력하고, 삽입할 위치를 찾기 위해 트리를 순회한다. 삽입 위치가 결정되면 새 노드를 해당 위치에 연결하고, 수정된 트리의 루트 노드를 반환한다.
BSTnode* insertBST(BSTnode* root, char key): 이 함수는 새 노드를 BS 트리에 삽입한다. 삽입할 노드의 위치를 찾기 위해 트리를 순회하고, 적절한 위치에 노드를 삽입한다. 중복된 키가 있는 경우 삽입을 허용하지 않고, 트리가 비어 있을 경우 새 노드를 루트로 설정한다.
BS 트리의 노드 삭제
if (del -> left == NULL && del -> right == NULL) { // 삭제하려는 노드(del)에 자식 노드가 없는 경우
if (parent != NULL) { // 삭제 노드의 부모 노드(parent)가 존재하는 경우
if (parent->left == del) { // 삭제 노드가 부모 노드의 왼쪽 자식인 경우
parent->left = NULL; // 부모 노드의 왼쪽 링크를 NULL로 설정
} else {
parent->right = NULL; // 삭제 노드가 부모 노드의 오른쪽 자식인 경우, 부모의 오른쪽 링크를 NULL로 설정
}
} else {
root = NULL; // 삭제 노드가 루트 노드인 경우, 트리는 비어있게 됨
}
} else if (del -> left != NULL && del -> right != NULL) { // 삭제하려는 노드에 자식 노드가 두 개 있는 경우
TreeNode* predecessor = del; // 전임자 노드를 가리키는 변수
TreeNode* successor = del -> left; // 후임자 노드를 가리키는 변수
while (successor -> right != NULL) { // 후임자 노드의 오른쪽 자식이 NULL이 아닐 때까지 반복
predecessor = successor; // 전임자를 현재 후임자로 업데이트
successor = successor -> right; // 후임자를 오른쪽 자식으로 이동
}
if (predecessor -> left == successor) { // 전임자의 왼쪽 자식이 후임자인 경우
predecessor -> left = successor -> left; // 전임자의 왼쪽 링크를 후임자의 왼쪽 자식으로 설정
} else {
predecessor -> right = successor -> left; // 전임자의 오른쪽 링크를 후임자의 왼쪽 자식으로 설정
}
del -> key = successor -> key; // 삭제 노드에 후임자의 키 값을 복사
del = successor; // 삭제할 노드를 후임자 노드로 변경
} else { // 삭제하려는 노드에 자식 노드가 하나 있는 경우
TreeNode* child; // 자식 노드를 가리킬 포인터
if (del -> left != NULL) { // 삭제 노드의 왼쪽 자식이 존재하는 경우
child = del -> left; // 자식 노드는 왼쪽 자식
} else {
child = del -> right; // 삭제 노드의 오른쪽 자식이 존재하는 경우, 자식 노드는 오른쪽 자식
}
if (parent != NULL) { // 삭제 노드의 부모 노드가 존재하는 경우
if (parent->left == del) { // 삭제 노드가 부모 노드의 왼쪽 자식인 경우
parent->left = child; // 부모 노드의 왼쪽 링크를 자식 노드로 설정
} else {
parent->right = child; // 삭제 노드가 부모 노드의 오른쪽 자식인 경우, 부모의 오른쪽 링크를 자식 노드로 설정
}
} else {
root = child; // 삭제 노드가 루트 노드인 경우, 루트를 자식 노드로 설정
}
}이 코드는 이진 탐색 트리(BS 트리)에서 노드를 삭제하는 로직을 구현한다. 삭제할 노드(del)에 따라 세 가지 경우로 나뉘어 처리한다:
- 자식 노드가 없는 경우: 삭제할 노드의 부모 노드에서 해당 링크를
NULL로 설정한다. - 자식 노드가 두 개 있는 경우: 삭제할 노드의 위치에 올라갈 후임자를 찾고, 이 후임자의 키 값을 삭제할 노드에 복사한 후, 후임자 노드를 삭제한다.
- 자식 노드가 하나 있는 경우: 삭제할 노드의 자식을 부모 노드에 연결한다.
- 노드 삭제: 삭제할 노드를 기반으로 트리에서 해당 노드를 안전하게 제거하며, 트리의 구조와 이진 탐색 트리의 속성을 유지한다.
- 후임자 찾기와 대체: 두 자식이 있는 노드를 삭제할 때, 후임자 노드를 찾아 그 키 값을 삭제할 노드 위치에 복사한다. 이 후임자는 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값 또는 오른쪽 서브트리에서 가장 작은 값으로 선택된다.
- 부모-자식 연결 재설정: 노드의 부모와 자식 사이의 연결을 적절히 재설정하여 트리의 연속성을 보장한다.
Splay 트리의 연산
노드 x: 최근에 접근한 노드, // 노드 x는 Splay 트리에서 최근에 접근한 노드를 나타낸다
노드 p: x의 부모 노드, // 노드 p는 노드 x의 부모 노드를 나타낸다
노드 g: x의 조부모(부모의 부모) 노드 // 노드 g는 노드 x의 조부모 노드를 나타낸다
zig: p가 트리의 루트 노드이고 x가 p의 왼쪽 자식일 때, p와 x의 간선 연결을 우측으로 회전시킨다. // 'zig' 연산은 p가 루트이고 x가 p의 왼쪽 자식일 때, p와 x의 관계를 우회전하여 x를 위로 올린다
zag: p가 트리의 루트 노드이고 x가 p의 오른쪽 자식일 때, p와 x의 간선 연결을 좌측으로 회전시킨다. // 'zag' 연산은 p가 루트이고 x가 p의 오른쪽 자식일 때, p와 x의 관계를 좌회전하여 x를 위로 올린다
zig-zig: p가 루트가 아니고, x와 p 모두 각각 자신의 부모의 왼쪽 자식일 때, 먼저 p와 g의 간선 연결을 우측으로 회전시키고, 그 다음 x와 p의 간선 연결을 우측으로 회전시킨다. // 'zig-zig' 연산은 p가 루트가 아니고 x와 p가 모두 왼쪽 자식일 때, 두 번의 우회전을 통해 x를 트리의 위쪽으로 이동시킨다
zag-zag: p가 루트가 아니고, x와 p 모두 각각 자신의 부모의 오른쪽 자식일 때, 먼저 p와 g의 간선 연결을 좌측으로 회전시키고, 그 다음 x와 p의 간선 연결을 좌측으로 회전시킨다. // 'zag-zag' 연산은 p가 루트가 아니고 x와 p가 모두 오른쪽 자식일 때, 두 번의 좌회전을 통해 x를 트리의 위쪽으로 이동시킨다
zig-zag: p가 루트가 아니고, x가 p의 왼쪽 자식이고 p가 g의 오른쪽 자식일 때, 먼저 x와 p의 간선 연결을 우측으로 회전시키고, 그 다음 x와 g의 간선 연결을 좌측으로 회전시킨다. // 'zig-zag' 연산은 p가 루트가 아니고, x가 p의 왼쪽, p가 g의 오른쪽 자식일 때, 우회전 후 좌회전을 수행하여 x를 트리의 위쪽으로 이동시킨다
zag-zig: p가 루트가 아니고, x가 p의 오른쪽 자식이고 p가 g의 왼쪽 자식일 때, 먼저 x와 p의 간선 연결을 좌측으로 회전시키고, 그 다음 x와 g의 간선 연결을 우측으로 회전시킨다. // 'zag-zig' 연산은 p가 루트가 아니고, x가 p의 오른쪽, p가 g의 왼쪽
자식일 때, 좌회전 후 우회전을 수행하여 x를 트리의 위쪽으로 이동시킨다이 코드는 Splay 트리에서의 다양한 회전 연산을 설명한다. Splay 트리는 특정 노드에 대한 접근을 빈번하게 할 때 해당 노드를 트리의 루트에 가깝게 이동시키는 이진 탐색 트리의 변형이다. 여기서 제시된 연산들은 노드 x를 트리의 더 상위로 이동시키기 위한 방법들이다. 각 연산은 노드 x의 위치와 그 부모 및 조부모 노드와의 관계에 따라 달라진다.
zig,zag연산은 단일 회전을 사용하여 루트 노드와의 관계를 조정한다.zig-zig,zag-zag연산은 동일한 방향으로 두 번의 회전을 사용하여 더 깊은 노드를 루트에 가깝게 이동시킨다.zig-zag,zag-zig연산은 두 방향으로 회전을 사용하여 복잡한 구조에서 노드를 루트에 가깝게 이동시킨다.
m원 탐색 트리
m원 탐색 트리 노드의 구조
struct Mnode {
int n; // 노드에 저장된 키의 개수
struct Rectype {
struct Mnode *ptr; // 자식 노드에 대한 포인터
int key; // 키 값
} keyptrs[]; // 가변 길이 배열, 자식 노드와 키 값의 쌍을 저장
struct Mnode *keyptrn; // 마지막 자식 노드에 대한 포인터
};이 코드는 m원 탐색 트리 노드의 구조를 정의한다. 각 노드는 키 값의 개수 n을 저장하며, 가변 길이 배열 keyptrs[]를 사용하여 자식 노드와 해당 키 값의 쌍을 저장한다. 마지막 자식 노드에 대한 포인터는 keyptrn으로 저장된다.
m원 탐색 트리의 탐색 연산 - 키 값을 찾는 연산
struct Mnode *Search(int skey, struct Mnode *r) {
int i;
if (r == NULL)
return NULL;
else {
i = 0;
while (i < r->n && skey > r->keyptrs[i].key)
i++;
if (i < r->n && skey == r->keyptrs[i].key)
return r->keyptrs[i].ptr;
else if (i < r->n)
return Search(skey, r->keyptrs[i].ptr);
else
return Search(skey, r->keyptrn);
}
}이 코드는 m원 탐색 트리에서 특정 키 값을 찾는 탐색 연산을 수행하는 함수를 정의한다. m원 탐색 트리의 노드 구조와 키 값을 찾는 탐색 연산을 정의하고 있다. 노드 구조는 키 값과 자식 노드를 저장하는 방식으로 이루어져 있으며, 탐색 연산은 루트 노드에서 시작하여 주어진 키 값을 찾는 역할을 한다.
struct Mnode *Search(int skey, struct Mnode *r): 특정 키skey를 찾는 함수로, 루트 노드r에서 시작하여 특정 키를 찾거나 해당 키가 없으면 NULL을 반환한다.i는 현재 노드의 키 값과 비교할 때 사용되며, 노드의n은 저장된 키 값의 개수를 나타낸다.- 노드 내의 키 값들과
skey를 비교하며, 해당 키를 찾거나 적절한 자식 노드로 이동하여 재귀적으로 탐색한다. - 만약 해당 키를 찾으면 해당 키에 대한 자식 노드를 반환하고, 찾지 못하면 NULL을 반환한다.
B 트리에 키를 삽입하는 알고리즘
1. 삽입할 위치를 찾기 위해 노드의 키 값을 왼쪽에서 오른쪽으로 탐색한다. (B 트리에서 모든 노드는 잎 노드에서 삽입이 시작됨)
2. 노드에 빈 자리가 있으면 삽입 후 종료한다.
3. 노드가 꽉 찼으면 노드를 2개로 분리하고 키와 포인터를 새 노드에 반씩 할당한다.
3.1 잎 노드 키값과 삽입 노드 키값 중에서 중간값을 선택한다.
3.2 선택된 중간값보다 작은 키값을 갖는 것은 왼쪽 노드에 넣고, 큰 것은 오른쪽 노드에 넣는다.
3.3 중간값을 갖는 노드의 키값과 포인터를 부모노드에 삽입한다.
만일 부모 노드가 루트 노드면, 두 노드를 가리키도록 (자식 노드가 되도록) 수정한다.B 트리에서 키를 삭제하는 알고리즘 - 잎노드에서 삭제
// 잎 노드에서 키 삭제 알고리즘
1. 삭제할 키 값을 포함한 노드를 찾는다.
2. 잎 노드에서 키 값을 삭제한다.
3. 필요하면 재배열한다.B 트리에서 키를 삭제하는 알고리즘 - 내부노드에서 삭제
// 내부 노드에서 키 삭제 알고리즘
1. 내부 노드의 키 값은 하위 노드에 대한 기준값(중간값)이기 때문에 삭제 시, 대체할 수 있는 적절한 값을 찾아야 한다.
2. 보통 왼쪽 서브 트리의 가장 큰 키 값 또는 오른쪽 서브 트리의 가장 작은 키 값으로 대체할 수 있다.
3. 새로운 기준값(삭제된 자리에 올 키 값)을 선택하여 해당 (잎) 노드에서 삭제하고 그 값을 현재 키 값을 삭제한 자리로 옮긴다.
4. 기준값으로 대체하기 위해 키를 삭제한 잎 노드가 정해진 개수의 키 값을 갖지 않으면 트리를 재배열한다.B 트리에서 키를 삭제하는 알고리즘 - 재배열
// 재배열 알고리즘
1. 키값이 부족한 노드의 오른쪽 형제가 존재하고 키가 정해진 최소개수보다 많다면 왼쪽으로 회전한다.
1.1 부모 노드의 기준(키)값을 개수가 부족한 노드의 끝으로 이동한다.
1.2 부모 노드의 기준값을 오른쪽 형제의 첫 번째 키로 수정해 균형을 맞춘다.
2. 키값이 부족한 노드의 왼쪽 형제가 존재하고 키가 정해진 최소개수보다 많다면 오른쪽으로 회전한다.
2.1 부모 노드의 기준(키)값을 개수가 부족한 노드의 끝으로 이동한다.
2.2 부모 노드의 기준값을 왼쪽 형제의 마지막 키로 수정해 균형을 맞춘다.
3. 좌우 형제가 최소개수의 키를 가지고 있다면, 좌우 형제를 합친다.
3.1 부모 노드의 기준 (키)값을 왼쪽 노드의 마지막에 복사한다.
3.2 오른쪽 노드의 모든 키 값을 왼쪽 노드로 옮긴다.
3.3 키를 갖지 않는 오른쪽 노드는 삭제한다.
4. 부모 노드가 루트면서 키를 더 이상 갖지 않으면 합쳐진 노드가 새로운 루트가 된다. 그렇지 않고 부모 노드의 키 개수가 정해진 최소 개수보다 작으면 부모 노드를 재배열한다.2-3 트리의 탐색
typedef struct two_three *two_three_ptr;
struct two_three {
int l_key, r_key;
two_three_ptr l_child, m_child, r_child;
};
two_three_ptr search23(two_three_ptr t, int x) {
while(t) {
int comp_result = compare(x, t);
switch(comp_result) {
case 1: t = t->l_child; break; // x가 노드의 왼쪽 키값(l_child)보다 작은 경우
case 2: t = t->m_child; break; // x가 노드의 왼쪽 키값보다 크고 오른쪽 키값보다 작은 경우
case 3: t = t->r_child; break; // x가 노드의 오른쪽 키값(r_child)보다 큰 경우
case 4: return t; // x가 노드의 키값들 중 어느 하나와 같은 경우
}
}
return NULL;
}typedef struct two_three *two_three_ptr;:two_three구조체를 가리키는 포인터 타입two_three_ptr을 정의한다.struct two_three { ... };: 2-3 트리의 노드를 나타내는two_three구조체를 정의한다. 각 노드는 두 개의 키(l_key,r_key)와 세 개의 자식 노드(l_child,m_child,r_child)로 구성된다.two_three_ptr search23(two_three_ptr t, int x) { ... }:search23함수를 정의한다. 이 함수는 2-3 트리t에서 특정 값x를 찾아서 해당 노드를 반환하는 역할을 한다.while (t) { ... }: 노드t가 NULL이 아닌 동안 반복한다.int comp_result = compare(x, t);:compare함수를 사용하여 현재 노드의 키와 값을 비교하고 결과를comp_result에 저장한다.switch (comp_result) { ... }:comp_result의 값에 따라 다음 동작을 수행한다.case 1::x가 현재 노드의 왼쪽 키값(l_key)보다 작은 경우, 왼쪽 자식 노드로 이동한다.case 2::x가 현재 노드의 왼쪽 키값보다 크고 오른쪽 키값(r_key)보다 작은 경우, 중간 자식 노드로 이동한다.case 3::x가 현재 노드의 오른쪽 키값보다 큰 경우, 오른쪽 자식 노드로 이동한다.case 4::x가 노드의 키값들 중 어느 하나와 같은 경우, 현재 노드를 반환하고 탐색을 종료한다.
return NULL;: 함수가 끝날 때까지 해당 값을 찾지 못한 경우 NULL을 반환한다.
이 함수는 2-3 트리에서 특정 값을 찾는 역할을 하며, comp_result를 통해 비교하면서 노드를 탐색하고, 일치하는 값을 찾으면 해당 노드를 반환한다.
2-3 트리의 삽입 알고리즘
void insert23(two_three_ptr *t, int y) { // 2-3 트리에 삽입하는 함수 insert23 정의, 트리의 주소와 삽입할 값 y를 매개변수로 받음
two_three_ptr q, p, r; // 2-3 트리 노드 포인터 q, p, r 선언
if (!(*t)) // 트리 t가 비어있으면
new_root(t, y, NULL); // 새 루트 노드 생성 함수 new_root 호출, t를 루트로 하고 y 값을 가짐
else { // 트리 t가 비어있지 않으면
p = find_node(*t, y); // y 값을 가진 노드를 찾는 함수 find_node 호출, 결과를 p에 저장
if (!p) { // y 값을 가진 노드가 이미 트리에 존재하면
fprintf(stderr, "The key is already in the tree\n"); // 에러 메시지 출력
exit(1); // 프로그램 종료
}
q = NULL; // q를 NULL로 초기화
for (;;) { // 무한 루프
if (p->r_key == INT_MAX) { // p 노드의 오른쪽 키가 최대 정수값이면 (노드에 공간이 있으면)
put_in(&p, y, q); // y 값을 p 노드에 삽입하는 함수 put_in 호출
break; // 루프 탈출
} else { // p 노드에 공간이 없으면
split(p, &y, &q); // 노드 분할 함수 split 호출, y와 q 업데이트
if (p == *t) { // p가 트리의 루트이면
new_root(t, y, q); // 새 루트 노드 생성 함수 new_root 호출
break; // 루프 탈출
} else
p = ascend(p); // p를 부모 노드로 이동하는 함수 ascend 호출
}
}
}
}이 코드는 2-3 트리에 새로운 값 y를 삽입하는 insert23 함수이다. 비어 있는 트리에는 새 루트 노드를 생성하고, 그렇지 않은 경우에는 삽입 위치를 찾아 값 y를 삽입한다. 만약 노드에 공간이 없어서 삽입할 수 없는 경우에는 노드를 분할하고, 필요한 경우 새로운 루트 노드를 생성한다.
void insert23(two_three_ptr *t, int y): 이 함수는 2-3 트리t에 새로운 값y를 삽입한다. 트리가 비어 있으면 새 루트 노드를 생성하고, 그렇지 않으면 적절한 위치를 찾아 값을 삽입한다. 필요한 경우 노드 분할과 새 루트 노드 생성을 수행한다.
그래프
순환 호출을 이용한 깊이 우선 탐색
void DFS(Graph* g, int s) { // 그래프 g와 시작 정점 s를 매개변수로 받는 DFS 함수 정의
int adjacent; // 인접 정점을 나타내는 변수 adjacent 선언
g->visited[s] = 1; // 시작 정점 s를 방문한 것으로 표시
printf("%d ", s); // 방문한 정점 s 출력
for(adjacent = 0; adjacent < g->nv; adjacent++) { // 모든 정점에 대해 반복
if(g->adj[s][adjacent] && !g->visited[adjacent]) { // 정점 s와 인접하고 아직 방문하지 않은 정점이 있다면
DFS(g, adjacent); // 해당 인접 정점에 대해 DFS 재귀 호출
}
}
}이 코드는 그래프 g의 정점 s부터 시작하여 깊이 우선 탐색(DFS)을 수행하는 함수 DFS를 정의한다. 각 정점은 방문 여부를 추적하기 위한 visited 배열을 사용하며, 방문하지 않은 인접 정점에 대해 재귀적으로 DFS를 호출한다.
void DFS(Graph* g, int s): 이 함수는 정점s에서 시작하여 그래프g를 깊이 우선 탐색한다. 재귀 호출을 사용하여 탐색을 진행하며, 방문한 정점은visited배열을 통해 표시된다.
스택을 직접 운영하는 깊이 우선 탐색
void DFS(Graph* g, int s) { // 그래프 g와 시작 정점 s를 매개변수로 받는 DFS 함수 정의
int v, w; // 현재 정점과 인접 정점을 나타내는 변수 v, w 선언
extern struct stack *st; // 외부에서 선언된 스택 st 사용
extern int visited[]; // 외부에서 선언된 방문 여부 배열 visited 사용
InitializeStack(st); // 스택 초기화
push(st, s); // 시작 정점 s를 스택에 푸시
visited[s] = 1; // 시작 정점 s를 방문한 것으로 표시
while(!IsStackEmpty(st)) { // 스택이 비어있지 않은 동안 반복
v = pop(st); // 스택에서 정점 v를 팝
if(!visited[v]) { // 정점 v를 아직 방문하지 않았다면
visited[v] = 1; // 정점 v를 방문한 것으로 표시
printf("%d ", v); // 방문한 정점 v 출력
for(w = 0; w < g->nv; w++) { // 모든 정점에 대해 반복
if(g->adj[v][w] && !visited[w]) { // 정점 v와 인접하고 아직 방문하지 않은 정점이 있다면
push(st, w); // 해당 인접 정점을 스택에 푸시
}
}
}
}
}이 코드는 스택을 사용하여 그래프 g의 정점 s부터 시작하는 깊이 우선 탐색(DFS)을 수행하는 함수 DFS를 정의한다. 스택을 통해 재귀 호출 없이 DFS를 구현하며, 방문하지 않은 정점을 스택에 푸시하여 탐색을 진행한다.
void DFS(Graph* g, int s): 이 함수는 스택을 사용하여 정점s에서 시작하여 그래프g를 깊이 우선 탐색한다. 재귀 호출 대신 스택을 이용하여 탐색을 진행하고, 방문하지 않은 인접 정점을 스택에 추가하여 탐색 범위를 확장한다.
너비 우선 탐색
void BFS(Graph* g, int s) { // 그래프 g와 시작 정점 s를 매개변수로 받는 BFS 함수 정의
int i, adjacent; // 반복문과 인접 정점 탐색에 사용할 변수 i, adjacent 선언
int visited[MAX_VERTICES]; // 방문한 정점을 추적하는 배열 visited 선언
for(i = 0; i < g->nv; i++) { // 그래프의 모든 정점에 대해 반복
visited[i] = 0; // visited 배열을 0으로 초기화
}
int queue[MAX_VERTICES]; // 정점을 저장할 큐 queue 선언
int front = 0, rear = 0; // 큐의 front와 rear 인덱스를 0으로 초기화
visited[s] = 1; // 시작 정점 s를 방문했음을 표시
queue[rear++] = s; // 큐에 시작 정점 s 추가
while(front != rear) { // 큐가 비어있지 않는 동안 반복
s = queue[front++]; // 큐에서 정점을 꺼내 s에 저장
printf("%d ", s); // 현재 정점 s 출력
for(adjacent = 0; adjacent < g->nv; adjacent++) { // 모든 인접 정점에 대해 반복
if(g->adj[s][adjacent] && !visited[adjacent]) { // 인접하고 아직 방문하지 않은 정점이면
visited[adjacent] = 1; // 해당 정점을 방문했음을 표시
queue[rear++] = adjacent; // 큐에 해당 정점 추가
}
}
}
}이 코드는 그래프의 너비 우선 탐색(BFS)을 수행하는 함수 BFS를 정의한다. 이 함수는 시작 정점에서 시작하여 인접한 모든 정점을 방문하고, 이를 반복하여 그래프를 탐색한다. 방문한 정점은 visited 배열에 기록되며, 탐색 대기 중인 정점은 queue에 저장된다.
void BFS(Graph* g, int s): 이 함수는 그래프g에서 시작 정점s를 기준으로 너비 우선 탐색을 수행한다. 이 탐색은 각 정점을 한 번씩 방문하며, 그 과정에서 큐를 사용하여 탐색할 정점을 관리한다.
프림 알고리즘
void prim() {
T = {}; // 선택된 간선의 집합 T 초기화
W = {임의의 시작 정점}; // 선택된 정점의 집합 W를 시작 정점으로 초기화
while (T에 n-1개 이하의 간선이 포함되어 있고, E가 공집합이 아닐 때) {
E에서 W와 연결된 간선 중 최소 비용인 간선 {v, w}를 선택;
if ({v, w}가 T 내에서 사이클을 생성하지 않음) {
T = T ∪ {{v, w}}; // 선택한 간선 추가
W = W ∪ {v, w}; // 선택한 정점 추가
}
}
}이 코드는 프림 알고리즘을 구현하는 prim 함수의 유사 코드이다. 프림 알고리즘은 최소 신장 트리를 찾는 알고리즘으로, 간선의 가중치가 최소가 되도록 간선을 선택하고, 사이클을 형성하지 않는 간선만 추가하여 최소 신장 트리를 구성한다.
void prim(): 이 함수는 프림 알고리즘을 구현한다. 시작 정점에서 시작하여 최소 비용의 간선을 선택하고, 사이클을 형성하지 않는 간선을 최소 신장 트리에 추가한다. 이 과정은 모든 정점이 트리에 포함될 때까지 반복된다.
크루스칼 알고리즘
void kruskal() { // 크루스칼 알고리즘을 구현하는 kruskal 함수 정의
T = {}; // 최소 신장 트리를 구성하는 간선의 집합
// 모든 정점이 각각 독립적인 집합으로 시작
while (T에 n-1개 이하의 간선이 포함되어 있고, E가 공집합이 아닐 때) {
E에서 최소 비용인 간선 {v, w}를 선택; // 가장 작은 가중치를 가진 간선 선택
if ({v, w}가 T 내에서 사이클을 생성하지 않음) { // 사이클을 형성하지 않으면
T = T ∪ {{v, w}}; // 선택한 간선을 T에 추가
}
}
} 이 코드는 그래프 내의 최소 비용 신장 트리를 찾기 위한 크루스칼 알고리즘을 구현한다. 각 정점을 독립적인 집합으로 시작하여, 최소 비용 간선을 선택하고, 선택된 간선이 사이클을 형성하지 않는 경우에만 최소 신장 트리 집합 T에 추가한다.
void kruskal(): 이 함수는 가장 작은 가중치를 가진 간선을 선택하고, 선택된 간선이 사이클을 형성하지 않을 경우에만 신장 트리 집합T에 추가하여, 최소 신장 트리를 구성한다.
솔린 알고리즘
void sollin() { // 솔린 알고리즘을 구현하는 sollin 함수 정의
T = {}; // 최소 신장 트리를 구성하는 간선의 집합
// F는 그래프의 모든 정점들로 구성된 간선이 없는 숲
while (T가 완전한 하나의 트리가 아니고, E가 공집합이 아닐 때) {
for (F 내의 각각의 트리 T'에 대하여) {
T'와 다른 트리를 연결하는 E의 간선 중 최소 비용 간선 {v, w}를 선택;
T = T ∪ {{v, w}}; // 선택한 간선 추가
E에서 간선 {v, w}를 제거;
}
// T에 새로 추가된 간선을 포함하여 F를 수정
}
}이 코드는 그래프의 최소 신장 트리를 찾는 또 다른 방법인 솔린 알고리즘을 구현한다. 각 정점을 포함하는 별도의 트리로 시작하여, 각 트리를 연결하는 최소 비용 간선을 선택하고, 이를 통해 점차 하나의 최소 신장 트리를 구성한다.
void sollin(): 이 함수는 각 정점을 포함하는 별도의 트리로 시작하며, 각 트리를 연결하는 최소 비용 간선을 선택하여 하나의 최소 신장 트리를 구성한다. 선택된 간선은 신장 트리 집합T에 추가되고, 간선 집합E에서 제거된다.
요약
트리
- 트리는 논리적 계층이 있는 구조입니다.
- 트리를 구성하는 항목을 “노드(node)” 혹은 “정점(vertex)”이라고 합니다.
- 트리에서 루트는 부모를 갖지 않은 노드입니다.
- 트리에 있는 어떤 노드에 대해 그 노드로 들어오는 선의 개수를 진입 차수, 나가는 선의 개수를 진출 차수라 합니다.
- 트리에서 각 노드의 차수(degree of a node)는 진출 차수로 정의합니다.
- 트리의 차수(degree of a tree)는 트리 내의 각 노드의 차수 가운데 최대 차수로 정의합니다.
- 루트도 잎도 아닌 노드를 내부 노드라 하고 같은 부모를 갖는 노드들을 형제(sibling)라 합니다.
- 트리에서 각 노드의 레벨(level)은 루트로부터 그 노드까지 이어진 경로의 길이로 정합니다.
- 트리는 데이터의 계층 관계, 포함 관계 등을 나타내는 자료구조입니다.
- 트리에 속한 모든 노드의 차수가 2 이하인 트리를 이진 트리라고 합니다.
- 이진 트리에서 각 레벨이 허용되는 최대 개수 노드를 가질 때 그 트리를 가득 찬(perfect) 이진 트리라고 합니다.
- 높이가 k인 이진 트리가 레벨 0부터 k-2까지 다 채우고 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워졌을 때 완전(complete) 이진 트리라고 합니다.
- 트리의 각 노드를 빠짐없이 한 번씩만 방문하는 것을 순회(traverse)라고 합니다.
- 루트를 방문하는 순서에 따라 각각 전위(preorder) 순회, 중위(inorder) 순회, 후위(postorder) 순회라고 구분하여 부릅니다.
스레드 트리
정해진 순회 방법에 따른 방문 순서를 유지하는 스레드(thread)라는 포인터를 갖는 이진 트리를 스레드 트리라고 합니다.
오른쪽 스레드는 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리키고 왼쪽 스레드는 그 노드의 선행 노드를 가리킵니다.
스레드를 구현할 때 스레드를 저장하는 포인터를 추가하는 방법이 있습니다.
스레드를 구현할 때 이진 트리를 위한 연결 리스트의 노드 구조를 그대로 사용하면서, 잎 노드에 있는 사용하지 않는 포인터를 활용하는 방법입니다.
노드가 n개인 이진 트리를 연결 리스트로 구현할 때 NULL 포인터는 항상 2n-(n-1) = n+1개가 존재합니다.
잎 노드에 있는 포인터를 활용할 때는 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브 트리에 대한 포인터인지 구분하기 위해 하나 혹은 두 개의 플래그 필드를 사용합니다.
힙
힙은 무엇인가를 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조를 상징합니다. 그리고 힙은 우선순위 큐의 한 종류입니다.
힙은 완전 이진트리이며, 최소힙은 루트가 최소값이고 최대힙은 최대값입니다.
최대힙은 트리의 모든 노드가 자식 노드보다 큰 값을 갖는 것을 알 수 있습니다.
최소힙은 트리의 모든 노드가 자식 노드보다 작은 값을 갖는 것을 알 수 있습니다.
힙에서 노드를 삭제한 후에도 완전 이진트리의 모습을 유지해야 하며, 최대힙 혹은 최소힙의 조건을 만족해야 합니다.
선택 트리, 숲, 이진 트리 개수
차례로 정렬된 데이터 리스트 A가 있다고 가정할 때, 그것들을 유지하는 하나의 리스트로 만드는 과정을 합병 정렬이라고 합니다.
합병 정렬에서 사용하는 특수한 트리가 선택 트리입니다.
선택 트리에는 승자 트리와 패자 트리 두 종류가 있습니다.
승자 트리는 각 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진 트리(실제로는 포화 이진 트리)입니다.
승자 트리 구축 과정은 작은 값이 승자로 올라가는 토너먼트 경기와 유사합니다. 즉, 트리의 각 내부 노드는 두 자식 노드의 값 중 승자를 자신의 값으로 합니다.
선택 트리를 사용하는 경우, 트리의 레벨은 ( \log n + 1 )이므로, 선택 트리를 재구성하는 시간은 ( O(\log n) )이고, 따라서 n개의 데이터를 모두 합병하는데 필요한 계산 복잡도는 ( O(n \log n) )입니다.
패자 트리는 루트 노드 위에 최상위 0번 노드를 갖습니다. 이 0번 노드에는 경쟁에서 이긴 최종 승자를 저장합니다.
패자는 부모 노드에 저장하고, 승자는 부모의 부모 노드로 올라가서 다시 경쟁합니다. 따라서 루트에는 마지막 토너먼트의 패자를 저장하고, 최종 승자는 0번 노드에 저장합니다. 분리된 트리 모임을 숲이라 부르며, 숲은 ( n ) (또는 그 이상) 개의 분리된 트리 집합입니다.
숲을 이진 트리로 바꾸려면 먼저 각 트리를 이진 트리로 바꿉니다. 이때 각 트리의 루트는 왼쪽 서브 트리만을 갖습니다.
다음은 숲의 루트를 최상위 루트로 하고, 왼쪽 자식은 그 왼쪽 서브 트리(오른쪽 서브 트리는 없습니다), 오른쪽 자식은 나머지들의 이진 트리가 되도록 합니다.
어떤 이진 트리에 대한 전위, 중위 순회 방문 순서가 주어지면, 트리 구조를 유일하게(한 개) 정할 수 있습니다. 1부터 n까지의 수를 스택에 넣었다가 가능한 모든 방법으로 삭제하여 생성할 수 있는 경우의 수와 n개의 노드를 가진 서로 다른 이진 트리의 수가 같습니다.
중위 순회 방문 순서가 주어지면 트리 구조를 유일하게（한 개） 정할 수 있습니다.
1부터 n까지 수를 스택에 넣었다가 가능한 모든 방법으로 삭제하여 생성할 수 있는 경우의 수와 n개의 노드를 가진 상이한 이진트리의 수가 같습니다.
BS, Splay, AVL, BB
트리에 특정 데이터가 있는지를 검색하고, 노드를 자주 삽입, 삭제하는 응용 문제에 가장 효과적인 이진 트리는 이진 탐색 트리(binary search tree)입니다.
키는 각 노드를 식별하기 위해서는 별도의 간단한 이름을 붙여준 것으로 노드의 데이터라고 생각할 수 있습니다.
이진 탐색 트리는 전위 순회, 중위 순회 및 후위 순회로 모든 정점을 차례로 순회할 수 있고 트리 내의 특정 정점을 탐색할 수도 있습니다.
이진 탐색 트리에서 새 노드는 항상 잎으로 삽입합니다. 즉, 루트부터 킷값을 비교하며 자기가 삽입될 위치가 왼쪽이냐 오른쪽이냐를 정하며 내려갑니다.
Splay 트리는 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 이진 탐색 트리입니다.
Splay 트리는 Splay 연산을 적용하여 최근에 사용하려고 접근한 노드 x를 루트에 위치시켜 트리를 재구성합니다.
AVL 트리는 노드 의 왼쪽 서브트리 높이와 의 오른쪽 서브트리 높이가 최대 1만큼 차이가 난다는 조건을 만족하는 트리입니다.
트리의 높이란 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값으로 루트로부터 잎까지 가장 긴 경로 길이를 말합니다.
트리의 무게는 트리에 속한 잎 노드의 개수로 정의합니다.
무게가 균형 잡힌 트리란 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리입니다. 이 트리를 무게가 균형 잡힌 트리(weight-balanced tree) 또는 BB-트리(bound-balanced)라고 부릅니다.
AVL 또는 BB 트리에 대하여 각각 높이 또는 크기 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작습니다.
삽입이나 삭제 후에 트리를 완전히 균형 잡히게 유지하기 위해서는 Ο(n)개의 노드를 옮겨야 하는 반면에 AVL 또는 BB 트리는 Ο(log₂n)개의 노드를 옮기면 되는 것으로 알려졌습니다.
멀티웨이 탐색 트리 1
트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리를 m원 탐색 트리라고 합니다.
m원 탐색 트리는 이진 탐색 트리를 확장한 것으로 탐색 트리의 제한을 따르되 2개 이상(m개 이하) 자식을 가질 수 있습니다.
인덱스 구조를 구현하는데 가장 일반적으로 사용하는 방법으로 차수가 m인 B트리가 있습니다.
B트리는 루트와 잎 노드를 제외한 트리의 각 노드는 최소 ⌈/2⌉개의 서브트리를 갖습니다.
B트리의 루트는 최소한 2개의 서브트리를 갖습니다.
B트리의 모든 잎 노드는 같은 레벨에 있습니다.
B트리의 삽입 연산에서 노드가 꽉 차있는 경우는 분리해서 키값과 포인터를 재분배해야 합니다.
B트리 삭제 연산에서 삭제 결과 개수가 부족하면 그 노드를 다른 노드와 묶어야 합니다.
노드의 약 2/3 이상이 차야하는 B트리를 B*트리라고 합니다.
B *트리는 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮깁니다.
B+트리는 인덱스된 순차 파일을 구성하는데 사용합니다. 인덱스된 순차 파일은 데이터를 차례로 처리하는 순차 처리와 특정 데이터를 직접 찾아 처리하는 두 가지를 모두 효율적으로 할 수 있는 구조입니다.
B+트리는 잎 노드의 마지막 포인터는 다음 키값을 갖는 노드를 가리킵니다. 따라서 순차 처리를 할 때는 이 포인터를 이용해서 차례로 다음 데이터에 접근해서 처리할 수 있습니다.
B+트리에서는 모든 키값이 잎 노드에 있고 그 키값에 대응하는 실제 데이터에 대한 주소를 잎 노드만이 가지고 있습니다.
멀티웨이 탐색 트리 2
차수가 2인 노드를 2-노드, 3인 노드를 3-노드라 합니다.
2-노드와 3-노드만으로 구성한 트리를 2-3 트리라 합니다. 이 트리는 균형이 잡힌 B 트리 계열과 거의 같은 성능을 유지하면서도 상대적으로 삽입과 삭제가 용이합니다.
2-노드, 3-노드, 및 4-노드만으로 구성한 트리를 2-3-4 트리라 합니다. 이 트리는 2-3트리와 같은 특성을 갖습니다. 대신 같은 수의 노드를 더 낮은 레벨로 구축할 수 있습니다.
2-3-4 트리는 4노드를 갖기 때문에 경우에 따라서는 기억 장소를 낭비할 수 있습니다. 기억장소를 효율적으로 사용하기 위해 2-3-4 트리를 이진 트리로 나타낸 것이 레드 블랙 트리입니다.
그래프 1
정점 집합 V와 간선 집합 E에 대하여 그래프는 G=(V,E)입니다. 즉, 대상(V)과 그 대상들의 관계(E)를 나타내는 수단입니다.
방향 그래프는 간선의 방향이 유의미한 그래프로 예를 들어 부자 관계를 그래프로 나타내면 간선은 유의미 합니다.
무방향 그래프는 간선의 방향이 무의미한 그래프로 예를 들어 두 지점 사이에 도로가 있는 지 아닌지를 그래프로 나타내면 간선은 무의미합니다. 단, 도로가 일방통행로라면 간선의 방향은 의미를 갖고 그 그래프는 방향 그래프로 나타내야 합니다.
두 정점쌍이 간선을 여러 개 가질 수 있는 그래프를 다중 그래프라 합니다. 예를 들어 두 지점사이에 여러 교통수단이 있다면 다중 그래프로 나타 낼 수 있습니다.
두 정점을 잇는 간선이 중요도나 비용 등을 나타내는 가중 값을 갖는 그래프를 가중 그래프라고 합니다. 예를 들어 두 지점 사이를 연결 하는 도로의 거리가 중요한 의미를 갖는 문제라면 그 그래프는 가중 그래프로 표현해야 합니다.
두 정점을 잇는 간선 열을 경로라 합니다. 그리고 경로에 있는 간선의 수를 그 경로의 경로 길이로 정의합니다.
한 정점에서 출발하여 자신으로 연결하는 간선을 루프라고 합니다. 예를 들어 입력에 따라 상태가 변하는 시스템을 그래프로 나타내는 경우 어떤 입력에 대해서는 상태가 변하지 않는다면 루프로 표현할 수 있습니다.
시작점과 끝점이 같은 경로를 사이클이라 합니다. 그리고 하나 이상의 사이클을 갖는 그래프를 사이클이 있는 그래프 혹은 사이클 그래프라 하고 사이클이 없는 그래프를 무 사이클 그래프 혹은 트리라고 합니다.
두 정점이 간선으로 연결되었을 때 두 정정이 인접한다고 표현합니다. 두 정점이 잇는 경로가 있다는 것과 반드시 구분해야 합니다.
그래프의 표현방법의 하나로 정점 사이의 인접성을 행렬로 나타낸 것을 인접행렬 표현법이라 하고 정점 사이의 인접성을 연결 리스트로 나타낸 것을 인접 리스트 표현법이라 합니다. 그래프가 정점 개수에 비하여 간선 개수가 적으면 연결 리스트로 나타내야 기억 장소를 효율적으로 사용할 수 있습니다.
그래프 2
그래프 내 특정 정점을 찾는 연산을 그래프 탐색이라 합니다. 그래프는 트리와 다르게 루트노드가 없으므로 시작을 나타내는 특정 정점이 주어집니다. (트리에서 노드로 부르는 것을 그래프에서는 보통 정점이라 합니다. 이 책은 그렇게 용어를 사용했습니다.)
특정 정점에서 시작하여 그래프의 모든 정점을 빠짐없이 그리고 중복 없이 방문하는 것을 그래프 순회라고 합니다. 그래프 탐색은 순회를 통하여 정점을 방문하다가 정해진 정점을 만나면 탐색 성공이고 모든 정점을 방문해도 정해진 정점을 만나지 못하면 실패입니다.
깊이 우선 탐색은 특정 점정에서 시작하여 자손을 먼저 방문 한 후 (더 이상 방문 할 자손이 없으면) 전 단계 형제를 방문하는 알고리즘입니다. 그래프는 루트가 없고 간선에 방향도 없으므로 어려워합니다. 시작 정점을 위에 올려놓고 생각하면 다소 쉬워집니다. 특히 시각적으로 더 위에 있는 것이 더 깊은 곳일 수 도 있음을 받아들이면 이해에 도움이 됩니다.
너비 우선 탐색은 특정 정점에서 시작하여 모든 형제를 방문한 후 자손을 방문하는 순서를 따릅니다. 자식이 여러 개인 경우 그것들의 순서를 정하는 규칙만 정하면 역시 어렵지 않게 이해 할 수 있습니다.
그래프의 모든 정점을 포함하는 사이클이 없는 부분 그래프 즉, 트리를 신장트리라 합니다. 그리고 가중 그래프에서 비용이 최소인 신장 트리를 최소 비용 신장 트리라 합니다. 대표적으로 프림, 크루스컬, 및 솔린 알고리즘을 사용합니다. 모두 사람 이름입니다.
프림 알고리즘은 최소비용을 갖는 간선을 차례로 추가하는 방법으로 트리를 구축합니다. 물론 사이클이 형성되면 해당 간선은 포기합니다. 비용이 적은 것을 합치면 그들의 합이 최소가 될 것이라는 (항상 옳지는 않은) 가정을 근거로 합니다.
크루스컬 알고리즘 프림 알고리즘처럼 현재 완성한 트리에 간선을 붙여 트리를 키워나가는 것이 아닙니다. 이 알고리즘은 매 단계 최소 비용 간선을 선택해 사이클만 형성하지 않으면 받아 들이는 것입니다. 그러니까 중간 과정은 (트리가 아니고) 숲 일 수 있습니다.
솔린 알고리즘은 앞 두 방법과 다르게 매 단계에 다수의 간선을 선택합니다. 먼저 간선이 하나도 없고 그래프의 모든 정점들로 구성된 숲에서 시작합니다. 그리고 단계가 거듭되면서 숲 내의 트리를 최소 비용을 갖는 간선으로 연결합니다. 이 과정을 남은 간선이 없거나 완전한 트리가 생성될 때까지 반복하면 신장 트리를 얻습니다.
'CS > 자료구조' 카테고리의 다른 글
| 방송통신대학교 자료구조 기말 시험 대비 예상 문제 - OX 유형 (0) | 2023.12.02 |
|---|---|
| 방송통신대학교 자료구조 기말 시험 대비 예상 문제 - 적합한 코드 찾기 유형 (0) | 2023.12.02 |
| 자료구조 슈도 코드 및 개념 요약 정리 : 배열, 스택, 큐, 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 (0) | 2023.12.02 |
| 자료구조 문제 풀이 (0) | 2023.11.26 |
| 멀티웨이 탐색 트리 2 : 2-3 트리, 2-3-4 트리, 레드 블랙 트리 (1) | 2023.11.26 |