Skiplist
-
-
[ Open Data Structures ] - Skiplists - 2DataStructure 2021. 7. 29. 13:49
SkiplistList 이렇게 되면 Get/Set 함수도 함께 자명해집니다. ? 어렵습니다. Add 함수가 두 개라서 헷갈릴 수 있습니다. 그런데 둘은 Parameter가 다르다는 점을 알아야 합니다. 노드를 받는 Add를 하나씩 분석해보며 이해하도록 합시다. 각 노드의 변의 길이를 결정하는 부분이 조금 헷갈렸으나 천천히 짚어보니 이해가 됐습니다. Node* u = sentinel; 은 기존 Skiplist처럼 좌상단의 노드부터 시작합니다. k는 추가하려는 노드의 높이를 나타냅니다. r = h는 Skiplist의 높이를 취합니다. 첫 번째 While문은 Skiplist의 높이를 조건으로 사용합니다. 두 번째 while 문에서 처음 j가 등장합니다. 기본적으로 j는 수직으로 이동할 때는 값이 변화하지 않습..
-
[ Open Data Structures ] - Skiplists - 1DataStructure 2021. 7. 28. 17:28
Skiplists 이번엔 다양한 활용이 가능한 Skiplist라는 아름다운 자료구조를 공부해보록 합니다. 이 자료구조를 사용하여 우리는 Add, Get, Set, Remove을 O ( log(n) )의 Running time을 갖는 List interface를 구성할 수 있으며 모든 오퍼레이션이 Expected running time이 O ( log(n) )을 취하는 Sorted Set을 구성할 수도 있습니다. Skiplist의 효율성은 랜덤화에서 기인합니다. 새로운 자료가 Skiplist에 추가될 때 Skiplist는 무작위 동전 던지기와 같은 기법으로 새로운 자료의 높이[Height]를 결정하곤 합니다( 곧 이 높이에 관해서 논할 겁니다 ). Skiplist의 성능[Performance]은 Expec..