소오설 소오설

* hash 함수는 다음에 배워 구현합니다. 이 챕터로써는 해시 함수를 포함한 코드를 실행시킬 수 없습니다. (Random numbers plucked from the atmosphere (irishtimes.com)) -> Atmospheric noise Add Operation Hash table은 List를 요소로 갖는 배열 t로 구현을 합니다. 격납되어 있는 모든 요소의 수를 n으로 추적합니다. Remove Operation Multiplicative Hashing * C/C++기준입니다. 다른 프로그래밍 언어에서는 Undefined Behaviour일 수 있습니다. 또한, 여기서 등장하는 HashCode(x)와 Hash(x)상당히 혼란스럽습니다. Hash(x)는 x에게 부여된 어떤 수를 갖고 배..

SkiplistList 이렇게 되면 Get/Set 함수도 함께 자명해집니다. ? 어렵습니다. Add 함수가 두 개라서 헷갈릴 수 있습니다. 그런데 둘은 Parameter가 다르다는 점을 알아야 합니다. 노드를 받는 Add를 하나씩 분석해보며 이해하도록 합시다. 각 노드의 변의 길이를 결정하는 부분이 조금 헷갈렸으나 천천히 짚어보니 이해가 됐습니다. Node* u = sentinel; 은 기존 Skiplist처럼 좌상단의 노드부터 시작합니다. k는 추가하려는 노드의 높이를 나타냅니다. r = h는 Skiplist의 높이를 취합니다. 첫 번째 While문은 Skiplist의 높이를 조건으로 사용합니다. 두 번째 while 문에서 처음 j가 등장합니다. 기본적으로 j는 수직으로 이동할 때는 값이 변화하지 않습..

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..