자료구조 트리 그래프 해시테이블편집자 확인

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 두 자식 노드는 일반적으로 왼쪽 자식과 오른쪽 자식으로 구분된다.

이진 트리는 다양한 형태를 가지며, 특정한 성질에 따라 여러 종류로 분류된다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨의 노드가 채워져 있고, 마지막 레벨의 노드는 왼쪽부터 순서대로 채워지는 형태이다. 포화 이진 트리는 모든 레벨의 노드가 완전히 채워진 특별한 형태의 완전 이진 트리이다. 전 이진 트리는 모든 노드가 0개 또는 2개의 자식을 가지는 트리를 의미한다. 이러한 구조적 특성은 데이터의 저장 및 탐색 효율성에 직접적인 영향을 미친다.

이진 트리의 주요 연산은 탐색, 삽입, 삭제이며, 이를 효율적으로 수행하기 위한 특수한 형태가 이진 탐색 트리이다. 이진 탐색 트리에서는 임의의 노드를 기준으로 왼쪽 서브트리의 모든 노드 값이 현재 노드 값보다 작고, 오른쪽 서브트리의 모든 노드 값이 현재 노드 값보다 크다는 순서 속성을 가진다. 이 속성 덕분에 평균적으로 O(log n) 시간 복잡도로 탐색이 가능하다. 그러나 노드 삽입 순서에 따라 한쪽으로 치우친 편향 트리가 생성될 수 있으며, 이 경우 성능이 O(n)으로 저하될 수 있다. 이를 해결하기 위해 균형 트리가 고안되었다.

이진 트리를 순회하는 방법에는 크게 세 가지가 있다. 전위 순회는 현재 노드, 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문한다. 중위 순회는 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순으로 방문하며, 이진 탐색 트리에서 오름차순으로 값을 얻을 때 사용된다. 후위 순회는 왼쪽 서브트리, 오른쪽 서브트리, 현재 노드 순으로 방문한다. 순회 방식은 트리의 구조를 변경하지 않고 모든 노드를 방문해야 하는 작업에 활용된다.

균형 트리는 이진 탐색 트리의 한계를 보완하기 위해 도입된 자료구조이다. 일반적인 이진 탐색 트리는 노드의 삽입 순서에 따라 한쪽으로 치우친 편향 트리가 될 수 있으며, 이 경우 탐색, 삽입, 삭제 연산의 시간 복잡도가 최악의 경우 O(n)으로 악화된다. 균형 트리는 이러한 문제를 해결하기 위해 트리의 높이를 가능한 한 낮게 유지하여 연산의 효율성을 보장한다. 대표적인 균형 트리로는 AVL 트리와 레드-블랙 트리가 있다.

AVL 트리는 1962년 게오르기 아델슨-벨스키와 예브게니 란디스가 고안한 최초의 균형 이진 탐색 트리이다. 이 트리는 각 노드의 균형 인자를 유지하며, 균형 인자는 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이로 정의된다. AVL 트리는 이 균형 인자의 절댓값이 항상 1 이하가 되도록 강력한 균형 조건을 가진다. 삽입이나 삭제 후 균형이 깨지면, 회전 연산(단일 회전, 이중 회전)을 통해 트리의 균형을 복원한다. 이로 인해 모든 기본 연산의 시간 복잡도가 O(log n)으로 보장된다.

레드-블랙 트리는 AVL 트리보다 덜 엄격한 균형 조건을 가지는 트리이다. 각 노드는 빨간색 또는 검은색의 색상을 가지며, 다음 다섯 가지 규칙을 만족해야 한다.

1. 모든 노드는 빨간색이거나 검은색이다.

2. 루트 노드는 검은색이다.

3. 모든 리프 노드(NIL)는 검은색이다.

4. 빨간색 노드의 자식은 모두 검은색이다(빨간색 노드가 연속으로 존재할 수 없다).

5. 각 노드에서 리프 노드까지의 모든 경로에는 같은 수의 검은색 노드가 존재한다.

