<p><a href="https://en.wikipedia.org/wiki/AVL_tree" rel="nofollow noreferrer">According to wikipedia</a>, 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.</p>
<p>My questions are:</p>
<ol>
<li><p>Did Bayer and other non-Soviets know about the AVL tree (or any other self-balancing binary search tree) at this point in time?</p>
</li>
<li><p>When did the AVL tree become known to non-Soviet researchers?  And in particular, when was it translated into English?</p>
</li>
<li><p>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?</p>
</li>
</ol>

CC BY-SA 4.0
2021-04-12T19:01:12.900Z
2 and 3 are answered by reference [3] in the Wikipedia article.
Emil Jeřábek
CC BY-SA 4.0
2021-04-12T21:15:17.933Z
...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.
Hermann Gruber
CC BY-SA 4.0
2021-04-12T22:05:14.087Z
@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.
Mike Izbicki
<ho.history-overview><binary-trees>
When did self-balancing binary search trees become known outside the soviet union?
Mike Izbicki
# When did self-balancing binary search trees become known outside the soviet union?

(Asked by: username_0 on 2021-04-12)

[According to wikipedia](https://en.wikipedia.org/wiki/AVL_tree), 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?

**Tags:** ho.history-overview, binary-trees

> **Comments:**
> **username_1**: 2 and 3 are answered by reference [3] in the Wikipedia article.  
> **username_2**: ...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.  
> **username_0**: @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.  

---

## 0 answers

