Jak najlepiej przechowywać dane z drzew?


(Krzychu224) #1

Będę pisał program, który będzie analizował dane ze strony www. Dane te zawierają nazwy użytkowników i zależności między nimi -> Zależności tworzą strukturę drzewa i teraz zastanawiam się jaki będzie najlepszy sposób, żeby te dane przechowywać? Jakie struktury będą najlepsze?


(kostek135) #2

Najlepsze do czego? W sensie co chcesz dalej z nimi zrobić?

  1. Wyświetlić w liście? Prawdopodobnie lista

  2. Zachować strukturę do przetwarzania - podejrzewam, że drzewo

  3. Badać przepływy, ścieżki, etc. - grafy

  4. itd itd.


(Krzychu224) #3

Chodzi mi o to w jaki sposób upakować to na poziomie programu. Wiadomo, że zachowanie struktury drzewa jest potrzebne ale w językach nie ma struktury danych - drzewo.

W sumie może to głupie pytanie, ale nigdy nie robiłem czegoś takiego. Mógłbym np. stworzyć tablicę i po kolei wrzucać dane węzła + wskaźniki na dzieci ale zastanawiam się czy właśnie w taki sposób się to robi?


(kostek135) #4

Teraz uściśliłeś o co chodzi robisz coś takiego:

C++ pseudo-code (tak wiem nie tak sie robi template, ale chodzi o zasadę):

class Node {

    T* dataPtr; // wskaźnik do danych albo same dane najlepiej parametryczne zwiększy re-use. Lepszy wskaźnik, bo możesz chcieć niszczyć node, a nie same dane.

    Node** childs; //tablica wskaźników do dzieci, ale można też użyć np vector'a (realokuje sie jest size i inne szmery bajery) wskaźników na inne nody.

}

W innych językach będzie podobnie tylko może referencja zamiast pointera, przykładowo java.

To tak generalnie bo istnieją jeszcze drzewa specjalnego przeznaczenia, drzewa binarne (w tym kopiec binarny), drzewa przedziałowe, b-drzewa, etc. trudno ci doradzić - nie wiadomo co chcesz zrobić konkretnie, ale ogólna zasada rozpoczęcia pracy z drzewem jest taka jak podałem.

EDIT: PS czasem warto też znać rodzica, żeby móc iść w górę, robisz to dodatkowym polem Node* parent; Technicznie korzeń będzie miał NULL wtedy iście z dowolnego węzła do korzenia, będzie while(parent != NULL) idź węzeł do góry. No i to tyle w sumie odwzorowanie 1:1.