레드-블랙 트리는 삽입 또는 삭제 시 발생하는 위반 사항을 색상 변경과 회전을 통해 해결한다. AVL 트리에 비해 균형 조건이 느슨하여 삽입/삭제 시 필요한 회전 횟수가 일반적으로 적고, 따라서 삽입과 삭제가 빈번한 경우에 더 효율적일 수 있다. 반면, AVL 트리는 더 엄격한 균형으로 인해 탐색 연산이 더 빠른 경우가 많다. 두 트리 모두 데이터베이스의 인덱스, 맵이나 셋의 구현체 등 다양한 분야에서 핵심 자료구조로 활용된다.

B-트리는 이진 트리와 달리 각 노드가 두 개 이상의 자식을 가질 수 있는 다중 경로 트리이다. 데이터베이스와 파일 시스템에서 대량의 데이터를 효율적으로 관리하기 위해 설계되었다. 모든 리프 노드는 같은 깊이를 유지하는 균형 트리이며, 하나의 노드는 여러 개의 키와 자식 포인터를 저장한다. 이 구조 덕분에 디스크 접근 횟수를 최소화하면서도 정렬된 순서로 데이터를 유지할 수 있다.

B+트리는 B-트리의 변형으로, 모든 실제 데이터(레코드)는 리프 노드에만 저장되고, 내부 노드는 단순히 키 값과 자식 포인터를 가지는 인덱스 역할만 한다. 리프 노드들은 연결 리스트 형태로 서로 연결되어 있어 범위 질의나 순차 접근 시 매우 효율적이다. 이러한 특성 때문에 관계형 데이터베이스의 인덱스 구현에 가장 널리 사용된다.

두 구조의 주요 차이점은 데이터 저장 위치와 리프 노드의 연결성에 있다. 다음 표는 핵심 차이를 보여준다.

B-트리 계열 구조의 공통 장점은 높은 팬아웃으로 인해 트리의 높이가 낮게 유지된다는 점이다. 이는 특히 2차 저장장치처럼 블록 단위로 데이터를 읽고 쓰는 환경에서 검색 및 갱신 연산의 디스크 I/O를 획기적으로 줄여준다.

그래프는 정점과 간선의 집합으로 구성된 추상 자료형이다. 간선이 방향성을 가지는지 여부에 따라 방향 그래프와 무방향 그래프로 구분된다.

방향 그래프는 간선에 방향이 존재하는 그래프이다. 각 간선은 순서가 있는 정점 쌍 (u, v)로 표현되며, u에서 v로 향하는 단방향 연결을 의미한다. 예를 들어, 웹 페이지 간의 하이퍼링크나 소셜 네트워크의 팔로우 관계는 방향 그래프로 모델링할 수 있다. 반면, 무방향 그래프는 간선에 방향이 없는 그래프이다. 간선은 순서가 없는 정점 쌍 {u, v}로 표현되며, u와 v가 서로 연결되어 있음을 의미한다. 도로 네트워크(일방통행 제외)나 프렌드 관계를 가진 소셜 네트워크가 대표적인 예이다.

두 그래프 유형은 표현 방식과 분석 방법에서 차이를 보인다. 무방향 그래프에서 정점의 차수는 해당 정점에 연결된 모든 간선의 수이다. 방향 그래프에서는 정점의 차수가 진입 차수와 진출 차수로 나뉜다. 진입 차수는 해당 정점으로 들어오는 간선의 수, 진출 차수는 해당 정점에서 나가는 간선의 수를 의미한다. 이 차이는 알고리즘 설계에 직접적인 영향을 미친다. 예를 들어, 위상 정렬 알고리즘은 방향 그래프에서만 적용 가능하다.

가중치 그래프는 그래프의 간선에 가중치 또는 비용이 할당된 그래프이다. 이 가중치는 두 정점 사이의 거리, 이동 시간, 비용, 용량, 또는 연결 강도 등을 나타낼 수 있다. 수학적으로는 각 간선 e에 대해 실수 값 w(e)를 가지는 그래프 G=(V, E, w)로 표현된다.

