실패하면 디버그 성공하면 리눅스 아닙니까!안녕하세요 6주 차 RB-Tree 트리 생성 발표를 맡은 고웅입니다.어쩌다 보니 2주 연속 오프닝을 맡게 되었습니다??우선 저는 RB-Tree를 구현하며 가장 처음 만나게 되는 생성함수에 대한 발표를 맡았습니다.너무 쉬운거 맡아서 날먹 하려고 하네?? 맞습! 아!👊(퍽!) 아닙니다. 😅제가 트리 생성을 발표하려던 이유는 제가 겪었던 디버깅의 추억?을 소개 시켜드리기 위해서 이런 쉬운 주제를 냉큼 주웠습니다.먼저 오늘 준비된 코드부터 보시죠🔬구현 코드rbtree *new_rbtree(void) { rbtree *p = (rbtree *) calloc(1, sizeof(rbtree)); // TODO: initialize struct if needed..

이 전 포스팅으로 이진 탐색 트리나, RED-BLACK TREE를 살펴봤다. 이진 탐색 트리의 비효율성을 개선하기 위해 균형 이진 탐색 트리(Balanced Binary Search Tree)의 개념이 등장했고 RB-Tree가 이 균형 이진 탐색 트리의 종류 중 하나였다. 이번에는 또 다른 균형 이진 탐색 트리인 AVL 트리에 대해 정리하겠다.AVL 트리란?AVL 트리라는 이름은 이 자료구조를 만든 두 사람, Adelson-Velsky와 Landis의 이름을 따서 지어졌다.모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리(BST)이다.이 높이 차이를 균형 인수(Balance Factor)라고 하며,Balance Factor=(left subtree height)−..

지난 시간에 간단하게 RB-Tree에서의 삭제를 이론적으로 살펴봤다. 이제 실제 구현을 통해 삭제에 대한 것을 설명하겠다.1. 구현 목표우리는 삭제 기능을 구현하기에 앞서 다음과 같은 기능들을 구현해야 한다.노드 삭제노드 삭제 시 노드 연결삭제 시 fixup 함수노드 기준 최소 값 찾기 (successor 탐색)2. 기능 구현🔨 노드 삭제int rbtree_erase(rbtree *t, node_t *p) { // TODO: implement to_erase}먼저 노드 삭제의 진입 함수인 erase 함수를 구현할 것이다. 이 함수는 BST의 삭제 방법에 따라 노드를 삭제하는 역할을 한다.구현 아이디어:successor, replacement 라는 노드를 가리킬 포인터 변수 생성삭제되는 노드의 색상..

이 전 포스팅에서 RB-Tree의 삽입에 대해 구현을 진행했다. 이제 RB-Tree의 마지막 관문 삭제 기능에 대해 본격적으로 구현에 들어가기 전에 이론 설명을 진행하겠다.RB-Tree 노드 삭제RB-Tree의 삭제는 일반 이진 탐색 트리(BST)처럼 노드를 제거하지만, Red-Black Tree의 5가지 속성을 유지하기 위한 추가적인 재조정(Fix-up)이 필요하다.1. 기본 삭제 절차Step 1: 일반 BST 삭제 수행삭제하려는 노드 z가 자식이 0개 또는 1개면 그대로 삭제자식이 2개인 경우, z의 후계자(successor) 노드 y를 찾아 z의 위치에 복사하고, 후계자 y를 삭제Step 2: 삭제된 노드의 색 확인삭제된 노드의 색이 Red인 경우 → 문제없음 (속성 위반 X)삭제된 노드가 Blac..

전 포스팅에서 RB-Tree에서의 삽입에 대한 이론적인 설명을 했다. 기본적으로 RB트리도 이진 탐색트리의 일종이기 때문에 삽입에서의 과정은 기존의 이진 탐색트리와 동일하다고 할 수 있다. 이제 다만 삽입 이후 RB-Tree의 조건들을 위반했을 경우 이를 고쳐나가는 fixup 과정이 추가되었다는 것이다.이 전 글을 보면 RB-Tree에서 fixup을 하는 경우는 크게 3가지로 얘기했다. Case1 ~ 3까지의 경우를 확인하며 이를 수행하는 코드를 작성해 볼 것이다.2025.04.21 - [크래프톤 정글] - RB-Tree 구현하기 (C언어) - Part.3 삽입 이론 설명 RB-Tree 구현하기 (C언어) - Part.3 삽입 이론 설명RB-Tree의 주요 속성 (5가지 규칙)모든 노드는 레드 또는 블랙..

RB-Tree의 주요 속성 (5가지 규칙)모든 노드는 레드 또는 블랙이다.루트 노드는 항상 블랙이다.모든 리프 노드(NIL 노드)는 블랙이다.레드 노드의 자식은 반드시 블랙이다.→ 즉, Red 노드는 연속해서 올 수 없다.어떤 노드에서 리프 노드까지 가는 모든 경로에는 동일한 개수의 Black 노드가 있다.→ 이를 black-height라고 한다.이 규칙을 다시 작성해 두는 이유는 이 규칙이 매우 중요하기 때문이다.삽입 연산의 개요RB-Tree의 삽입은 기본적으로 이진 탐색 트리(BST)의 삽입과 유사하다. 하지만 삽입 후에는 RB-Tree의 규칙을 깨뜨릴 수 있으므로, 삽입 후 Fix-Up(재조정) 과정을 통해 트리를 다시 균형 있게 만든다.삽입 기본 과정새 노드 생성: 새 노드는 항상 Red 색으로 ..

1. 구현 목표이전 포스팅을 통해 RB-Tree의 생성과 트리 삭제, 탐색을 다뤘다면 이번 글에서는 RB-Tree의 핵심인 삽입과 삭제를 다루기 전에 추가적으로 필요한 기능들을 구현하고 넘어가려고 한다.2025.04.20 - [크래프톤 정글] - RB-Tree 구현하기 (C언어) - Part.1 설명 및 뼈대 구현 RB-Tree 구현하기 (C언어) - Part.1 설명 및 뼈대 구현RB-Tree(Red Black Tree)란?컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진트리 자료 구조이다.각 노드에 값이 있다.값들은 전순서가 있다.노드의 왼쪽 서브트리에www.gowoong.com우리가 이번에 구현할 기능은 RB-Tree에서 최소 값과 최댓값을..

RB-Tree(Red Black Tree)란?컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진트리 자료 구조이다.각 노드에 값이 있다.값들은 전순서가 있다.노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.높이가 h인 이진 탐색 트리에서 동적 집합 연산이 O(h) 될 수 있다는 것이다. 즉 이진 탐색 트리의 경우 치우친 편향 트리 (skewed tree)가 발생할 수 있다.위의 이미지가 치우친 편향 트리의 예시인데 만약 이러한 트리에 100개의 자식이 전부 위와 같은 모양이고..

이전 포스팅에서 스택의 기본적인 기능들을 구현했다. 이번 Part3에서는 일종의 심화 기능들을 구현해 보겠다. 사실 이전 포스팅에서 생각보다 많은 기능들을 구현했다. 하지만 간단한 기능들이 다수였다. 반면 이번 기능들은 심화 기능이니 비교적 복잡하다 느낄 수 있다.1. 구현 목표get_size : 스택의 크기를 구한다.reverse_stack : 스택을 뒤집는다.copy_stack : 스택의 값을 복사한다.2. 기능 구현🔨 get_sizeget_size 함수는 스택의 사이즈를 구하는 함수이다. 스택의 사이즈를 구하는 방법은 간단하다 스택의 노드들을 반복문으로 순회하며 순회할 때마다 카운트 변수의 값을 증가시키고 반복이 끝났을 때 반환하면 끝이다.int get_size(Stack *stack) { ..

본격적인 스택 구현의 첫 시간이다. 우리는 push, pop, free_stack, peek을 구현해 볼 것이다. 만약 같이 따라 해볼 예정이라면 이전 환경설정 포스트를 확인하는 것을 추천한다.2025.04.16 - [크래프톤 정글] - 스택(Stack) 구현 (C언어) : Part.1 - 초기 환경 설정 & 구현할 함수 소개 스택(Stack) 구현 (C언어) : Part.1 - 초기 환경 설정 & 구현할 함수 소개이번에는 C언어를 이용해 스택을 직접 구현해보려고 한다. 링크드 리스트를 직접 구현했던 내용도 있으니 링크드 리스트에 대해서 부족하지만 정리했던 내용을 확인하려면 이 전 포스팅 했던www.gowoong.com1. 구현 목표init_stack : 스택의 값을 초기화 한다. (보너스)push : ..