대학교에서 자료구조 수업 수강중인 21학번 2학년 군복학생+코로나학번+I 97%+경기도-서울 통학+아싸+찐따 컴붕이임....물어볼 사람도 없고 내가 이해 못한 부분을 설명해주는 글이 영어로도 존재하지 않아서 여기에라도 물어봄.....

스킵리스트가 뭐하는 앤진 다 이해했다고 할 수 있음


n개의 원소를 갖는 Linked List에 대해/각 원소마다

동전 던져서 앞면:head/뒷면:tail이 나온다고 할 때, 각 원소는 tail이 나올 때 까지의 횟수만큼의 높이로 윗리스트에 타워를 쌓는 구조잖

나는 탐색 부분에서 이해가 안되는 부분이 있는데-나는 역과정으로 이해해보려 함.


어떤 n개의 원소를 갖는 skip list가 가장 밑의 level 0부터 level h 까지 있다고 생각하면, 가장 밑 리스트의 어떤 원소에서 시작한다고 해보고, 원래 탐색의 시작은 -inf이니, 역과정의 탐색의 끝은 -inf가 될 것이고..


어떤 최하위 레벨의 원소가 상위 리스트에도 있을 확률, 즉 upstep을 가질 확률은 1/2이고, 아닐 확률도 1/2이며, 아니라면 왼쪽으로 이동하는 연산, 즉 leftstep을 가질 확률도 1/2일 것임.


그렇다면 이 원소가 위쪽으로 올라가기 위해, '임의의 한 레벨에서 "동전을 던지는 횟수"는 두 번이 될 것이다' 라는 것은 '평균 두 번 중에 한 번은 upstep을 갖게 되기 때문이다' 라는 것 까지는 이해했음.


여기서 왜 leftstep(즉 원래 방향이라면 scan-forward step)이 한 레벨에 한 번 꼴이 아니라 두 번 꼴로 발생하는 지를 모르겠음. 어떤 칸에서 upstep을 하게된 직후, 그 칸에 대해서 코인을 던져 upstep을 진행하거나 leftstep을 진행하고, leftstep을 진행했다면 다시 한 칸 옮긴 칸에 대해서 upstep을 진행하거나 leftstep을 진행할텐데, 이렇게 되면 leftstep은 평균 1회 발생하는 것이 아님? 내가 이해한 걸 그림으로 보여드림


이거 웰케 작아


여기서 오른쪽 아래에서 시작한다고 가정해보겠음. 오른쪽 아래에서 동전을 던져서 u로 갈지 l로 갈지 결정하는거잖음?
기댓값에 따라 평균 두 번째에 위로 올라가게 될 것임.
다음 층으로 올라왔음. 현재 위치는 두 번째 층의 가장 오른쪽
여기서 동전을 던짐. 위로 올라가냐, 왼쪽으로 갈거냐.
역시 기댓값으로 따지면, 두 번째에 위로 올라가게 될 것임.
내가 말하고 싶은건, 두 번째에 위로 올라가게 되면 왼쪽으로 가는 연산은 한 레벨에 한 번 발생하는거 아님?

왜 두 번 발생하는게 맞는 거임?