가중치 그래프는 다양한 실세계 문제를 모델링하는 데 널리 사용된다. 예를 들어, 도시를 정점으로 하고 도로를 간선으로 하며, 도로의 길이나 통행 시간을 가중치로 할당하여 최단 경로 문제를 풀 수 있다. 네트워크 라우팅, 물류 최적화, 회로 설계, 작업 스케줄링 등에서 핵심적인 역할을 한다. 가중치 그래프의 주요 알고리즘으로는 다익스트라 알고리즘과 벨만-포드 알고리즘이 있으며, 이들은 모두 단일 출발점 최단 경로를 찾는 알고리즘이다.

가중치 그래프의 종류는 가중치의 특성에 따라 구분된다. 모든 간선의 가중치가 양수인 그래프, 음의 가중치를 허용하는 그래프, 그리고 가중치의 합을 최소화하는 최소 신장 트리를 찾는 문제에 사용되는 그래프 등이 있다. 최소 신장 트리를 찾는 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있다.

그래프의 모든 정점을 체계적으로 방문하기 위한 대표적인 방법으로 깊이 우선 탐색과 너비 우선 탐색이 있다. 이 두 알고리즘은 탐색 순서에 근본적인 차이가 있으며, 그래프의 구조나 해결하려는 문제의 성격에 따라 선택되어 활용된다.

깊이 우선 탐색은 한 정점에서 시작하여 가능한 깊숙이, 즉 더 이상 방문할 새로운 인접 정점이 없을 때까지 탐색을 진행한 후, 백트래킹하여 다른 경로를 탐색하는 방식이다. 주로 스택 자료구조를 명시적으로 사용하거나 재귀 호출을 통해 구현된다. DFS는 경로의 존재성을 확인하거나 사이클을 탐지하는 데 유용하며, 미로 탐색이나 위상 정렬 같은 문제에 자주 적용된다.

반면, 너비 우선 탐색은 시작 정점을 기준으로 가까운 정점들부터 차례대로, 즉 같은 깊이(레벨)에 있는 모든 정점을 방문한 후에 다음 깊이의 정점들을 방문하는 방식이다. 이 알고리즘은 일반적으로 큐 자료구조를 사용하여 구현된다. BFS는 두 정점 사이의 최단 경로(간선의 가중치가 모두 동일할 때)를 찾거나, 소셜 네트워크에서 친구 추천 같은 문제에 적합하다.

두 알고리즘의 시간 복잡도는 인접 리스트로 표현된 그래프의 경우 O(V+E)이며, 인접 행렬로 표현된 경우 O(V²)이다. 여기서 V는 정점의 수, E는 간선의 수를 나타낸다. 공간 복잡도는 최악의 경우 모든 정점을 저장해야 하므로 O(V)이다. 선택은 문제의 요구사항에 따라 달라지는데, 예를 들어 모든 가능한 경로를 탐색해야 한다면 DFS가, 최소 비용이나 최단 거리를 보장된 형태로 찾아야 한다면 BFS가 일반적으로 선호된다.

해시 함수는 임의의 길이를 가진 데이터(키)를 고정된 길이의 값(해시 값 또는 해시 코드)으로 변환하는 함수이다. 이 함수는 해시테이블의 핵심 구성 요소로, 키를 테이블 내 특정 인덱스(버킷의 위치)로 매핑하는 역할을 한다.

이상적인 해시 함수는 결정론적이어야 하며, 즉 같은 입력에 대해 항상 동일한 해시 값을 반환해야 한다. 또한 계산 속도가 빨라야 하고, 해시 테이블의 모든 버킷에 키를 균등하게 분배하여 충돌 가능성을 최소화해야 한다. 일반적인 해시 함수의 동작은 키를 정수로 변환한 후, 테이블 크기로 나눈 나머지(모듈로 연산)를 인덱스로 사용한다.

다양한 해시 함수 기법이 존재하며, 키의 데이터 타입과 특성에 따라 선택된다. 정수 키에 대해서는 나눗셈법이나 곱셈법이 흔히 사용된다. 문자열과 같은 복잡한 키의 경우, 각 문자의 아스키 코드 값을 이용한 다항식 누적 계산 방식(예: 폴딩 함수)을 적용하여 해시 값을 생성한다.

