세그먼트 트리란 무엇인가?이번 글에서는 데이터 구조 중 하나인 세그먼트 트리(Segment Tree)에 대해 알아보겠습니다. 세그먼트 트리의 개념을 본격적으로 살펴보기 전에, 먼저 다음과 같은 문제 상황을 가정해 보겠습니다.크기가 n인 배열 arr[0, …, n-1]이 주어졌을 때, 우리는 아래 두 가지 연산을 수행해야 합니다.인덱스 l부터 r까지 구간의 원소 합을 구합니다. (단, 0 ≤ l ≤ r ≤ n-1)배열의 특정 위치 i의 값을 새로운 값 x로 변경합니다. 즉, arr[i] = x를 수행하며, i는 0부터 n-1 사이의

K-ary 트리란 무엇인가?이번 섹션에서는 데이터 구조 중 하나인 K-ary 트리(K진 트리)에 대해 알아보겠습니다. K-ary 트리는 루트(rooted) 트리의 한 종류로, 각 노드가 최대 k개까지의 자식 노드를 가질 수 있는 트리를 의미합니다.여기서 k 값에 따라 트리의 형태가 결정됩니다. 만약 k가 2라면, 이를 흔히 알고 있는 이진 트리(binary tree)라고 부릅니다. 즉, 이진 트리나 삼진 트리(ternary tree) 같은 것들은 모두 특수한 형태의 K-ary 트리인 셈입니다. 따라서 K-ary 트리는 다양한 트리

비순환 유향 그래프(DAG)란 무엇인가?이번 글에서는 데이터 구조에서 중요한 개념인 비순환 유향 그래프(Acyclic Digraph)에 대해 알아보겠습니다. 비순환 유향 그래프는 이름 그대로 방향성 순환(directed cycle)을 하나도 포함하지 않는 유향 그래프를 의미합니다.쉽게 말해, 그래프의 어떤 간선을 따라 이동하더라도 다시 시작점으로 되돌아오는 경로가 존재하지 않는 그래프입니다. 이러한 그래프는 영어로 Directed Acyclic Graph라고 하며, 줄여서 DAG라고 부릅니다.DAG의 핵심 성질모든 유한한(finit

높이 균형 좌향 트리(Height Balanced Leftist Tree)란?이번 글에서는 높이 균형 좌향 트리(HBLT, Height Balanced Leftist Tree)가 무엇인지 자세히 살펴보겠습니다. HBLT를 이해하려면 먼저 확장 이진 트리(Extended Binary Tree)라는 개념부터 알아야 합니다.확장 이진 트리와 외부 노드이진 트리에서 비어 있는 모든 서브트리 자리를 외부 노드(External Node)라 불리는 특수한 노드로 대체한다고 가정해 봅시다. 그리고 외부 노드를 제외한 나머지 모든 노드를 내부 노드

맥스 HBLT 삽입이란?맥스 HBLT(Max Height-Biased Leftist Tree)에 새로운 요소를 삽입하는 작업은 맥스 멜드(Max Meld) 연산을 활용하여 수행할 수 있습니다. 멜드 연산은 서로 다른 두 개의 맥스 HBLT를 하나의 맥스 HBLT로 병합하는 데 사용되는 핵심 연산입니다.삽입 과정예를 들어, 값 x를 맥스 HBLT인 H에 삽입한다고 가정해 보겠습니다. 이때의 절차는 다음과 같습니다.삽입할 값 x만으로 구성된 작은 HBLT(단일 노드 트리)를 생성합니다.이 작은 HBLT를 기존 트리 H와 멜드(Meld)

Max HBLT에서의 최댓값 삭제 원리Max HBLT(Height-Biased Leftist Tree, 높이 편향 좌편향 트리)에서는 트리 전체에서 가장 큰 값인 최댓값(max element)이 항상 루트(root)에 위치합니다. 이러한 구조적 특성 덕분에 최댓값을 삭제하는 작업은 매우 효율적으로 처리할 수 있습니다.삭제 과정최댓값을 삭제한다는 것은 곧 루트 노드를 제거하는 것을 의미합니다. 루트가 삭제되면 기존의 하나였던 트리가 왼쪽 서브트리와 오른쪽 서브트리라는 두 개의 독립적인 Max HBLT로 분리됩니다.이때 분리된 두 개의

병합(meld) 전략은 재귀 호출을 활용하면 손쉽게 구현할 수 있습니다. 병합하고자 하는 두 개의 HBLT(Height-Biased Leftist Tree, 높이 편향 좌편향 트리)를 A와 B라고 가정해 봅시다. 만약 둘 중 하나가 비어 있다면, 나머지 하나를 그대로 최종 결과로 삼으면 됩니다. 두 HBLT 모두 비어 있지 않다면, 먼저 두 루트에 있는 원소를 비교해야 합니다. 이때 더 큰 원소를 가진 루트가 병합된 HBLT의 루트가 됩니다.A의 루트가 더 크다고 가정해 보겠습니다. A의 왼쪽 서브트리를 L이라 하고, A의 오른쪽

배열 표현 방식의 공간 낭비 문제배열(Array)은 크기가 고정된 자료구조이기 때문에, 저장할 데이터의 양이 시간에 따라 계속 변하는 경우에는 공간을 매우 비효율적으로 사용하게 됩니다. 데이터를 저장하기 위해 미리 넉넉한 크기의 배열을 할당해 두어야 하며, 이 과정에서 실제로 필요한 용량보다 더 많은 메모리가 낭비될 수 있습니다.배열 두 배 확장 기법의 한계배열이 가득 찼을 때 크기를 늘리는 대표적인 방법은 배열 두 배 확장(Array Doubling) 기법입니다. 예를 들어 현재 배열의 크기가 8192이고 이 배열이 꽉 차 있다면

Max HBLT에서 임의 노드 삭제란?Max HBLT(Max Height-Biased Leftist Tree) 또는 Min HBLT에서 임의의 노드를 삭제하는 것은 우선순위 큐(Priority Queue)나 HBLT의 표준 연산은 아닙니다. 하지만 특정 상황에서는 루트가 아닌 임의의 노드 K를 트리에서 제거해야 할 필요가 생길 수 있습니다. 이 경우 다음과 같은 규칙에 따라 삭제 작업을 수행해야 합니다.임의 노드 삭제 절차서브트리 분리 및 병합(Meld): 노드 K를 루트로 하는 서브트리를 전체 트리에서 분리한 뒤, 그 자리를 노드

가중치 편향 좌파 트리(Weight Biased Leftist Tree, WBLT)는 좌파 트리(Leftist Tree)의 또 다른 변형입니다. 일반적인 좌파 트리가 루트에서 외부 노드(external node)까지의 최단 경로 길이를 기준으로 삼는 것과 달리, WBLT는 서브트리에 포함된 노드의 개수를 기준으로 사용한다는 점이 특징입니다.노드 가중치 w(x)의 정의WBLT에서는 노드 x의 가중치(weight) w(x)를 다음과 같이 정의합니다.w(x): 노드 x를 루트로 하는 서브트리에 포함된 내부 노드(internal node)

이번 글에서는 최대 WBLT(Max Weight-Biased Leftist Tree)에서 사용되는 다양한 연산들을 자세히 살펴보겠습니다.HBLT와 WBLT의 관계HBLT(Height-Biased Leftist Tree, 높이 편향 좌측 트리)에는 삽입(insert), 삭제(delete), 초기화(initialization)와 같은 여러 연산이 존재합니다. 흥미로운 점은 이러한 연산들이 WBLT(Weight-Biased Leftist Tree, 가중 편향 좌측 트리)에서도 거의 동일한 방식으로 적용된다는 것입니다.단일 패스(Singl

로빈후드 해싱(Robin Hood Hashing) 개요로빈후드 해싱(Robin Hood Hashing)은 개방 주소법(Open Addressing)에 속하는 해싱 기법 중 하나입니다. 이름에서 알 수 있듯이 부자에게서 빼앗아 가난한 자에게 주는 로빈후드의 정신처럼, 기존 방식보다 더 공정한 충돌 해결(fair collision resolution) 전략을 사용하여 요소 탐색 시간의 편차를 줄이고 균형을 맞추려고 시도합니다.삽입 과정의 동작 원리로빈후드 해싱의 핵심 아이디어는 삽입 과정에서 확인할 수 있습니다. 요소 x를 위치 xi에

사전(Dictionary) 자료구조와 이진 트리추상 자료형(Abstract Data Type)인 사전(Dictionary)을 구현할 때, 각 노드는 값(value)과 연결됩니다. 사전은 본질적으로 키(key)들의 집합이며, 이 키들은 반드시 전체 순서(total ordering)를 따르는 원소여야 합니다. 각 키에는 추가적인 정보가 함께 저장될 수 있지만, 이는 개념적 이해에는 큰 영향을 주지 않습니다.이진 탐색 트리의 불변식(Invariant)사전을 트리 구조로 구현하면, 각 노드는 고유한 키를 가집니다. 트리 내 임의의 노드 u

병합(Merge) 알고리즘이란?병합(Merge) 알고리즘은 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 합치는 알고리즘입니다. 이 알고리즘은 다양한 상황에서 활용되며, 특히 병합 정렬(Merge Sort)을 수행할 때 정렬된 작은 리스트들을 점점 더 큰 리스트로 합치는 핵심 과정에 사용됩니다.동작 원리병합 알고리즘의 접근 방식은 매우 단순합니다. 두 개의 리스트와 각 리스트를 가리키는 두 개의 포인터(pointer)를 준비합니다. 첫 번째 포인터는 첫 번째 리스트의 요소를, 두 번째 포인터는 두 번째 리스트의 요소를 가리킵니다.

이번 글에서는 데이터 구조 중 하나인 B-트리(B-Tree)에 대해 자세히 알아보겠습니다. B-트리는 특수한 형태의 m-way 탐색 트리(m-way search tree)로, 주로 디스크 접근(disk access)에 최적화되어 있어 데이터베이스와 파일 시스템에서 널리 활용됩니다.B-트리란 무엇인가?B-트리는 차수(order)가 m인 경우, 한 노드가 최대 m-1개의 키(key)와 m개의 자식 노드를 가질 수 있습니다. 하나의 노드에 많은 수의 요소를 저장할 수 있기 때문에 트리 전체의 높이가 상대적으로 낮아지며, 이것이 B-트리의

이번 글에서는 R-트리(R-Tree)라는 자료구조를 살펴봅니다. R-트리는 공간(spatial) 데이터 인덱스를 효율적으로 저장하기 위해 설계된 트리 구조로, 공간 질의(spatial query)와 대용량 공간 데이터 저장에 매우 유용하게 활용됩니다.R-트리의 주요 활용 분야R-트리는 실제 다양한 산업 현장에서 사용되고 있으며, 대표적인 적용 사례는 다음과 같습니다.다차원 정보(multidimensional information)의 인덱싱게임 데이터 처리 및 관리지리적 좌표(geospatial coordinates) 저장가상 지도(

이번 장에서는 레드-블랙 트리(Red-Black Tree)가 무엇인지 자세히 알아보겠습니다. 레드-블랙 트리는 스스로 균형을 유지하는 자가 균형 이진 탐색 트리(Self-balancing Binary Search Tree)의 일종으로, 모든 노드가 반드시 지켜야 할 몇 가지 조건을 가지고 있습니다.레드-블랙 트리의 기본 규칙모든 노드는 색상을 가지며, 그 색은 빨강(Red) 또는 검정(Black) 중 하나입니다.트리의 루트(root) 노드는 항상 검정이어야 합니다.인접한 두 개의 빨강 노드는 존재할 수 없습니다. 즉, 빨강 노드의

산술 표현식을 작성하는 방식을 표기법(notation)이라고 부릅니다. 하나의 산술 표현식은 식의 본질이나 계산 결과를 전혀 바꾸지 않으면서도 서로 다른 세 가지 방식으로 표현할 수 있습니다. 이 세 가지 표기법은 다음과 같습니다.중위 표기법(Infix)전위 표기법(Prefix)후위 표기법(Postfix)중위 표기법은 우리가 일상적으로 수학식을 작성할 때 사용하는 표준적인 방식입니다. 반면 전위 표기법과 후위 표기법은 컴퓨터가 식을 처리하기에 훨씬 유리한 형태로, 괄호 없이도 연산 순서를 명확하게 나타낼 수 있다는 큰 장점이 있습니

이 글에서는 데이터 구조의 중요한 개념인 토너먼트 트리(Tournament Tree)와 그 두 가지 변형인 승자 트리(Winner Tree), 패자 트리(Loser Tree)에 대해 자세히 알아봅니다.토너먼트 트리는 n개의 외부 노드(단말 노드)와 n−1개의 내부 노드를 가진 완전 이진 트리(complete binary tree)입니다. 외부 노드는 경기에 참가하는 선수(키 값)를 나타내고, 내부 노드는 두 선수 간의 경기에서 승리한 사람을 나타냅니다. 이러한 구조적 특성 때문에 토너먼트 트리는 선택 트리(Selection Tree

이번 글에서는 데이터 구조에서 중요한 개념인 비루트 이진 트리(Unrooted Binary Tree)에 대해 자세히 알아보겠습니다.비루트 이진 트리의 정의비루트 이진 트리는 사이클(cycle)이 없는 연결된 무방향 그래프(connected undirected graph)입니다. 일반적인 루트 트리와 달리 특정한 루트(root) 노드가 지정되어 있지 않다는 점이 가장 큰 특징입니다.잎 노드(Leaf)와 내부 노드(Internal Node)트리를 구성하는 정점(vertex)은 이웃(neighbor)의 수에 따라 두 가지로 분류됩니다.잎