Do jakich zastosowań nadają się drzewa czerwono-czarne?

Najogólniej pisząc, drzewa czerwono-czarne są dynamiczną strukturą umożliwiającą szybkie wyszukiwanie i modyfikowanie danych. Część dalsza wkrótce.
     
     
     

Komentarze

Prześlij komentarz

Popularne posty z tego bloga

benchmark 00 tablicowej implementacji drzew czerwono czarnych

Kilka postów wcześniej zobowiązałem się przedstawić bencznarki i pomiary czasu implementacji tablicowej drzew czerwono - czarnych . Pokażę zatem, czy implementacja tablicowa naprawdę działa szybciej, o ile szybciej i w jakich sytuacjach możemy uzyskać przyspieszenie względem szablonów takich jak std::set i QMap. Benczmark 00 dotyczy wersji beta 0.00v. Na potrzeby tego bencznarku napisałem specjalny program i specjalny skrypt powłoki bash. Skrypt kompiluje, optymalizuje i profiluje kod bibliotek, kod drzewa czerwono czarnego i kod samego bencznmarku. Do kompilacji i profilowania został wykorzystany kompilator g++, więcej szczegółów kompilacji można wyczytać w pliku bench00.sh. Do pobrania: kod źródłowy bencznarku (pobierz i zapisz jako bench00.cpp) Do pobrania: skrypt ułatwiający uruchomienie testu (pobierz i zapisz jako bench00.sh) Wszystkie testy w benchmarku 00 są przeprowadzane na  32bitowym typie bez znaku unsigned int. Zapewne pomiary czasu na większym typie, n...
Czytaj całość »

Zalety i wady implementacji drzew czerwono czarnych na tablicy

Opisywana implemetnacja drzew czerwono - czarnych na tej stronie została zrealizowana w oparciu o ciągły obszar pamięci , innymi słowy, w oparciu o tablicę elementów . Taki obszar pamięci można zapewnić przy pomocy odpowiedniego allocatora. Przykładowymi allocatorami mogą być: struktura QVector z biblioteki QT, std::vector z biblioteki standardowych szablonów w C++, a nawet std::array i QVarLengthArray. Można też samodzielnie obudować zwykłą tablicę klasą C++ i przekazać tę klasę jako parametr szablonu RBTree. Dla wygody zostały przygotowane trzy gotowe allocatory. Zatem już na pierwszy rzut oka widać, że ta implementacja drzew czerwono czarnych nie jest standardowa, ponieważ zwykle spotykamy się w praktyce i w literaturze z implementacją na wskaźnikach. Z implemetnacją na ciągłym obszarze pamięci wiąże się szereg zalet i wad. Zalety implementacji na tablicy W pobieżnych testach implementacja na tablicy działa szybciej. Rzadziej jest wywoływana funkcja malloc, jest mniejszy na...
Czytaj całość »

Wyzwanie - wydajny uporządkowany zbiór w C++

      Dużo jest dostępnych bibliotek C++ implementujących uporządkowany zbiór z możliwością modyfikowania i wyszukiwania (i nie tylko) w czasie Log(N), gdzie N jest ilością danych przechowywanych w zbiorze. Szablony  takie jak std::set, std::map, QMap z biblioteki standardowej i biblioteki QT, oferują taką możliwość.  Szablony te oferują taką możliwość dzięki temu, że zostały zaimplementowane w oparciu o strukturę danych nazywaną drzewami czerwono -czarnymi (ang red -black trees ). Strukturami o podobnych możliwościach są drzewa AWL, B-Drzewa, 2-3-4 drzewa, a także po prostu wszelkie drzewa wyszukiwań (nie koniecznie wyszukiwań binarnych) z dowolnym mechanizmem równoważenia.       Drzewa bez  mechanizmu równoważenia nie zawsze gwarantują szybkie wyszukiwe, modyfikowanie (i kilka innych operacji) w czasie logarytmicznym Log(N). Gdy dane do drzewa nie są wstawiane w kolejności losowej, to drzewa bez mechanizmu balansowan...
Czytaj całość »