이번에는 저번 글에 이어서 동적 메모리 할당기의 종류에 대해 알아보자. 일단 메모리 할당기는 크게 두 가지 분류로 나눌 수 있다. Implicit allocator implicit allocator는 자바나 자바스크립트 등의 언어에서의 garbage collector 역할을 하는 동적 메모리 할당기이다. 이 할당기들은 Heap에서 특정 메모리 공간이 더 이상 참조되지 않을 때, 참조되지 않는다는 것을 detecting 하여 스스로 메모리를 반환시키는 할당기들이다. Explicit allocator 오늘 중점적으로 알아볼 할당기이다. explicit allocator는 implicit allocator와는 달리 응용 프로그램이 특정 메모리 공간을 반환한다고 명시적으로 요청해야 한다. 즉 더 이상 사용하지 ..
동적 메모리 vs 정적 메모리 우리가 특정 프로세스를 실행하면, 운영체제는 실행된 프로세스에게 특정 메모리 공간을 할당해 준다. 그 메모리 공간을 그림으로 간단하게 나타내면 아래와 같다. 위의 그림에서 .bss, .data, .text 영역은 정적인 데이터들이 저장되는 공간이다. 정적 메모리는 데이터들이 컴파일 단계에서 메모리 할당이 이루어지는 공간이다. 이와 달리 Heap 영역이나 Stack 영역은 컴파일 이후에 프로그램이 실행되고 나서 메모리 할당이 발생하는 공간이다. Stack 영역은 함수의 지역 변수 또는 매개 변수가 저장되는 공간이고, Heap 영역이 바로 우리가 malloc 또는 free 함수를 통해 변수에 메모리를 할당하고 해제할 수 있는 영역이다. 이렇게만 표현해서는 정확히 정적 메모리와 ..
RB Tree란? Red-Black Tree는 이진 탐색 트리의 한 종류이다. 가장 기본적인 형태의 이진 탐색 트리는 최악의 경우 트리의 높이가 n으로 나타나 비효율적인 면이 있는데, 이를 보완하기 위해 삽입 또는 삭제 연산 시 트리의 균형을 맞추는 트리들이 나타났다. 이를 자가 균형 트리라고 부르며, 대표적으로 AVL Tree와 Red-Black Tree가 있다. 이번에는 Red-Black Tree에 대해 알아보자. RB Tree에는 총 다섯 가지의 규칙이 있으며, 이 규칙을 통해 트리의 밸런스를 유지한다. 다섯 가지의 규칙은 아래와 같다. RB Tree의 다섯 가지 규칙 1. 모든 노드는 빨간색 혹은 검은색 노드이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드들은 검은색이다. 4. 빨간색 노..
