Tale of Two Trees: BST to AVL

A historical and practical paper describing and comparing BST and AVL trees using the Matlab PFDS functions and primary source papers.

This paper compares two data structure papers that were published in 1962. One, by Hibbard, discusses Binary Search Trees (BST). The other, by Adelson-Velsky and Landis, discusses AVL Trees. There are both gains and losses in using one or the other of these tree types. Experimental MATLAB code compares these two data types, using implementations for both in PFDS (Programmer Friendly Data Structures). All the implementation code and test code is available in the Mathworks repository, as described in the paper. The paper is both history of science and practical development advice.