1-2 Brother Trees or AVL Trees Revisited

Open Access
Publisher Website
Google Scholar
Abstract
1-2 brother trees are binary search trees which have similarities to both height balanced search trees and 2-3 trees. Firstly, 0(log2n) insertion and deletion algorithms are demonstrated and their similarities with those for brother trees are noted. Secondly, it is proved that the space utilisation of (random) 1-2 brother trees is much better than that for (random) 2-3 trees. Thirdly, the close relationship between 1-2 brother trees and height balanced trees is demonstrated, and as this also holds for their right-sided counterparts it leads to 0(log2n) insertion and deletion algorithms for right-sided height balanced trees. Finally, this demonstrates that the insertion and deletion algorithms for right-sided height balanced trees were already available, but hidden, in the corresponding algorithms for right brother trees.

This publication has 0 references indexed in Scilit: