AVL vs Red-Black — jaki jest trade-off?

Głębiej

Zarówno AVL, jak i Red-Black to samobalansujące BST, które utrzymują wysokość O(log n), więc search/insert/delete mają O(log n). Różnią się „jak bardzo” pilnują zbalansowania.

AVL:

• Silniejszy inwariant balansu (balance factor -1/0/+1).
• Zwykle mniejsza wysokość, więc wyszukiwanie może być minimalnie szybsze.
• Wstawienia/usunięcia częściej powodują rotacje/równoważenie.

Red-Black:

• Luźniejszy inwariant przez reguły kolorów.
• Wysokość nadal O(log n), ale zwykle nieco większa niż w AVL