Zestawy rozmówBlog

Twoja wymarzona praca? Lets Git IT.
Interaktywna platforma przygotowująca do rozmów technicznych dla nowoczesnych programistów.

XGitHub

Platforma

  • Kategorie

Zasoby

  • Blog
  • O aplikacji
  • FAQ
  • Sugestie

Prawne

  • Polityka prywatności
  • Regulamin

© 2026 LetsGit.IT. Wszelkie prawa zastrzeżone.

LetsGit.IT/Kategorie/Struktury danych
Struktury danychhard

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

Tagi
#avl#red-black#balancing#tree
Wróć do kategoriiPrzejdź do quizu

Odpowiedź

AVL utrzymuje bardziej rygorystyczne zrównoważenie, więc wyszukiwanie bywa szybsze, ale wstawienia/usunięcia częściej wymagają równoważenia. Red-Black ma luźniejsze reguły, dzięki czemu aktualizacje są tańsze, a wysokość nadal jest O(log n).

Odpowiedź zaawansowana

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

Powiązane pytania

Struktury danych
Co to są drzewa zrównoważone (np. AVL, Red-Black)?
#tree#binary-search-tree#balancing
.
  • Aktualizacje częściej wymagają mniej rotacji, więc bywa lepsze dla write-heavy.

    • Reguła kciuka

    • Read-heavy, niska latencja wyszukiwania: AVL może wygrać.
    • Mixed/write-heavy: często wybiera się Red-Black (wiele bibliotek standardowych bazuje na RB).

    Typowe pułapki

    • Myślenie, że AVL jest zawsze szybsze: zależy od workloadu i stałych.
    • Zapominanie, że oba są O(log n); trade-off dotyczy głównie liczby rotacji i stałych wysokości.

    Pytania uzupełniające

    • Co wybierzesz dla indeksu in-memory z częstymi insertami?
    • Jakie operacje wywołują rotacje i dlaczego?