스킵 리스트: 균형 트리에 대한 확률적 대안

Key Points

• 목표는 데이터 구조 작업에서 건너뛰기 리스트와 균형 트리의 효율성을 평가하는 것이다.
• 건너뛰기 리스트와 균형 트리에서의 삽입 및 삭제 알고리즘을 분석했다.
• 건너뛰기 리스트의 확률적 균형 메커니즘에 대해 논의했다.
• 각 알고리즘의 계산 복잡성을 비교했다.
• 건너뛰기 리스트는 균형 트리보다 삽입 및 삭제 속도가 훨씬 빠르다.
• 건너뛰기 리스트의 알고리즘은 균형 트리의 알고리즘보다 구현이 더 간단하다.

Abstract