반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 7: 스킵 리스트 (Skip List) 스킵 리스트 (Skip List)스킵 리스트는 연결 리스트에 인덱스를 추가하여 검색, 삽입, 삭제 연산의 시간 복잡도를 (O(\log n))으로 개선한 자료구조입니다. 여러 레벨로 구성된 연결 리스트로, 각 레벨마다 원소를 건너뛰어가며 검색할 수 있습니다. 이는 균형 이진 탐색 트리와 유사한 시간 복잡도를 가지면서도 구현이 간단합니다.스킵 리스트의 주요 특징시간 복잡도:평균: (O(\log n))최악의 경우: (O(n))레벨 구조: 여러 레벨의 리스트로 구성되며, 각 레벨은 원소를 건너뛰어가며 검색할 수 있도록 합니다.확률적 균형 유지: 랜덤하게 레벨을 선택하여 원소를 삽입함으로써 확률적으로 균형을 유지합니다.스킵 리스트의 기본 연산삽입 (Insert): 새로운 원소를 삽입하고 레벨을 랜덤하게 결정합니다.. 2024. 8. 1. 이전 1 다음 반응형
