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

Leave a Comment

Do not write "http://" in your comment, it will be blocked. It may take a few days for me to manually approve your first comment.

You can edit your comment after submitting it.