Milyen összefüggés van az elemek száma és a fa mélysége között kiegyensúlyozott fa, piros-fekete fa, minimális magasságú fa és tökéletesen kiegyensúlyozott fa esetén?

Legyen n csúcs van a fában, a magassága pedig m:

Tökéletesen kiegyensúlyozott fa:

m = [log(n+1)]      (ahol [x] a felfelé kerekítést jelenti)

Minimális magasságú fa:

Ugyanannyi, mint az előbb. (Csak a levelek elhelyezkedése más az alsó sorban.)

Kiegyensúlyozott fa:

m < 1,5 · log n       (van rá pontosabb, de sokkal bonyolultabb képlet is... lásd angol wikipedia, AVL tree)

Piros-fekete fa:

m ≤ 2 · log(n+1)

(A log itt mindenhol kettes alapú logaritmust jelent.)