2 ms·
I remember using a skiplist few years ago and I implemented it so that its memory usage averaged to just two pointers and no ancillary information per node. Thi
by huhtenberg 18y ago
I remember using a skiplist few years ago and I implemented it so that its memory usage averaged to just two pointers and no ancillary information per node. This is as small as it gets when it comes to the binary search trees and alike.
In other words the memory usage is not really an issue with skiplists.
- BrandonM 18y agoInteresting... now that I think of it, it's not necessary for a node to know how high it is, because that information is available in the traversal algorithm (the node is guaranteed to be encountered at the level which represents its height). Using a log-2 dice roll (as the algorithm specifies), you will get nodes with an average height of 2, and with only forward pointers, that does work out to 2 pointers per node. I may have to revisit my implementation and do it "right".