ITPE * JackerLab

개요Fibonacci Heap은 그래프 알고리즘에서 중요한 역할을 하는 우선순위 큐 구현 구조로, 특히 Decrease-Key, Merge 연산에서 탁월한 이론적 성능을 보이는 자료구조입니다. 이름은 노드 수가 피보나치 수열을 따르는 구조적 특성에서 유래하며, Dijkstra, Prim 알고리즘의 이론적 시간 복잡도를 낮추는 데 핵심 역할을 합니다.1. 개념 및 정의Fibonacci Heap은 연결 리스트 기반의 느슨한 구조로 구성된 **최소 힙(min heap)**이며, 여러 개의 트리를 루트 리스트로 구성하고 lazy 방식으로 병합 및 삽입을 처리합니다.창시자: Fredman과 Tarjan (1984)특징: 느슨한 균형 유지, 지연된 구조 조정(lazy consolidation)용도: 최단 경로 탐색..

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