Algorytm oparty o strukturę drzew

Witajcie! :) Mam do napisania algorytm opierając jego działanie o drzewa patricia, b-drzewa, avl lub czerwono-czarne.

Głównym zadaniem jest utworzenie spisu mieszkańców osiedla.
Kluczem jest numer pesel osoby.
Pozostałe dane dla każdej osoby to imię i nazwisko.

Można dodać "dziecko" poleceniem "pesel1 pesel2" gdzie pesele to pesele tych osób tj. rodzica i dodawanego dziecka.

Moim zdaniem należy tu porządkować po dacie urodzenia z peselu i w "wierzchołku" przechowywać dodatkowy numer pesel określający "ojca", ale problem dotyczy czego innego...

Niby wszystko fajnie ale problem pojawia się gdy trzeba wyświetlić członków rodziny dla każdej osoby, bo jak to wtedy OPTYMALNIE robić ? To jest chyba kontrprzykład tego, że moje rozumowanie nie jest poprawne, bo według mojego rozumowania trzebybyło przejść wszystkie wierzchołki. Jak to zrobić optymalnie ?

Dzięki za pomoc!

Nie za bardzo rozumiem co masz zrobić, co chcesz zrobić i dlaczego nie możesz tego zrobić :D

O ile wiem czym w kontekście drzewowym są ojciec i dziecko, to czym w takim razie jest rodzina danej osoby?

Rozwiązanie przykładowe, przy założeniu, że każda osoba to obiekt posiadające pole określające PESEL: kopiujesz kod TreeSeta z biblioteki standardowej Javy (albo innego języka), tworzysz komparator porównujący PESELe, względnie implementujesz interfejs Comparable w klasie Osoba, który porównuje PESELe. Jeśli chcesz znaleźć osobę po PESELu wywołujesz get(pesel). Jeśli chcesz znaleźć ojca to robisz get(dziecko.peselOjca).

Klasa Osoba niech ma pole pesel oraz np peselOjca i peselMatki. Po niej niech dziedziczy np klasa Rodzic z polami: listaPeseliDzieci, peselŻony, etc Mając obiekt dowolnej klasy możemy wtedy łatwo i szybko dostać się do krewnego.

Niby wszystko fajnie ale problem pojawia się gdy trzeba wyświetlić członków rodziny dla każdej osoby,
Rodzina to wszystko co jest w dół drzewa (dzieci, wnuki) oraz powiedzmy dwa poziomy w górę (rodzice, dziadki) i wszystko co jest w dół od tych rodziców i dziadków (wujki, kuzyni).

Wibowit napisał(a)

Rozwiązanie przykładowe, przy założeniu, że każda osoba to obiekt posiadające pole określające PESEL: kopiujesz kod TreeSeta z biblioteki standardowej Javy (albo innego języka), tworzysz komparator porównujący PESELe, względnie implementujesz interfejs Comparable w klasie Osoba, który porównuje PESELe. Jeśli chcesz znaleźć osobę po PESELu wywołujesz get(pesel). Jeśli chcesz znaleźć ojca to robisz get(dziecko.peselOjca).

Klasa Osoba niech ma pole pesel oraz np peselOjca i peselMatki. Po niej niech dziedziczy np klasa Rodzic z polami: listaPeseliDzieci, peselŻony, etc Mając obiekt dowolnej klasy możemy wtedy łatwo i szybko dostać się do krewnego.

Ale na jakiej zasadzie działa wtedy "get(dziecko.peselOjca)" ? Jeżeli chcę znaleźć wszystkich członków rodziny dla określonej osoby to jak przechodzić po drzewie aby to znaleźć z OPTYMALNĄ złożonością - muszę własnoręcznie napisać kod, a nie mogę korzystać z gotowych funkcji itp. Czy muszę przejść po wszystkich wierzchołkach ? Dodam tylko że ja mam wyszukać członków rodziny a nie cały czas przechowywać ich w jakiejś strukturze danych ;/

Głównym zadaniem jest utworzenie spisu mieszkańców osiedla.
Kluczem jest numer pesel osoby.
Pozostałe dane dla każdej osoby to imię i nazwisko.

