Aszimptotikusan ugyanolyan jó, mint az AVL-fa, minden művelet O(lg n) legrosszabb esetben. A konstans tényezői pedig nem különböznek jelentősen a piros-fekete fa konstans tényezőitől. Ha érdekes működésű fa kell, ajánlom a splay fát.