그림으로 쉽게 배우는 자료구조와 알고리즘: 미션1 | 메모리 검색

development-logo

들어가며

소프트웨어를 개발할 때 메모리 관리 방식은 프로그램의 안정성과 성능을 좌우하는 핵심 요소입니다. 특히 자바스크립트, Python, C# 같은 매니지드 언어(Managed Language)에서는 가비지 컬렉터(Garbage Collector)가 자동으로 메모리를 수집하고 해제하여 개발자가 직접 메모리 할당·해제에 신경 쓰지 않아도 되지만, 내부적으로 어떤 원리로 동작하는지를 이해하는 일은 여전히 중요합니다.

그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)

이번 스터디에서는 “그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)” 강의를 통해, 다양한 자료구조와 알고리즘의 개념을 학습해 왔습니다. 그중 하나의 미션으로, AVL 트리를 이용해 가비지 컬렉터의 메모리 검색 기능을 직접 구현해 보고, 그 과정을 정리하여 공유하고자 합니다.

미션

이번 미션에서는 “매니지드 언어의 가비지 컬렉터에서 메모리 검색 기능을 구현”하는 것이 목표입니다.
요구사항은 다음과 같습니다.

빈 메모리 블록 삽입(insertFreeMemory)
- 내부적으로 빈 메모리 블록(크기)을 관리하는 자료구조를 구축해야 합니다.
- AVL 트리를 사용하여 빈 블록을 삽입합니다.
메모리 요청 시 검색(searchFreeMemory)
- 사용자가 요청한 크기(requestSize)에 딱 맞는 블록이 있다면 그것을 반환합니다.
- 딱 맞는 블록이 없으면, 요청 크기보다 큰 블록들 중에서 가장 작은 크기의 블록을 반환합니다.
- 반환된 노드는 즉시 할당된 것으로 간주하고, 빈 블록 목록에서 제거해야 합니다.
반환된 블록 삭제(releaseFreeMemory)
- searchFreeMemory를 통해 선택된 빈 블록의 크기를 AVL 트리에서 삭제합니다.

전제 조건: 같은 크기의 빈 메모리 블록은 존재하지 않는다고 가정합니다.

구현 개요

자료구조

빈 메모리 블록을 삽입/삭제/검색하는 연산이 모두 O(log N)에 이루어지는 AVL 트리를 사용합니다.

클래스 구조

JavaScript

import { AVLTree } from "../../avlTree/avlTree.mjs";

class GarbageCollector {
  constructor() {
    this.avlTree = new AVLTree();
  }

  // 빈 메모리 블록 삽입
  insertFreeMemory(size) {
    this.avlTree.root = this.avlTree.insert(this.avlTree.root, size);
  }

  // 요청 크기 이상인 블록 검색
  searchFreeMemory(requestSize) {
    let current = this.avlTree.root;
    let candidate = null;

    while (current) {
      const nodeSize = current.getData();

      if (nodeSize === requestSize) {
        // 정확히 같은 크기를 찾으면 즉시 반환
        candidate = current;
        break;
      }
      if (nodeSize > requestSize) {
        // 후보로 저장한 뒤, 더 작은 후보를 찾기 위해 왼쪽 서브트리 탐색
        candidate = current;
        current = current.getLeftSubTree();
      } else {
        // 노드 크기가 요청 크기보다 작으면 오른쪽 서브트리로 탐색
        current = current.getRightSubTree();
      }
    }

    return candidate;
  }

  // 반환된 블록(크기) 삭제
  releaseFreeMemory(size) {
    this.avlTree.root = this.avlTree.remove(this.avlTree.root, size);
  }
}

JavaScript

테스트 흐름

빈 메모리 블록(64, 48, 87, 13, 102, 34, 61, 40, 6)을 차례대로 삽입
searchFreeMemory(64) 호출 → 크기 64 노드를 찾아 반환 → 즉시 삭제
searchFreeMemory(42) 호출 → 42 이상 중 최소값(48)을 찾아 반환 → 즉시 삭제

구현 코드 전체

JavaScript

import { AVLTree } from "../../avlTree/avlTree.mjs";

class GarbageCollector {
  constructor() {
    this.avlTree = new AVLTree();
  }

  // 빈 메모리 블록 삽입
  insertFreeMemory(size) {
    this.avlTree.root = this.avlTree.insert(this.avlTree.root, size);
  }

  // 요청 크기 이상인 블록 검색
  searchFreeMemory(requestSize) {
    let current = this.avlTree.root;
    let candidate = null;

    while (current) {
      const nodeSize = current.getData();

      if (nodeSize === requestSize) {
        candidate = current;
        break;
      }
      if (nodeSize > requestSize) {
        candidate = current;
        current = current.getLeftSubTree();
      } else {
        current = current.getRightSubTree();
      }
    }

    return candidate;
  }

