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, np. n
Czytaj całość »

metodyka testowania implementacji drzew czerwono czarnych na bazie tablicy

Kod nieprzetestowany albo nie działa w ogóle, albo nie działa poprawnie - i tak było w przypadku tej implementacji drzew czerwono - czarnych . Dlatego napisałem specjalny kod do przetestowania. Metodyka jaką przyjąłem polega na testowaniu porównawczym. Trzy takie same programy, oparte jednak na innych implementacjach drzew czerwono - czarnych , muszą dać takie same wyniki. W celu przetestowania zaprojektowałem 15 procedur. Każda procedura, w przybliżeniu, testuje kolejną metodę z tej implementacji, a także analogiczne metody z implementacji w std::set i QMap. Kolejność wywoływania procedur jest losowa, a także losowa jest kolejność wybierania implementacji, co powinno wykluczyć błędy ujawniające się tylko przy określonej kolejności, np. po wywołaniu metody sort, która kompletnie reorganizuje ułożenie węzłów w pamięci. Oczywiście niektóra kolejność wywoływania procedur jest błędna z założenia, np. po wywołaniu metod: insert, remove, nie można wywoływać metod z przed
Czytaj całość »