해시 함수의 품질은 충돌 발생 빈도에 직접적인 영향을 미친다. 설계가 나쁜 해시 함수는 많은 키를 특정 버킷에 집중시켜 성능을 급격히 저하시킬 수 있다. 따라서 균일한 분포를 제공하는 함수를 선택하거나, 키의 특정 패턴에 민감하지 않은 암호학적 해시 함수의 원리를 차용하기도 한다.

해시 테이블에서 서로 다른 키가 동일한 해시 함수에 의해 같은 해시 버킷 인덱스로 매핑되는 현상을 해시 충돌이라고 한다. 이는 해시 함수의 출력 공간이 한정되어 있기 때문에 필연적으로 발생하며, 이를 효과적으로 처리하는 방법이 필수적이다. 주요 충돌 해결 방법으로는 체이닝과 개방 주소법이 널리 사용된다.

체이닝 방법은 각 버킷을 하나의 연결 리스트나 다른 형태의 자료구조로 관리한다. 충돌이 발생하면, 해당 버킷의 리스트에 새로운 키-값 쌍을 추가한다. 탐색 시에는 해당 버킷의 리스트를 순차적으로 검색하여 원하는 키를 찾는다. 이 방법의 장점은 구현이 비교적 간단하며, 버킷 개수 이상의 데이터를 저장할 수 있다는 점이다. 단점은 하나의 버킷에 많은 데이터가 모이면 리스트 탐색 시간이 증가하여 성능이 저하될 수 있다.

개방 주소법은 모든 데이터를 테이블 배열 내에 직접 저장하는 방식이다. 충돌이 발생하면, 미리 정해진 규칙에 따라 다른 빈 버킷을 탐색하여 데이터를 저장한다. 대표적인 탐사 방법은 다음과 같다.

개방 주소법의 장점은 포인터를 사용하지 않아 추가 메모리 오버헤드가 적고, 데이터가 연속된 공간에 위치하여 참조 지역성이 좋을 수 있다는 점이다. 단점은 로드 팩터가 일정 수준을 넘으면 탐사 횟수가 급증하며, 데이터 삭제 처리가 복잡할 수 있다는 것이다.

로드 팩터는 해시테이블의 현재 저장된 항목 수와 전체 버킷 수의 비율이다. 이 값은 해시테이블의 성능과 공간 효율성을 나타내는 핵심 지표이다. 일반적으로 로드 팩터가 높을수록, 즉 테이블이 가득 찰수록 해시 충돌이 발생할 확률이 높아져 조회, 삽입, 삭제 연산의 평균 시간 복잡도가 증가한다. 각 충돌 해결 방법마다 이상적인 로드 팩터 임계값이 다르며, 이를 초과하면 성능이 급격히 저하될 수 있다.

재해싱은 로드 팩터가 특정 임계값에 도달했을 때 해시테이블의 크기를 동적으로 조정하는 과정이다. 일반적으로 더 큰 크기의 새로운 버킷 배열을 할당한 후, 기존 테이블의 모든 키-값 쌍을 새로운 해시 함수를 적용하여 새로운 위치에 재배치한다. 이 과정은 O(n)의 시간이 소요되므로 비용이 큰 연산이지만, 성능 저상을 방지하기 위해 필수적이다. 대부분의 구현에서는 로드 팩터 임계값을 0.7에서 0.75 사이로 설정한다.

재해싱 전략은 크게 두 가지로 나뉜다. 하나는 테이블이 일정 비율 이상 차면 크기를 두 배로 늘리는 배수 확장 방식이다. 다른 하나는 소수 크기 테이블을 사용하며, 다음 소수 크기로 확장하는 방식이다. 후자는 해시 함수의 분포를 개선하는 데 도움이 될 수 있다. 재해싱 후 새로운 로드 팩터는 크게 낮아지며, 이로 인해 충돌 확률이 감소하고 성능이 회복된다.

