5 ms·

I don't find skip lists to be simpler than AVL trees, but it's my understanding I'm in the minority on this issue. What I do find very interesting about skip l

by jbapple 16y ago

I don't find skip lists to be simpler than AVL trees, but it's my understanding I'm in the minority on this issue. What I do find very interesting about skip lists is that they support fingers - pointers to locations in the structure that allow fast modification nearby. As a very simple example, prepending an item to a skip list (this cons) is O(1) expected. Getting this property for AVL or red-black trees is possible, but much more difficult, and requires fundamental changes to the structural invariants and representations. For more on the uses of finger search, see: http://www.cs.au.dk/~gerth/pub/finger05.html http://www.cs.au.dk/~gerth/pub/finger05.html

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 jbapple 16y ago

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.