ITPE * JackerLab

개요KD-Tree(K-Dimensional Tree)는 다차원(K차원) 데이터에서 효율적인 검색을 가능하게 하는 공간 분할 기반의 이진 탐색 트리입니다. 특히 2D/3D 공간 탐색, 최근접 이웃 검색(Nearest Neighbor Search), 범위 질의(Range Query) 등에 최적화되어 있어 컴퓨터 그래픽스, 머신러닝, 로보틱스 등에서 널리 활용됩니다.1. 개념 및 정의KD-Tree는 K차원 데이터를 표현하기 위한 **이진 분할 트리(Binary Space Partitioning Tree)**입니다. 각 노드는 하나의 축을 기준으로 데이터를 이진 분할하며, 축은 트리의 깊이에 따라 반복적으로 선택됩니다.차원 기반 트리: 트리 깊이 d에서 분할 축은 d mod k로 결정구성 원리: 중간값 기준으로..

개요Splay Tree는 자주 접근하는 노드를 루트로 끌어올려 접근 성능을 최적화하는 자가 조정형(Self-adjusting) 이진 탐색 트리입니다. 특별한 균형 기준 없이, 최근 접근 노드를 우선시하며 트리 구조를 동적으로 재조정하는 방식으로, 캐시 성능을 높이고 평균 연산 시간을 줄이는 데 효과적입니다.1. 개념 및 정의Splay Tree는 1985년 Sleator와 Tarjan에 의해 제안된 트리 자료구조로, 검색·삽입·삭제 연산 시 해당 노드를 루트로 끌어올리는(Splay) 과정을 통해 접근 성능을 개선합니다.목적: 자주 접근되는 노드를 빠르게 찾기 위한 트리 구조 최적화특징: 별도의 균형 조건 없이도 amortized O(log n) 성능 보장구조: 이진 탐색 트리의 변형 형태2. 연산 구조Sp..

개요Treap은 Tree와 Heap을 조합한 이름으로, 이진 탐색 트리(Binary Search Tree, BST)와 힙(Heap) 구조의 특성을 동시에 만족하는 확률적 자료구조입니다. 키에 대해 이진 탐색 트리 성질을, 우선순위에 대해 힙 성질을 유지함으로써 삽입, 삭제, 탐색 모두 평균적으로 O(log n) 시간 복잡도를 제공하며, 균형 잡힌 트리 구조를 확률적으로 유지할 수 있습니다.1. 개념 및 정의 항목 내용 정의각 노드가 키(Key)와 우선순위(Priority)를 가지며, 키는 BST, 우선순위는 힙 성질을 만족하는 이진 트리목적자가 균형(self-balancing) 유지로 빠른 탐색, 삽입, 삭제 지원필요성명시적 리밸런싱 없이 트리 높이 최적화를 달성하여 성능 향상Treap은 간단한 구조와..