Dlaczego implementacja drzewa czerwono-czarnego dla drzewa JavaMap?

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."Dlaczego implementacja drzewa czerwono-czarnego dla drzewa JavaMap?

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)?

Źródło

2013-02-17 Nikunj Banka

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.

Źródło

2013-02-17 16:43:18 Justin

+15

Java używa quicksort dla obiektów pierwotnych, ponieważ jest szybszy niż sortowanie scalone w przypadku przeciętnym. Używa sortowania scalonego do sortowania obiektów, ponieważ sortowanie scalone jest stabilnym algorytmem sortowania. ZOBACZ: http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types –

@NikunjBanka Dobre informacje, dzięki! – Justin

Ponieważ Java 7 merge-sort została zastąpiona przez TimSort http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6804124 –

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ą.

Źródło

2013-02-17 19:12:15 googmeister

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.

Źródło

2017-10-20 23:13:39

Dlaczego implementacja drzewa czerwono-czarnego dla drzewa JavaMap?

Odpowiedz

Powiązane problemy