Wybitnie chodzi o to, żeby zrobić zrównoważone drzewo uporządkowane po PESELu. Wtedy operacja get(pesel) zajmie O(lg n) czasu.

Można dodać "dziecko" poleceniem "pesel1 pesel2" gdzie pesele to pesele tych osób tj. rodzica i dodawanego dziecka.

Gdzie to ma być powiązane? Ja się domyśliłem w poprzednim poście, że np PESEL ojca ma być w dziecku i np PESEL dziecka ma być w ojcu. Wtedy można łatwo i szybko przejść z dziecka do ojca i z powrotem - get(pesel) działa w czasie O(lg n), więc m wywołań get(...) zajmie O(m lg n).

Dodam tylko że ja mam wyszukać członków rodziny a nie cały czas przechowywać ich w jakiejś strukturze danych ;/

Skąd masz wiedzieć, że ktoś jest członkiem rodziny, skoro nie chcesz przechowywać żadnych informacji o powiązaniach?

Ewentualnie zamiast przechowywać PESEL ojca czy dziecka w obiekcie można przechowywać bezpośrednio referencję do dziecka czy ojca. Dereferencja zajmuje teoretycznie O(1), więc miałbyś optymalną złożoność szukania rodziny.

Wibowit napisał(a)

Można dodać "dziecko" poleceniem "pesel1 pesel2" gdzie pesele to pesele tych osób tj. rodzica i dodawanego dziecka.
Gdzie to ma być powiązane? Ja się domyśliłem w poprzednim poście, że np PESEL ojca ma być w dziecku i np PESEL dziecka ma być w ojcu. Wtedy można łatwo i szybko przejść z dziecka do ojca i z powrotem - get(pesel) działa w czasie O(lg n), więc m wywołań get(...) zajmie O(m lg n).

Tak, powiedzmy że w strukturze jednego wierzchołka będę przechowywać PESEL jego ojca i jego dzieci (max 2) czyli 3 numery pesel. Ale co w przypadku gdy muszę dla danej osoby podać (czyli wyszukać w drzewie) rodzeństwa, przodków i potomków różnych rzędów: dzieci, wnuków itd, rodziców, dziadków itd. Jak wtedy to ogarnąć aby uzyskać dobrą złożoność ? Pierwsza myśl jaka przychodzi do głowy to szukać n członków rodziny kosztem mlogn każde wyszukanie, ale to na pewno za słabe rozwiązanie, bo można rzecz że pesymistyczny przypadek to n^2logn, czy da się to zrobić lepszym sposobem ?

Reszta rzeczy opisanych przez Ciebie jest oczywiście jasna.
Dzięki za pomoc!

Skąd ci się wzięło n^2 lg n? Jeśli rodzina to całe drzewo to pesymistycznie miałbyś n lg n. Przy referencjach miałbyś n.

Do każdego obiektu dodaj PESEL/ referencję do rodziców oczywiście. No i zrób listę dzieci, bo może być ich dowolna ilość.

Wibowit napisał(a)

Skąd ci się wzięło n^2 lg n? Jeśli rodzina to całe drzewo to pesymistycznie miałbyś n lg n. Przy referencjach miałbyś n.

Tak już rozumiem tą kwestie, dzięki :)

Wibowit napisał(a)

Do każdego obiektu dodaj PESEL/ referencję do rodziców oczywiście. No i zrób listę dzieci, bo może być ich dowolna ilość.

Jak to ma działać ? Z wierzchołka (rodzica) mogą odchodzić dwa kolejne wierzchołki (dzieci) czyli w moim rozumowaniu wierzchołek reprezentuje jednego rodzica i taki rodzic może mieć max. dwójkę dzieci - gdzie "upakować" tu listę tych dzieci ? To jest moje rozumowanie, ale wygląda że jest błędne jeżeli porównać z tym co Ty napisałeś, czy mógłbyś rozwinąć swój tok rozumowania, bo ja na starcie obrałem inną drogę i jakoś nie mogę zrozumieć Twojego sposobu :)

Dziękuje za pomoc.

