strongly resembles that of fibonacci numbersthey are called fibonacci-trees (see fig they are defined as follows the empty tree is the fibonacci-tree of height single node is the fibonacci-tree of height if - and - are fibonacci-trees of heights - and - then is fibonacci-tree no other trees are fibonacci-trees fig fibonacci-trees of height and the number of nodes of is defined by the following simple recurrence relationn nh nh- nh- the nh are those numbers of nodes for which the worst case (upper limit of hcan be attainedand they are called leonardo numbers balanced tree insertion let us now consider what may happen when new node is inserted in balanced tree given root with the left and right subtrees and rthree cases must be distinguished assume that the new node is inserted in causing its height to increase by hl hrl and become of unequal heightbut the balance criterion is not violated hl hrl and obtain equal heighti the balance has even been improved hl hrthe balance criterion is violatedand the tree must be restructured consider the tree in fig nodes with keys and may be inserted without rebalancingthe tree with root will become one-sided (case )the one with root will improve its balance (case insertion of nodes or howeverrequires subsequent rebalancing fig balanced tree some careful scrutiny of the situation reveals that there are only two essentially different constellations