기본 개념다차원 이진 탐색 트리(multidimensional binary search tree), 흔히 k-d 트리라고 불리는 자료구조는 여러 개의 키(multikey)를 가진 레코드를 저장하기 위해 고안된 구조입니다. 통계학과 데이터 분석 분야에서 다양한 기하학적 문제를 해결하기 위해 널리 활용되어 왔습니다.k-d 트리(k-dimensional tree)는 k차원 공간에 존재하는 점들을 체계적으로 조직화하기 위한 공간 분할(space-partitioning) 자료구조로 정의됩니다. 다차원 검색 키를 사용하는 연산, 예를 들어 범

다방향 트리란?다방향 트리(Multiway Tree)는 하나의 노드가 두 개 이상의 자식 노드를 가질 수 있는 트리 구조를 의미합니다. 앞서 살펴본 이진 트리(Binary Tree)가 각 노드당 최대 2개의 자식만 가질 수 있는 것과 달리, 다방향 트리는 자식 노드의 개수에 제한이 없습니다.만약 다방향 트리의 각 노드가 가질 수 있는 자식의 최대 개수가 m개라면, 이 트리를 차수(order)가 m인 다방향 트리, 즉 m-원 트리(m-way tree)라고 부릅니다.m-원 트리의 노드 구조기존에 학습한 다른 트리들과 마찬가지로, m-원

데이터 구조에서 핑거 탐색(finger search)은 해당 구조가 지원하는 일반적인 탐색 연산을 확장한 개념입니다. 쿼리와 함께 데이터 구조 내 특정 요소를 가리키는 참조(핑거, finger)가 추가로 주어진다는 점이 특징입니다. 일반적인 요소 탐색 시간은 데이터 구조에 포함된 요소의 개수에 대한 함수로 표현되지만, 핑거 탐색의 시간은 목표 요소와 핑거 사이의 거리에 대한 함수로 다룹니다.거리의 정의와 시간 복잡도m개의 요소로 이루어진 집합에서 두 요소 a와 b 사이의 거리 d(a, b)는 두 요소의 순위(rank) 차이로 정의됩

핑거 검색 트리(finger search tree)는 특정 위치(핑거)에서 시작해 인접한 요소를 빠르게 찾는 데 최적화된 고급 데이터 구조입니다. 이 글에서는 동적 핑거 검색 데이터 구조의 정의, 시간 복잡도, 다양한 구현 방식, 그리고 계산 모델별 적용 사례까지 체계적으로 살펴봅니다.동적 핑거 검색 데이터 구조란?동적 핑거 검색(dynamic finger search) 데이터 구조는 단순히 핑거(finger)를 이용한 검색만 지원해서는 충분하지 않습니다. 핑거가 가리키는 위치에서 요소를 삽입하고 삭제하는 연산까지 함께 수행할 수

레벨 링크를 활용한 (2,4)-트리의 핑거 탐색이 절에서는 레벨 링크(level link)를 도입하여 (2,4)-트리가 어떻게 효율적인 핑거 탐색(finger search)을 지원할 수 있는지 설명합니다. 여기서 소개하는 아이디어는 b ≥ 2a를 만족하는 보다 일반적인 높이 균형 트리(height-balanced tree), 즉 (a,b)-트리 클래스에도 그대로 적용됩니다.(2,4)-트리는 모든 리프 노드가 동일한 깊이를 가지며, 모든 내부 노드의 차수(degree)가 2, 3 또는 4인 높이 균형 탐색 트리입니다. 실제 원소들은

