4
건너 뛰기 목록이 정렬 된 데이터 구조라는 것을 알고 있지만 중복 요소가있을 수 있습니까? 또는 이미 존재하는 요소를 삽입하려고하면 기존 요소에 대한 포인터를 반환해야합니까?건너 뛰기 목록에 중복 된 요소가있을 수 있습니까?
A
답변
3
대답은 "예, 건너 뛰기자가 중복 요소를 가질 수 있지만 필수는 아닙니다."입니다.
중복을 지원하는 skiplist를 만들 수 있습니까? 전혀! 삽입 프로 시저를 업데이트하면 찾고있는 요소가 보이면 바로 뒤에 요소를 삽입 할 수 있습니다. 여러 개의 동일한 값을 저장하는 BST를 사용하는 것과 비슷합니다. 동일한 절차를 수행 할 때 삽입 절차를 항상 왼쪽으로 또는 항상 오른쪽으로 이동하면됩니다.
하지만 은이어야합니다. skiplist는 항상 중복을 허용합니까? 아니요, 모든 BST가 중복을 허용하지는 않습니다.
skiplist 라이브러리를 사용하는 경우 설명서를 참조하여 중복 라이브러리를 지원하는지 확인하십시오. 자신 만의 제품을 만드는 경우 자유롭게 원하는대로 만들 수 있고 결정을 문서화 할 수 있습니다.
http://www.cs.yorku.ca/~ruppert/Mikhail.pdf를 참조하십시오. –