Witam
Czy da się w jakiś sposób mając iterator do jakiegoś elementu seta wyłuskać iterator do jego ojca,lewego syna i prawego syna w drzewie czerwono-czarnym ? Przydałoby się to do tworzenia zmodyfikowanych drzew np. drzew przedziałowych gdyż pisanie własnej implementacji drzewa czerwono-czarnego jest dość męczące.
0
2
Nie masz gwarancji że set jest zaimplementowany jako drzewo, standard tego nie gwarantuje.
Biblioteka boost ma: http://www.boost.org/doc/libs/1_42_0/doc/html/boost/intrusive/rbtree.html
0
Używanie biblioteki boost nie wchodzi w grę gdyż jest mi to potrzebne do OI gdzie nie mogę używać zewnętrznych bibliotek.
Nie wiem co gwarantuje standard ale w każdym razie tu : http://www.cplusplus.com/reference/set/set/
jest napisane że są to drzewa wyszukiwań binarnych.
0
Pafos napisał(a):
Nie wiem co gwarantuje standard ale w każdym razie tu : http://www.cplusplus.com/reference/set/set/
jest napisane że są to drzewa wyszukiwań binarnych.
I co z tego, skoro nie masz dostępu do liści?
Chyba nie zamierzasz dłubać po prywatnych atrybutach klasy kontenera / iteratora?
Biblioteki są zabronione, bo to żadna sztuka ściągnąć sobie odpowiednią implementację (chociażby nagłówkową) i ją użyć.
0
np. drzew przedziałowych gdyż pisanie własnej implementacji drzewa czerwono-czarnego jest dość męczące.
Akurat drzewa przedziałowe możesz łatwiej, szybciej i zużywając mniej pamięci zaimplementować na statycznej tablicy.
Możesz o tym posłuchać/poczytać tutaj http://was.zaa.mimuw.edu.pl/?q=node/8
Implementacja drzew przedziałowych za pomocą drzew czerwono-czarnych to najczęściej mocne utrudnianie sobie życia.
0
To szkoda że nie da się wykorzystać do tego seta. Implementacja na statycznej tablicy narzuca ograniczenie na wielkość dziedziny ale mam nadzieję że nie będzie to bardzo przeszkadzało. Dzięki wam za pomoc :d
0
W temacie OI, warto wspomnieć o komparatorach, które można wpakować do seta i dzięki temu otrzymać na przykład kolejkę priorytetową, bądź też do sorta otrzymując sortowanie na podstawie własnych kryteriów. Przykład: http://en.cppreference.com/w/cpp/algorithm/sort