알고리즘 심화: 균형 트리와 그래프 탐색 기초

편향 트리의 성능 문제를 해결하는 레드-블랙 트리와 B-트리, 그리고 데이터 간의 관계를 탐색하는 DFS와 BFS의 핵심 원리를 정리합니다.

1. 스스로 균형을 잡는 트리

• 레드-블랙 트리 (Red-Black Tree): 각 노드에 색상을 부여하고 규칙에 따라 삽입/삭제 시 트리의 높이를 조정합니다. 자바의
  text

  TreeMap

  이나
  text

  TreeSet

  의 내부 구현으로 사용될 만큼 신뢰받는 알고리즘입니다.
• B-트리 (B-Tree): 노드 하나에 여러 개의 키를 저장할 수 있는 다진 검색 트리입니다. 트리의 높이를 매우 낮게 유지할 수 있어, 디스크 접근 횟수를 줄여야 하는 데이터베이스 인덱스에 주로 사용됩니다.

2. 그래프 탐색 알고리즘

데이터 간의 연결 관계(간선)가 복잡한 그래프 구조를 훑는 방식은 크게 두 가지입니다.

• DFS (깊이 우선 탐색): 한 방향으로 갈 수 있을 때까지 깊게 들어갑니다. 스택이나 재귀를 이용하며, 미로 찾기나 모든 경로를 확인해야 하는 문제에 유리합니다.
• BFS (너비 우선 탐색): 시작점에서 가까운 노드들부터 순차적으로 방문합니다. **큐(Queue)**를 이용하며, 최단 경로를 찾는 문제에서 강력한 위력을 발휘합니다.