کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431638 | 688602 | 2012 | 8 صفحه PDF | دانلود رایگان |
We present the Skip lift, a randomized dictionary data structure inspired by the skip list [Pughʼ90, Comm. of the ACM]. Similar to the skip list, the skip lift has the finger search property: given a pointer to an arbitrary element f, searching for an element x takes expected O(logδ) time where δ is the rank distance between the elements x and f . The skip lift uses nodes of O(1)O(1) worst-case size (for a total of O(n)O(n) worst-case space usage) and it is one of the few efficient dictionary data structures that performs an O(1)O(1) worst-case number of structural changes (pointers/fields modifications) during an update operation. Given a pointer to the element to be removed from the skip lift the deletion operation takes O(1)O(1) worst-case time.
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 13–20