4 ms·

I find AVL trees simpler as well, and probably a good deal more performant. The nice thing about skip lists, beyond being mostly simple, is that min() is O(1)

by sesqu 16y ago

I find AVL trees simpler as well, and probably a good deal more performant. The nice thing about skip lists, beyond being mostly simple, is that min() is O(1), which is far more useful than the middling value at the root of AVL trees. That you can finger-append in O(u) is misleading, since ideally u≃log n and finger operations are amortized O(1) in AVL trees (I know it's been shown empirically, not sure if analytically).

antirez 16y ago
Since MIN / MAX are O(1) operations there is a trivial optimization where you can add elements that are greater or smaller of any other element in O(1), and in many applications this is happens with a great probability. Of course you can do this for AVL trees as well, but in order to do so there is to take additional information in the structure.
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 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 ago
    I 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.

by sesqu 16y ago

antirez 16y ago

Since MIN / MAX are O(1) operations there is a trivial optimization where you can add elements that are greater or smaller of any other element in O(1), and in many applications this is happens with a great probability. Of course you can do this for AVL trees as well, but in order to do so there is to take additional information in the structure.

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