期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2018
卷号：15
期号：1
页码：14-21
DOI：10.1016/j.akcej.2018.01.019
语种：English
出版社：Elsevier
摘要：AbstractWe introducegapsthat 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 theBasic-Theoremthat 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 introducingFibonacci-isomorphic treesthat are isomorphic toFibonacci treesof the same height and showing that they have the maximum number of gaps in AVL trees. Note that twoordered trees(such as AVL trees) areisomorphiciff 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.
关键词：KeywordsAVL treeFibonacci treeFibonacci-isomorphic treeGaps in AVL treeEncoding
