Drzewa Czerwno Czarne [Red Black Trees]

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

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: Kod źródłowy drzewa czerwono - czarnego wersja beta 0.00v 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.

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

To jest kod open-source, jest jednak rozprowadzany na innej licencji niż typowe licencje open-source. Jeśli poniższa licencja Tobie nie odopowiada, to skasuj ten kod ze swojego komputera. Możesz ten kod pobrać z mojej strony internetowej, możesz go czytać możesz go używać nieodpłatnie w swoich programach, możesz go zmieniać, jednak pod kilkoma warunkami i w określonych poniżej ramach. Zanim zaczniesz cokolwiek robić z wykorzystaniem tego kodu zapoznaj się z opisem. Niektóre cechy tego kodu, można łatwo uznać za błędy. Możesz ten kod pobrać z mojej strony internetowej, nie możesz rozprowadzać tego kodu ani w oryginalne, ani po zmianach, ani w całości, ani we fragmentach, ani obcym, ani znajomym.  Jeśli rozprowadzasz wesję skompilowaną tego kodu, nie musisz udostępniać źródła, ani mnie informować, ani nic płacic. Jeśli jednak mnie poinformujesz, to zrobię Ci małą reklamę, napiszę że Twój program korzysta z tego kodu, opublikuję Twój e-mail i link do strony Twojego programu....

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

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