Dlaczego implementacja drzewa czerwono-czarnego dla drzewa JavaMap?

Question

Trzeci akapit wikipedia's article on AVL trees mówi: "Ponieważ drzewa AVL są bardziej sztywno zbalansowane, są szybsze niż drzewa czerwono-czarne dla aplikacji intensywnie korzystających z wyszukiwania."

A więc czy nie należy implementować TreeMap przy użyciu drzewek AVL zamiast drzew czerwono-czarnych (ponieważ będzie więcej wyszukiwań intensywniejszych dla struktury danych opartych na haszowaniu)?

Answer 1

Drzewa czerwono-czarne mają bardziej ogólny cel. Robią to stosunkowo dobrze przy dodawaniu, usuwaniu i wyszukiwaniu, ale drzewa AVL mają szybsze wyszukiwania kosztem wolniejszego dodawania/usuwania. Ogólna polityka Java to zapewnienie najlepszych struktur danych ogólnego przeznaczenia. Z tego samego powodu domyślna implementacja Array.sort (Object [] a) w Javie jest stabilna, adaptacyjna, iteracyjna sortuj zamiast quicksort.

Answer 2

Artykuł w Wikipedii jest błędny (a przynajmniej nie ma żadnego uzasadnienia, aby potwierdzić roszczenie). Prawdą jest, że najgorsza wielkość drzewa AVL (1,44 lg n) jest lepsza niż najgorsza szansa na czerwono-czarne BST (2 lg n), ale jest to najgorszy przypadek i może nie mieć wiele do zrobienia z rzeczywistą wydajnością.

Answer 3

Historycznie, liczba obrotów była uważana za bardzo ważną, więc czerwono-czarne drzewa zostały wybrane nad AVL, ponieważ czerwono-czarna wykonuje nieco mniej rotacji z losowymi wstawkami - .6 vs .7 średnie obroty na wkładkę.

Z perspektywy czasu, drzewa AVL prawdopodobnie byłyby lepszym wyborem. Możesz zobaczyć porównanie wydajności AVL & czerwono-czarnych drzew w Javie tutaj: https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/

Przy losowych wstawkach wydajność jest podobna. W przypadku danych sekwencyjnych drzewa AVL działają znacznie lepiej - 30% lub więcej.