JUNGLE 240415 ~ 240417 (W04)

in Study #Jungle

KRAFTON JUNGLE Week 04

1. Keywords

포인터 (Pointer)

  • int* : int 형에 대한 포인터
  • int* const : int 형 상수에 대한 포인터 (상수 변경 X)
  • const int* : int 형에 대한 포인터 상수 (포인터 변경 X)
  • const int* const : 상수를 가리키는 상수 포인터
  • void* : 어떤 형식의 데이터도 가리킬 수 있는 포인터

BST에서의 삭제

BSTNode* removeNodeFromTree(BSTNode *root, int value)
{
	/* add your code here */
	// 1. 트리가 비어있다면 NULL 반환
	if (root == NULL)
		return NULL;

	// 2. 삭제할 노드 탐색 (재귀)
	if (value < root->item) {
		root->left = removeNodeFromTree(root->left, value);
	}

	else if (value > root->item) {
		root->right = removeNodeFromTree(root->right, value);
	}

	// 3. 삭제할 노드 찾았으면,
	else {
		// 3-1. 삭제할 노드의 자식이 없으면 걍 삭제 ㄱ
		if (root->left == NULL && root->right == NULL) {
			free(root);
			return NULL;
		}

		// 3-2. 삭제할 노드의 자식이 1개면?? 대체
		else if (root->left == NULL) {
			BSTNode* tmp = root->right;
			free(root);
			return tmp;
		}
		else if (root->right == NULL) {
			BSTNode* tmp = root->left;
			free(root);
			return tmp;
		}

		// 3-3. 삭제할 노드의 자식이 2개면, 
		else {
			// 오른쪽 최솟값 올리고
			BSTNode* tmp = findMinValue(root->right);
			root->item = tmp->item;		// 값 갱신
			root->right = removeNodeFromTree(root->right, tmp->item);	// 오른쪽에서 재귀적으로 삭제 작업
		}
	}
	return root;
}
  • 트리가 비어있다면 NULL 반환
  • 삭제할 노드를 재귀로 탐색
  • 삭제할 노드를 찾았다면, (3가지 경우를 따져줘야 함)
    1. 삭제할 노드의 자식이 없는 경우
    2. 삭제할 노드의 자식이 1개인 경우
    3. 삭제할 노드의 자식이 2개인 경우

B-Tree 삽입과 삭제

영상 참고: Click!!

B-Tree 삽입

삽입 과정

  • 트리가 비어있다면, 루트 노드를 할당하고 K 삽입
  • 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드 탐색
  • 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료
  • 리프 노드가 부적절한 상태에 있다면 분리
  1. 분할이 일어나지 않는 경우
    • 리프 노드가 넘치지 않았다면, 오름차순으로 K 삽입
  2. 분할이 일어나는 경우
    • 리프 노드에 key 노드가 가득 찬 경우, 노드를 분할
B-Tree 삭제

재조정 과정

  • key 수가 여유있는 형제의 지원을 받는다.
  • 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
  • 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.
  1. 리프 노드에서 삭제하고 재조정 할 필요 없는 경우
  2. 리프 노드에서 삭제하고 재조정 해야하는 경우
    • key 수가 여유있는 형제의 지원을 받을 수 있는 경우
    • key 수가 여유있는 형제의 지원을 받을 수 없는 경우에는 부모의 지원을 받고 형제와 합친다.
  3. internal 노드에서 데이터를 삭제하는 경우
    • 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.

2. C Pointer Quiz

Q24.

#include <stdio.h>
 
int main()
{
 int var;  /*Suppose address of var is 2000 */
 
 void *ptr = &var;
 *ptr = 5;
 printf("var=%d and *ptr=%d",var,*ptr);
              
 return 0;
}
  • void 포인터를 역참조 하는 것은 허용되지 않음
  • void가 불완전한 데이터 유형이기 때문
  • 따라서 올바른 방법은 void 포인터를 형변환하고 그 다음에 사용하는 것
  • A. *ptr -> (int *)ptr