I am teaching 600.226: Data Structures as a summer session course right now, and we covered AVL Trees yesterday. As I was ranting about them I suddenly realized that they were first published in 1962, and here I am in 2012 still teaching them to my eager (and somewhat perplexed) students.
So blame my brain: I have never been able to develop a good intuition about red-black trees (which I gather is what "respectable" schools are supposed to teach). My favorite balanced trees are treaps anyway, because they take so little code yet perform so well. But I feel that I "owe" my students at least one deterministic balanced search tree, and 2-3(-4) trees are just so messy to implement. Hence AVL!
I started to wonder: Since AVL trees were published in 1962, were they the first efficient data structure for ordered sets or maps? So I did some checking, and here is what I found:
AVL Trees 1962
B-Trees 1970
Symmetric Binary B-Trees 1972
Finger Trees 1977
Red-Black Trees 1978
Splay Trees 1985
Treaps 1989
If we losen things up a bit and include things that either demand more of the data or provide fewer general operations, we could consider these as well:
Tries 1960
Heaps 1964
So as far as I can tell after a quick search, AVL Trees are indeed the oldest efficient way to maintain a dynamic ordered set or map. And since students still have some trouble implementing them today, I guess that means we either haven't made a lot of progress, or we should take our proverbial hats off and nod a quiet "Thanks!" to Adelson-Velskii and Landis for figuring out how balanced search trees should work before most of us were even born.
No comments:
Post a Comment