Gap terminology and related combinatorial properties for AVL trees and Fibonacci-isomorphic trees

Abstract

We introduce gaps that are edges or external pointers in AVL trees such that the height difference between the subtrees rooted at their two endpoints is equal to 2. Using gaps we prove the Basic-Theorem that illustrates how the size of an AVL tree (and its subtrees) can be represented by a series of powers of 2 of the heights of the gaps, this theorem is the first such simple formula to characterize the number of nodes in an AVL tree. Then, we study the extreme case of AVL trees, the perfectly unbalanced AVL trees, by introducing Fibonacci-isomorphic trees that are isomorphic to Fibonacci trees of the same height and showing that they have the maximum number of gaps in AVL trees. Note that two ordered trees (such as AVL trees) are isomorphic iff there exists a one-to-one correspondence between their nodes that preserves not only adjacency relations in the trees, but also the roots. In the rest of the paper, we study combinatorial properties of Fibonacci-isomorphic trees.