RB-Tree 구현하기 (C언어) - Part.4 삽입 구현

전 포스팅에서 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가지 규칙)모든 노드는 레드 또는 블랙..

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 22.
• textsms

RB-Tree 구현하기 (C언어) - Part.3 삽입 이론 설명

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

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 21.
• textsms

RB-Tree 구현하기 (C언어) - Part.2 최소, 최대, 출력 구현

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에서 최소 값과 최댓값을..

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 21.
• textsms

RB-Tree 구현하기 (C언어) - Part.1 설명 및 뼈대 구현

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

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 20.
• textsms

컴퓨터 시스템 : CSAPP 9장 정리 - 9.8 메모리 매핑

9.8 메모리 매핑 (Memory Mapping)리눅스는 가상 메모리 영역의 초기 내용을 디스크 상의 객체에 연결(mapping)함으로써 초기화한다. 이를 메모리 매핑(memory mapping)이라고 한다. 가상 메모리 영역은 다음 두 종류의 객체 중 하나에 매핑될 수 있다:일반 파일예: 실행 파일, 객체 파일 등.파일의 일부분을 페이지 단위로 나누어 가상 페이지에 대응시킨다.요구 페이징(demand paging)을 사용하므로, 해당 페이지에 실제 접근하기 전까지는 메모리에 로드되지 않는다.영역 크기가 파일보다 크면, 나머지 공간은 0으로 패딩 된다.익명 파일(anonymous file)커널이 생성한, 내용이 모두 0으로 채워진 임시 객체.이 영역의 페이지에 처음 접근할 때, 커널이 물리 메모리에서 희..

• format_list_bulleted 크래프톤 정글 (컴퓨터 시스템: CSAPP)/9장 가상 메모리
• · 2025. 4. 20.
• textsms

컴퓨터 시스템 : CSAPP 9장 정리 - 9.7 사례 연구 : 인텔 코어 i7/리눅스 메모리 시스템

9.7 Intel Core i7/Linux 메모리 시스템 사례 연구지금까지 설명한 가상 메모리 개념들을 실제 시스템에 적용한 사례로, Intel Core i7에서 Linux가 사용하는 메모리 시스템을 다룬다.Core i7 아키텍처 개요하스웰(Haswell) 마이크로아키텍처는 64비트 가상 및 물리 주소 공간을 지원한다.현재 Core i7 구현은 다음을 지원한다:48비트 가상 주소 공간 (256TB)52비트 물리 주소 공간 (4PB)**32비트 호환 모드 (4GB 주소 공간)**도 존재한다.Core i7 메모리 구성4개의 코어, 공유 L3 캐시, DDR3 메모리 컨트롤러 포함각 코어는 다음을 포함함:L1 i-TLB (128 entries), L1 d-TLB (64 entries), L2 TLB (512 e..

• format_list_bulleted 크래프톤 정글 (컴퓨터 시스템: CSAPP)/9장 가상 메모리
• · 2025. 4. 20.
• textsms