Cześć, poszukuję pomocy w rozwiązaniu takiego zadania z AiSD
Jeśli w drzewach AVL zmienilibyśmy warunek, by poddrzewa mogły różnić się o 2 (nie o 1) wysokością, to Czy drzewo n-wierzchołkowe dalej ma wysokość \Theta(n)?
Próbowałem stworzyć drzewa Fibonacciego (najmniejsza liczba wierzchołków dla ustalonej wysokości h), ale nie dałem rady tego pociągnąć, jakieś porady, wskazówki? 
Zakładam, że chodził o utrzymanie wysokości \Theta(\log{n})
Jeżeli się nie mylę, to trzeba rozwiązać taką rekurencję:
N_{h} = N_{h-1} + N_{h-3} + 1
gdzie N_{h} to liczba wierzchołków w drzewie o wysokości h
Dlaczego? Obliczamy liczbę wierzchołków w obu poddrzewach a następnie dodajemy root’a. Jeżeli drzewo ma wysokosć h, to jedno z poddrzew musi mieć wysokość h-1, natomiast drugie poddrzew może różnić się o 2, czyli mieć wysokość h-3 (najgorszy przypadek). Wtedy:
N_{h} = N_{h-1} + N_{h-3} + 1
N_{h} = (N_{h-2} + N_{h-4} + 1) + N_{h-3} + 1
N_{h} = ((N_{h-3} + N_{h-5} + 1) + N_{h-4} + 1) + N_{h-3} + 1
N_{h} > 2 N_{h-3}
Stąd
N_{h} > 2 N_{h-3} > 2(2(N_{h-6})) > 2(2(2(N_{h-9}))) > \dots{} > 2^{\frac{h}{3}}
W potędze powinna być podłoga, no ale asymptotycznie nas to nie boli. Dla uproszczenia zapisu niech N = N_{h}
N > 2^{\frac{h}{3}}
\log{N} > \log{2^{\frac{h}{3}}}
3\log{N} > h
Zatem, h = O(logN). Stała wciąż będzie mała, bo C < 3, gdzie w zwykłym AVL jest to C = 1.44
Ładniejszy dowód i dokładniejsze oszacowanie moglibyśmy dostać rozwiązując to anihilatorami, no ale być może przez fakt, że to już nie do końca są liczby fibonacciego (tak jak to jest w równianiu na zwykłe drzewa AVL), dokładne rozwiązanie nie byłoby trywialne.