  // 반환된 블록(크기) 삭제
  releaseFreeMemory(size) {
    this.avlTree.root = this.avlTree.remove(this.avlTree.root, size);
  }
}

// 실행
const gc = new GabageCollector();
console.log("========== 빈 메모리 영역 초기화 ==========");
gc.insertFreeMemory(64); // 빈 64바이트 삽입
gc.insertFreeMemory(48); // 빈 48바이트 삽입
gc.insertFreeMemory(87); // 빈 87바이트 삽입
gc.insertFreeMemory(13); // 빈 13바이트 삽입
gc.insertFreeMemory(102); // 빈 102바이트 삽입
gc.insertFreeMemory(34); // 빈 34바이트 삽입
gc.insertFreeMemory(61); // 빈 61바이트 삽입
gc.insertFreeMemory(40); // 빈 40바이트 삽입
gc.insertFreeMemory(6); // 빈 6바이트 삽입

// 64바이트 요청 → 64 찾기 → 삭제
let freeMemory1 = gc.searchFreeMemory(64); // 64바이트 메모리
console.log(freeMemory1);
if (freeMemory1) {
  gc.releaseFreeMemory(freeMemory1.data);
}

// 42바이트 요청 → 42 이상 중 최소값(48)을 찾아 반환 → 삭제
let freeMemory2 = gc.searchFreeMemory(42); // 48바이트 메모리 획득
console.log(freeMemory2);
if (freeMemory2) {
  gc.releaseFreeMemory(freeMemory2.data);
}

JavaScript

실행 결과

아래는 위 코드를 Node.js에서 실행했을 때 출력된 콘솔 로그 입니다.

PowerShell

========== 빈 메모리 영역 초기화 ==========
BinaryTree {
  data: 64,
  leftSubTree: BinaryTree {
    data: 48,
    leftSubTree: BinaryTree {
      data: 34,
      leftSubTree: BinaryTree {
        data: 13,
        leftSubTree: [BinaryTree],   // data: 6
        rightSubTree: null,
        height: 2
      },
      rightSubTree: BinaryTree {
        data: 40,
        leftSubTree: null,
        rightSubTree: null,
        height: 1
      },
      height: 3
    },
    rightSubTree: BinaryTree {
      data: 61,
      leftSubTree: null,
      rightSubTree: null,
      height: 1
    },
    height: 4
  },
  rightSubTree: BinaryTree {
    data: 87,
    leftSubTree: null,
    rightSubTree: BinaryTree {
      data: 102,
      leftSubTree: null,
      rightSubTree: null,
      height: 1
    },
    height: 2
  },
  height: 5
}
BinaryTree {
  data: 48,
  leftSubTree: BinaryTree {
    data: 34,
    leftSubTree: BinaryTree {
      data: 13,
      leftSubTree: [BinaryTree],  // data: 6
      rightSubTree: null,
      height: 2
    },
    rightSubTree: BinaryTree {
      data: 40,
      leftSubTree: null,
      rightSubTree: null,
      height: 1
    },
    height: 3
  },
  rightSubTree: null,
  height: 4
}

PowerShell

첫 번째 결과(data: 64 트리)
- 모든 빈 메모리 블록(64, 48, 87, 13, 102, 34, 61, 40, 6)을 AVL 트리에 삽입한 직후의 구조입니다.
- 루트가 64이며, 왼쪽 서브트리는 48(그 아래 34→13과 40, 오른쪽 61), 오른쪽 서브트리는 87(→102)으로 균형이 잡혀 있습니다.
두 번째 결과(data: 48 트리)
- searchFreeMemory(64)로 “64 노드”를 찾아 반환했기 때문에, 내부적으로 releaseFreeMemory(64)가 호출되어 AVL 트리에서 64가 삭제되었습니다.
- 그 뒤 searchFreeMemory(42)를 실행하여, “42 이상인 값 중 최소값”인 48을 찾아 반환했습니다.
- 출력된 트리는 48을 루트로 삼고, 왼쪽에 34(→13, 6, 40)만 남은 구조입니다. (오른쪽 서브트리 없음)

세부 노드 제거 및 회전 과정을 거쳐 AVL 균형이 정상적으로 유지됨을 확인할 수 있습니다. 따라서 요구사항대로 “정확히 같은 크기 노드 우선 반환 → 삭제”와 “크기 이상의 값 중 최소값 반환 → 삭제”가 올바르게 구현되었음을 검증했습니다.

느낀 점

AVL 트리의 실전 활용
- 삽입, 삭제, 검색이 모두 로그 시간에 동작하기 때문에, 빈 메모리 블록이 많아질 때도 성능을 보장할 수 있다는 점을 체감했습니다.
검색 로직 작성 시 주의사항
- “정확히 같은 크기가 없을 때, 그보다 큰 값 중 최소값을 찾는 후보(candidate)” 로직을 루트부터 내려가며 올바르게 업데이트해야 합니다.