kod źródłowy C++ drzewa czerwono czarnego wrsja beta 0.00v

Zamieszczam do pobrania kod źródłowy implementacji na tablicy drzewa czerwono czarnego w postaci szablonu C++. Kod został sformatowany przy pomocy hilite. Implementacja jest dostępna pod poniższym linkiem:


Pobierz powyższy kod i zapisz najlepiej jako plik nagłówkowy rb_tree.h

Jeśli znajdziesz jakieś błędy w kodzie, albo będziesz miał pomysły na udoskonalenie lub przyspieszenie, zapraszam do podzielenia się wszystkim w komentarzach. Mam nadzieję jednak, że Twoja aplikacja dzięki tej implementacji będzie działa bezbłędnie i nieco szybciej.
Wkrótce zamieszczę instrukcje z przykładami jak można używać tej biblioteki.

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ść »