3 ms·
By finger-append I meant that skip lists are normally singly linked, and so you can append to a sublist but not prepend nor insert into the implied subtree. Th
by sesqu 16y ago
By finger-append I meant that skip lists are normally singly linked, and so you can append to a sublist but not prepend nor insert into the implied subtree.
The O(1) wasn't amortized, it was expected. The citation is P. L. Karlton, S. H. Fuller, R. E. Scroggs and E. B. Kaehler, Performance of height-balanced trees. Comm. ACM 19, 1 (1976), 23-28.
- sesqu 16y agoI should also note that it's not very surprising that AVL restructurings show up as expected O(1) empirically, since many AVL trees are BB-trees, and it's been shown for BB-trees under the assumption that the root approximates the median - which is certainly true in most experimental settings. So It's quite possible the expectation isn't O(1) for pathological distributions, not to mention sequences.