According to wikipedia, the AVL tree was first published in 1962 by Soviet scientists Adelson-Velsky and Landis. The earliest self-balancing binary search tree I can find by a non-soviet block scientist is the red-black tree, created by West German computer scientist Rudolf Bayer in 1972.

My questions are:

  1. Did Bayer and other non-Soviets know about the AVL tree (or any other self-balancing binary search tree) at this point in time?

  2. When did the AVL tree become known to non-Soviet researchers? And in particular, when was it translated into English?

  3. I can't find copies of the original publications online for these papers, but I'd like to read them for their references. Can anyone help me find copies?

  • 2
    $\begingroup$ 2 and 3 are answered by reference [3] in the Wikipedia article. $\endgroup$ – Emil Jeřábek Apr 12 at 19:01
  • 2
    $\begingroup$ ...and 1 can be answered by looking at the technical report version of the paper introducing B-trees, which is linked from the Wikipedia article on B-tree. The answer is yes, they were aware of it, since they cite it. For this kind of question, it can also help to go to a university library (in case this is feasible for you) and browse through the academic journal volumes if googling does not help. $\endgroup$ – Hermann Gruber Apr 12 at 21:15
  • $\begingroup$ @EmilJeřábek Thanks! Don't know how I missed that. To fully answer my title question, then, I need to know whether the AVL tree was the first self-balancing binary search tree. Based on the paper, I'm guessing yes since they don't cite any prior work, but that could just be because they didn't know about it. $\endgroup$ – Mike Izbicki Apr 12 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.