Comment by jbapple

These trees nearly identical to Scapegoat Trees, which were a rediscovery of the idea by different authors. https://cglab.ca/~morin/teaching/5408/refs/a99.pdf has the history:

"A preliminary version of this article is published in Proceedings of Workshop on Algorithms and Data Structures, WADS ’89, Ottawa. An independent article has also been presented by Galperin and Rivest at the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA."