건너뛰기 목록에서는 이 지점 a에서 검색을 계속하기만 하면 요소 b를 포함하는 노드에서 요소를 손가락으로 검색할 수 있습니다.
a
백워드 케이스는 스킵 리스트에서 일반 검색과 대칭이지만, 포워드 케이스는 실제로 더 복잡합니다.
일반적으로 스킵 리스트에서의 검색은 리스트의 시작에 있는 센티넬이 가장 높은 노드로 간주되기 때문에 빠를 것으로 예상됩니다.
그러나 우리의 손가락은 높이가 1인 노드와 연관될 수 있습니다. 이 때문에 검색을 시도하는 동안 거의 오르지 않을 수 있습니다. 평소에는 절대 일어나지 않는 일입니다.
건너뛰기 목록의 가장 중요한 속성은 예상 선형 공간이 필요하고 예상 O(log n) 수준을 포함하고 예상 O(log n) 시간에 검색을 지원하며 예상 O(1)의 주어진 위치에서 삽입 및 삭제를 지원한다는 것입니다. ) 시간.
건너뛰기 목록이 예상 O(log d) 시간에 손가락 검색을 지원하는 방법에 대한 의사 코드를 포함하여 건너뛰기 목록의 다양한 속성과 확장에 대해 자세히 설명했습니다. 역방향 핑거 검색을 용이하게 하기 위해 노드 V에 대한 핑거는 각 레벨 i에 대해 레벨 i 포인터가 가리키는 V의 왼쪽에 있는 노드에 대한 포인터를 저장하는 예상 O(log n) 공간 핑거 데이터 구조로 저장됩니다. V 또는 V의 오른쪽에 있는 노드. 손가락을 움직이면 해당 포인터 목록이 업데이트되어야 합니다.
역방향 손가락 검색은 먼저 검색 키 y의 왼쪽에 있는 손가락 데이터 구조의 가장 낮은 노드를 식별하여 수행되며, 여기서 손가락 데이터 구조의 노드는 레벨이 증가하는 순서로 고려됩니다.
그 후 검색은 표준 건너뛰기 목록 검색과 유사한 식별된 노드에서 아래쪽으로 진행됩니다.