Nic nie rozumiesz. Drzewa mają być zrównoważone i indeksowane po PESELach, a więc porządek musi być jak w BST natomiast wysokość drzewa logarytmiczna. Lewy węzeł ma mieć mniejszy PESEL, prawy ma mieć większy, itd (tzn ma zachować normalne własności BST). Rodzic to tutaj pojęcie dwuznaczne - albo rodzic w drzewie BST, albo rodzic w sensie pokrewieństwa.

A więc węzeł drzewa ma mieć postać:

class Drzewo {
Węzeł korzeń;
}

class Węzeł {
int balans; // jeżeli AVL
boolean kolor; // jeżeli czerwono-czarne
Osoba osoba;
Węzeł leweDziecko;
Węzeł praweDziecko;
Węzeł rodzic; // może być, ale nie musi, zależy czy prędzej zrozumiesz zrównoważone BST z rodzicami czy bez
}

class Osoba {
Osoba ojciec; lub String peselOjca;
Osoba matka; lub String peselMatki;
String pesel;
}

class Rodzic extends Osoba {
List<Osoba> dzieci; lub List<String> peseleDzieci;
}

Poczytaj jak działają np te drzewa czerwono-czarne, a potem przeczytaj jeszcze raz tego posta.

Wibowit napisał(a)

Nic nie rozumiesz. Drzewa mają być zrównoważone i indeksowane po PESELach, a więc porządek musi być jak w BST natomiast wysokość drzewa logarytmiczna. Lewy węzeł ma mieć mniejszy PESEL, prawy ma mieć większy, itd (tzn ma zachować normalne własności BST). Rodzic to tutaj pojęcie dwuznaczne - albo rodzic w drzewie BST, albo rodzic w sensie pokrewieństwa.
[...]
Poczytaj jak działają np te drzewa czerwono-czarne, a potem przeczytaj jeszcze raz tego posta.

No tak, jasne ze tak ma być, wybacz mi za to głupstwo co napisałem :) Tak jak wspomniałeś, zacząłem mylić rodzica w drzewie i rodzica w sensie pokrewieństwa, dzięki za nakierowanie mnie na dobrą drogę. Teraz myślę, że już sobie poradzę z tym zadankiem. Dzięki! :)

Azarien napisał(a)

Niby wszystko fajnie ale problem pojawia się gdy trzeba wyświetlić członków rodziny dla każdej osoby,
Rodzina to wszystko co jest w dół drzewa (dzieci, wnuki) oraz powiedzmy dwa poziomy w górę (rodzice, dziadki) i wszystko co jest w dół od tych rodziców i dziadków (wujki, kuzyni).

ok, ale nadal nie do końca rozumiem o co chodzi w zadaniu - do czego się przydaje wyświetlanie grafowej "rodziny" przy spisie lokatorów osiedla?

notexists napisał(a)

Azarien napisał(a)

Niby wszystko fajnie ale problem pojawia się gdy trzeba wyświetlić członków rodziny dla każdej osoby,
Rodzina to wszystko co jest w dół drzewa (dzieci, wnuki) oraz powiedzmy dwa poziomy w górę (rodzice, dziadki) i wszystko co jest w dół od tych rodziców i dziadków (wujki, kuzyni).

ok, ale nadal nie do końca rozumiem o co chodzi w zadaniu - do czego się przydaje wyświetlanie grafowej "rodziny" przy spisie lokatorów osiedla?

Wibowit rozwiązał już mój problem, a więc nie rozumiem Twojego posta...

mój post jest powodowany chęcią zrozumienia problemu nawet jeżeli to nie mój problem i został już dawno rozwiązany...
lub mówiąc inaczej ciekawi mnie po co ta rodzina, jeśli relacje ojciec dziecko nie prezentują relacji "więzów krwi"

notexists napisał(a)

mój post jest powodowany chęcią zrozumienia problemu nawet jeżeli to nie mój problem i został już dawno rozwiązany...
lub mówiąc inaczej ciekawi mnie po co ta rodzina, jeśli relacje ojciec dziecko nie prezentują relacji "więzów krwi"

Proszę Cię przeczytaj posty w tym temacie (moje i Wibowita), jak wspomniałem już wcześniej wszystko zostało w nich wyjaśnione w tym mój błędny tok rozumowania.