결정론적 탐색 트리(deterministic search tree)에 대한 무작위화(randomized) 기반 대안으로는 무작위 이진 탐색 트리인 트립(treap)과 스킵 리스트(skip list)가 대표적입니다. 두 자료 구조 모두 우아한 설계로 평가받으며, 무작위성을 활용해 단순하면서도 효율적인 갱신 연산을 가능하게 합니다.이 글에서는 자료 구조 자체를 변경하지 않고도 트립과 스킵 리스트를 효율적인 손가락 검색 트리(finger search tree)로 구현할 수 있는 방법을 살펴봅니다. 두 자료 구조 모두 기대 시간(expec

스킵 리스트의 핑거 탐색이란?스킵 리스트(Skip List)에서는 이미 요소 b를 담고 있는 노드를 알고 있다면, 그 지점에서 탐색을 이어가 다른 요소 a를 찾는 핑거 탐색(finger search)을 수행할 수 있습니다. 처음부터 전체 리스트를 훑는 대신, 이미 파악한 위치를 출발점으로 삼는 효율적인 탐색 방식입니다.탐색 방향은 어떻게 결정될까?찾으려는 값 a와 현재 노드의 값 b를 비교하면 탐색 방향이 정해집니다. a < b이면 탐색은 뒤쪽(역방향)으로 진행되고, a > b이면 앞쪽(정방향)으로 진행됩니다.역방향 탐색

적응형 병합 정렬(Adaptive Merge Sort)이란?적응형 병합 정렬은 일반 병합 정렬(Merge Sort)과 마찬가지로 정렬된 부분 리스트를 병합하는 방식으로 동작합니다. 하지만 결정적인 차이점은, 초기 부분 리스트의 크기를 항상 1로 시작하는 것이 아니라 입력 리스트에 이미 존재하는 정렬 상태(순서)를 활용하여 부분 리스트의 크기를 결정한다는 점입니다. 예를 들어 다음 그림과 같은 리스트를 살펴보겠습니다.이 리스트는 두 개의 정렬된 부분 리스트로 구성되어 있습니다.부분 리스트 1: 16, 15, 14, 13부분 리스트 2

스플레이 트리란 무엇인가?스플레이 트리(splay tree)는 최근에 접근한 요소를 다시 빠르게 찾을 수 있다는 독특한 속성을 가진 자가 균형(self-balancing) 이진 탐색 트리입니다. 이 자료구조는 1985년 다니엘 슬레이터(Daniel Sleator)와 로버트 타잔(Robert Tarjan)이 제안했으며, 삽입·조회·삭제와 같은 기본 연산을 분할 상환(amortized) 시간 O(log n) 안에 처리할 수 있습니다.흥미로운 점은, 연산 시퀀스의 특정 패턴을 미리 알지 못하더라도 비무작위(non-random) 연산이 반

동적 최적성 추측(Dynamic Optimality Conjecture)스플레이 트리(splay tree)는 스스로 구조를 조정하는(self-adjusting) 이진 탐색 트리로, 자주 접근되는 원소일수록 트리의 상단으로 이동시켜 이후 접근 속도를 높이도록 설계된 자료구조입니다. 이러한 스플레이 트리에는 이미 증명된 성능 보장 외에도, 아직 증명되지 않아 많은 관심을 받고 있는 추측이 하나 있습니다. 바로 동적 최적성 추측입니다.임의의 이진 탐색 트리 알고리즘 B가 원소 y에 접근할 때, 루트에서 y까지의 경로를 따라 이동하며 d(

정적 손가락 정리(Static Finger Theorem)란?정적 손가락 정리는 스플레이 트리(Splay Tree)의 성능을 분석하는 대표적인 이론 중 하나입니다. 스플레이 트리는 자기 조절(self-adjusting) 이진 탐색 트리로, 자주 접근되는 항목일수록 트리의 루트에 가깝게 배치되어 빠른 접근이 가능합니다. 정적 손가락 정리는 이러한 스플레이 트리가 특정 고정된 위치(손가락) 근처의 항목들에 반복적으로 접근할 때 얼마나 효율적인지를 수학적으로 보여줍니다.정리의 정의STATIC FINGER THEOREM — 트리 내의 특정

솔리드 트리(Solid Tree)의 기본 개념 주어진 숲(forest)에서 일부 간선은 점선(dashed)으로 표시하고, 나머지 간선은 실선(solid)으로 유지합니다. 각 리프가 아닌 노드는 자식 중 단 하나만 실선 간선으로 연결하며, 나머지 모든 자식은 점선 간선을 통해 연결됩니다. 보다 구체적으로 설명하면, 임의의 트리에서 가장 오른쪽에 있는 링크(자식을 향한 링크)는 실선으로 유지하고, 다른 자식들을 향한 모든 링크는 점선으로 만듭니다. 실선 경로와 가상 트리(Virtual Tree) 그 결과 트리는 여러 개의 실선 경로

가상 트리(virtual tree)에서는 일부 간선을 실선(solid)으로, 나머지 간선을 점선(dashed)으로 취급합니다. 일반적인 스플레이 연산은 실선으로만 연결된 트리(solid tree) 내부에서 수행되며, 가상 트리 전체를 한꺼번에 회전시키지 않습니다.가상 트리의 특정 노드 y에서 스플레이를 수행하려면 다음 절차를 따릅니다. 이 알고리즘은 트리를 총 세 번 순회하면서(각 패스마다 한 번씩) 구조를 점진적으로 변경합니다.Splay(y) 알고리즘패스 1: 가상 트리를 루트 방향으로 거슬러 올라가되, 스플레이는 실선 서브트리

허프만 코드(Huffman Code)허프만 코드는 무손실 데이터 압축에 널리 사용되는 최적 접두어 코드(optimal prefix code)의 한 종류로 정의됩니다.이러한 코드를 찾거나 구현하는 과정은 허프만 코딩(Huffman coding)이라는 알고리즘을 통해 이루어집니다. 이 알고리즘은 MIT에서 박사(Sc.D.) 과정에 있던 데이비드 A. 허프만(David A. Huffman)이 개발했으며, 1952년 발표한 논문 「A Method for the Construction of Minimum-Redundancy Codes(최소

허프만 알고리즘의 기본 절차허프만(Huffman) 알고리즘은 가중치(문자의 빈도)를 기반으로 최적의 코드 트리를 만들어내는 대표적인 알고리즘입니다. 그 동작 과정은 다음과 같이 단순하게 정리할 수 있습니다.n개의 초기 허프만 트리를 준비합니다. 각 트리는 하나의 리프(leaf) 노드로만 구성되며, 이 n개의 트리를 가중치(빈도)를 기준으로 정렬된 우선순위 큐(priority queue)에 넣어 관리합니다.우선순위 큐에서 가장 작은 가중치를 가진 두 개의 트리를 꺼냅니다(삭제합니다). 이 두 트리를 결합해 새로운 트리를 만드는데, 새

높이 제한 허프만 트리란?아래 그림은 높이 또는 깊이가 제한된(depth-limited) 허프만 트리의 구조를 보여줍니다.트리 깊이 제한은 사소해 보이지만, 실제 환경에서 허프만 코딩을 구현하는 대부분의 시스템이 반드시 해결해야 하는 중요한 문제입니다.허프만 트리 생성에는 깊이 제한이 없다표준 허프만 트리 생성 알고리즘 자체는 트리의 높이나 깊이를 제한하지 않습니다. 오히려 깊이를 임의로 제한하면 트리가 더 이상 최적(optimal) 상태를 유지할 수 없게 됩니다.다만 허프만 트리의 최대 깊이는 피보나치 수열(Fibonacci se

비용이 다른 문자에 대한 최적 접두어 코드 문제란?문자별 비용(cost)이 서로 다른 경우의 최적 접두어 자유 코드(prefix-free code)를 찾는 문제는, 인코딩 알파벳이 길이(비용)가 각각 α와 β인 두 종류의 문자(α ≤ β)로 구성된 조건에서 최소 비용의 접두어 자유 코드를 계산하는 것이다. 본 글에서는 이 문제를 이진 트리(binary tree)로 한정하여 살펴본다.편향 트리(Lopsided Tree)와 허프만 트리의 차이이러한 코드는 편향 트리(lopsided tree)

버킷팅(Bucketing)이란 무엇인가?버킷팅은 해시 테이블(hash table)을 단일 1차원 배열이 아닌 2차원 배열 형태로 구성하는 기법입니다. 이때 배열의 각 항목(entry)은 M개의 데이터를 담을 수 있을 만큼 충분히 크게 설계됩니다. 여기서 M은 전체 데이터의 양이 아니라, 하나의 버킷에 저장할 수 있는 최대 항목 수를 나타내는 상수입니다.버킷팅의 주요 문제점공간 낭비: 각 버킷이 고정된 크기(M개의 슬롯)를 가지므로, 실제로 사용되지 않는 빈 공간이 많아져 메모리가 비효율적으로 소모됩니다.오버플로우 처리: 한 버킷에

사각형 데이터란 무엇인가?다변량 단면 데이터(multivariate cross-sectional data, 즉 시계열이나 반복 측정 데이터가 아닌 형태)는 일반적으로 사각형 데이터(rectangular data)로 표현됩니다. 이 구조에서는 각 열(column)이 하나의 변수(특징, feature)를 나타내고, 각 행(row)은 하나의 사례(case) 또는 레코드(record)에 해당합니다.그렇다면 이러한 사각형 데이터를 컴퓨터 내부에서 어떻게 저장하고 처리할 수 있을까요? 크게 세 가지 접근 방식이 존재하며, 각 방식은 고유한 장

평면 직선 그래프(PSLG)란 무엇인가? 계산 기하학(computational geometry)에서 평면 직선 그래프(Planar Straight-Line Graph, PSLG)는 평면 그래프를 평면 위에 배치(매립)하면서 모든 변(edge)이 직선 선분으로 표현되도록 만든 그래프를 의미합니다. 문헌에 따라서는 직선 평면 그래프 또는 평면 직선 그래프라는 용어로도 불립니다. 파리의 정리(Fárys theorem, 1948)에 따르면, 모든 평면 그래프는 이러한 형태의 매립을 가질 수 있습니다. 즉, 어떤 평면 그래프든 변들이 서로