자료구조의 선택은 연산의 시간 복잡도에 큰 영향을 미친다. 주요 연산인 탐색, 삽입, 삭제에 대한 각 자료구조의 평균 및 최악의 경우 시간 복잡도를 비교하면 다음과 같다.

해시테이블은 이상적인 경우(충돌 최소화) 대부분의 연산에서 상수 시간 O(1)의 성능을 보인다. 그러나 최악의 경우(모든 키가 동일한 버킷에 해시될 때) 연산은 O(n)으로 저하된다. 균형 이진 트리는 키의 정렬 상태를 유지하며, 탐색, 삽입, 삭제 모두 로그 시간 O(log n)을 보장한다. 그래프의 연산 복잡도는 표현 방식(인접 리스트 또는 인접 행렬)과 수행하려는 작업에 크게 의존한다. 예를 들어, 정점 간 연결 여부 확인은 인접 행렬에서는 O(1)이지만, 인접 리스트에서는 O(V)가 될 수 있다.

이러한 복잡도 차이는 자료구조의 핵심 특징에서 비롯된다. 해시테이블은 해시 함수를 통한 직접 접근을, 트리는 분할 정복을 통한 계층적 탐색을, 그래프는 정점과 간선의 명시적 관계 표현을 기반으로 한다. 따라서 데이터의 특성(정렬 필요 여부, 키의 분포)과 주로 수행할 연산의 종류(빠른 검색, 범위 질의, 관계 탐색)에 따라 적합한 자료구조를 선택해야 한다.

트리 구조는 계층적 데이터를 표현하는 데 적합하다. 파일 시스템의 디렉토리 구조는 대표적인 예시로, 루트 디렉토리에서 시작해 하위 폴더와 파일로 뻗어나가는 형태를 가진다. 데이터베이스 인덱스 구현에는 B-트리나 B+트리가 널리 사용되며, 이는 디스크 기반 저장 장치에서 효율적인 검색과 범위 질의를 가능하게 한다. 또한, DOM(Document Object Model)은 HTML 또는 XML 문서를 트리 형태로 표현하여 프로그래밍적으로 문서 구조에 접근하고 조작할 수 있게 한다.

그래프는 객체 간의 복잡한 관계와 네트워크를 모델링한다. 소셜 네트워크 서비스에서는 사용자를 정점(Node)으로, 친구 관계를 간선(Edge)으로 표현하여 추천 시스템이나 커뮤니티 탐지에 활용한다. 내비게이션 시스템과 로지스틱스에서는 도로와 교차로를 가중치 그래프로 모델링하고, 다익스트라 알고리즘이나 A* 알고리즘을 적용하여 최단 경로를 계산한다. 의존성 관리 도구(예: Maven, npm)는 패키지 간 의존 관계를 방향 그래프로 관리하여 설치 순서를 결정하고 순환 의존성을 탐지한다.

해시테이블은 빠른 키-값 조회가 핵심인 시스템에서 광범위하게 사용된다. 프로그래밍 언어의 연관 배열(Associative Array)이나 사전(Dictionary) 자료형(예: Python의 dict, Java의 HashMap)의 내부 구현체로 쓰인다. 캐시 시스템(예: Memcached, Redis)은 데이터를 빠르게 제공하기 위해 해시테이블을 기반으로 한다. 또한, 대규모 웹 서비스에서는 요청을 분산 처리하기 위해 로드 밸런서가 일관성 해싱 기법을 사용하여 서버에 작업을 균등하게 배분한다.

이 세 가지 자료구조는 종종 결합되어 사용된다. 예를 들어, 그래프 데이터베이스는 내부적으로 그래프 구조를 저장하고 탐색하기 위해 인덱스로 B-트리를, 속성 조회를 위해 해시테이블을 함께 활용할 수 있다. 시스템의 요구사항(데이터의 관계성, 조회 속도, 갱신 빈도, 메모리/디스크 사용 등)에 따라 적절한 자료구조를 선택하거나 조합하는 것이 성능과 확장성에 결정적 영향을 미친다.