3 ms·
> That you can finger-append in O(u) is misleading, since ideally u≃log n What's finger-append? > finger operations are amortized O(1) in AVL trees (I know it
by jbapple 16y ago
> That you can finger-append in O(u) is misleading, since ideally u≃log n
What's finger-append?
> finger operations are amortized O(1) in AVL trees (I know it's been shown empirically, not sure if analytically)
Do you have a citation for that? I thought delete was Theta(lg n) expected, even from a finger.
- sesqu 16y agoBy 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.