Fibonacci coding is a universal code defined based Fibonacci number by:
$N = \sum_{i = 0}^{k - 1} d(i).F(i + 2),$ and $d(k - 1) = d(k) = 1$
Where: $F_{i} = F_{i-1} + F_{i-2}$, for $i \geq 1$, where $F_{-1} = F_{0} = 1$
I'd like to know the complexity of this coding (Fibonacci coding) and why it's better to use this universal coding than others ?
Let $F$ be a Fibonacci tree with $n$ nodes and $h_F$ it's depth. We know that $h_F=n-1$.
The Fiboancci tree is a complete tree by definition. This means that each internal node $N_i$ has either two sons, either none. This means that the Fibonacci tree is an AVL tree, thus the complexity of any query in $F$ is O(log $h_F$) = O(log (n-1)) = O(log n), where by log we understand $log_2$.
A Fibonacci tree is automatically AVL, so you need not waste time with rotations. Being AVL, it has a compact structure, so every query takes minimum time, that is O(log n). If you'd like to understand that thoroughly, you'll have to dwelve into AVL trees.