New Terminology and Results for AVL Trees

We introduce gaps which are special edges or external pointers in AVL trees such that the height difference between the subtrees rooted at two endpoints of a gap is equal to 2. Using gaps we prove the Basic-Theorem which 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 a 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 defining Fibonacci-isomorphic trees, and we show that they have the maximum number of gaps in AVL trees. In the rest of the paper, we study combinatorial properties of these trees. Keywords: AVL tree, Fibonacci tree, Fibonacci-isomorphic tree, Gaps in AVL tree, Subtree size, Enumeration, Encoding.