Skip Lists vs Binary Trees
I sent this to a bunch of my programmer-type friends recently
It’s the algorithm, stupid.
If you’ve ever taken a computer programming course, you know what a binary tree is…. and dreaded implementing it.
I present to you what looks like the obituary to binary trees:
(and check out the link, the paper is very readable)Skip Lists vs B-Trees (added: 8-May-2003)
http://www.enhyper.com/content/skiplist.pdf
Skip lists are a relatively new algorithm introduced in 1987 by William Pugh. Their simplicity and performance makes them an attractive alternative to the well known Btree algorithms. Testing reveals a dramatic speed advantage for skip lists when compared to B-trees. In addition to the basic speed advantage of the algorithm, skip lists also show an additional speed advantage for large data sets.If this article doesn’t impress you, then float it to a programmer friend of yours and you’ll likely put a smile on his face (and another tool in his toolchest)
Happy Day,
lee—-and now your random quote—-
My friend Katherine W was looking for comments on a user manual that she was writing. She sent it out to one co-worker and asked for comments back a couple days later. When returning it, he said quite confidently, “Oh yes, I read the whole thing.. And it looks just fine.” Then she pointed out the several spots where it read, “When you read this, come see me and I’ll give you 5 dollars.”
Here is a local copy of Skiplist.pdf