ITPE * JackerLab

개요Link-Cut Tree는 동적으로 연결되거나 분리되는 트리 구조에서 효율적으로 경로 질의 및 갱신 연산을 수행할 수 있도록 설계된 고급 트리 기반 자료구조입니다. Sleator와 Tarjan에 의해 1983년 제안된 이 자료구조는 splay tree를 기반으로 하며, 각 노드의 서브트리나 루트까지의 경로에 대해 로그 시간 내 연산을 지원합니다. Union-Find, Euler Tour Tree보다 더 복잡한 트리 동작이 필요한 알고리즘에 적합합니다.1. 개념 및 정의 항목 설명 정의Link-Cut Tree는 포레스트(트리들의 집합) 구조에 대해 노드 간 연결(Link), 분리(Cut), 경로 질의(Query), 경로 갱신(Update)을 동적으로 처리하는 트리 자료구조입니다.목적트리 구조가 변동하..

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