> The algorithms for AVL/red-black/splay trees are not especially complex
and can be coded once, then used in millions of programs. That whole point is largely moot.
A red-black tree gives you certain guarantees without any probabilistic arguments. Wikipedia: A skip list does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure.
A skip list algorithm which guards against the worst case will necessarily have to do some rebalancing that requires nodes to move among levels according to some heuristic.
Skip lists are not storage efficient unless the nodes are variably sized. If each node includes enough pointers to participate in any level, then you waste space. Variable size means we cannot draw nodes from a single, compact pool array of nodes for a skip list. Variable size also creates difficulties if we want to use this as an "intrusive container". (A container which works by inserting the necessary node links and other fields into the client's data structure, so that the client data structures directly link into the graph as nodes, rather than being separately allocated and referenced from it.)
This uses the C struct hack for variable node sizing, which makes it rely on malloc for the nodes. A client cannot pass in a pre-allocated node.
A mistake in this type of code can lead to a buffer overflow: accessing the n-th level of a node which only has k < n levels worth' of pointers.
If logic were added which moves a node from one skip level to another, that would require the entire node to be realloc'ed, if its number of links needs to increase. Realloc-ing can change its address; all existing pointers to the node must be rewritten.
and can be coded once, then used in millions of programs. That whole point is largely moot.
A red-black tree gives you certain guarantees without any probabilistic arguments. Wikipedia: A skip list does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure.
A skip list algorithm which guards against the worst case will necessarily have to do some rebalancing that requires nodes to move among levels according to some heuristic.
Skip lists are not storage efficient unless the nodes are variably sized. If each node includes enough pointers to participate in any level, then you waste space. Variable size means we cannot draw nodes from a single, compact pool array of nodes for a skip list. Variable size also creates difficulties if we want to use this as an "intrusive container". (A container which works by inserting the necessary node links and other fields into the client's data structure, so that the client data structures directly link into the graph as nodes, rather than being separately allocated and referenced from it.)
I'm looking at a C implementation pointed at by DADS. http://epaperpress.com/sortsearch/txt/skl.txt
This uses the C struct hack for variable node sizing, which makes it rely on malloc for the nodes. A client cannot pass in a pre-allocated node.
A mistake in this type of code can lead to a buffer overflow: accessing the n-th level of a node which only has k < n levels worth' of pointers.
If logic were added which moves a node from one skip level to another, that would require the entire node to be realloc'ed, if its number of links needs to increase. Realloc-ing can change its address; all existing pointers to the node must be rewritten.