Builder.cz - Informacni server o programovani

Odběr fotomagazínu

Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!

 

Zadejte Vaši e-mailovou adresu:

Kamarád fotí rád?

Přihlas ho k odběru fotomagazínu!

 

Zadejte e-mailovou adresu kamaráda:

Zjištění hlouky u stromových struktur?

Seznam témat     Nová odpověď

Přihlásit se     Registrace     Zapomenuté heslo

Re: Zjištění hlouky u stromových struktur?

Autor: kubanis

0:07:16 29.11.2010

Díky za zhodnocení. Ještě to promyslím, ale nejspíše to tedy vyřeším pamatováním rozdílů hloubek mezi pravou a levou větví...

Citovat příspěvek

 

Re: Zjištění hlouky u stromových struktur?

Autor: Maaartin

23:49:44 28.11.2010

> [ital] nepamatovat si přímo hloubku, ale jen rozdíl mezi hloubkami pravé a levé větve.[/ital]

To taky nezni spatne.

> [ital]A pak bych začal u kořene a traverzováním vždy do delší větve si tu hlouku zjistil, ale taky mi to nepřijde moc efektivní...[/ital]

Me celkem jo, pokud je ten strom vyvazeny, tak to nebude tak zly.


> [ital]A řešení histogramem mi nic moc neříká, nemohl bys mi dát nějaký odkaz, kde bych o tom něco našel?[/ital]

Nemohl, bo me to zrovna napadlo. Ale ono by to pri vyvazovani (rotacich atd.) stejne neslo. Bez nej by to bylo jednoduchy, proste si pamatujes, kolik uzlu mas v jaky hloubce, kdyz pridas ci uberes, tak to aktualizujes. Maximalni hloubku najdes hned. Jenomze kdyz vyvazujes, tak zmenis hloubku N uzlu a kdyz N neznas... smula.


Takze bych sel do pamatovani si rozdilu hloubek. Pamatovat si hloubku samotnou totiz quli vyvazovani taky nejde, to jsem prehlidnul. Projet par uzlu trva chvilku, vetsinou to budou furt ty samy, takze budou hezky nacachovany.

Citovat příspěvek

 

Re: Zjištění hlouky u stromových struktur?

Autor: kubanis

22:17:11 28.11.2010

Díky za reakci. A není to pouze přidávání, ale i odebírání...

Taky mě samozřejmě napadlo pamatovat si u každého prvku hloubku podstromu. Například u PrioritySearchTree, kde se při operacích mohou provádět levé či pravé rotace, by asi bylo vhodnější nepamatovat si přímo hloubku, ale jen rozdíl mezi hloubkami pravé a levé větve. V podstatě by to bylo stejné jako u AVL stromu. A pak bych začal u kořene a traverzováním vždy do delší větve si tu hlouku zjistil, ale taky mi to nepřijde moc efektivní...

A řešení histogramem mi nic moc neříká, nemohl bys mi dát nějaký odkaz, kde bych o tom něco našel? Díky

Citovat příspěvek

 

Re: Zjištění hlouky u stromových struktur?

Autor: Maaartin

12:30:55 28.11.2010

To zalezi na operacich, co s tim delas. Kdyz jenom pridavas, tak je to trivka. Jinak bych to asi resil histogramem hloubky, ten aktualizovat by nemel byt problem a najit v nem odpoved taky ne (treba binary search ale nejspis ani netreba). Dalsi moznost by byla pamatovat si u kazdyho uzlu hloubku podstromu, ale to mi prijde zbytecne narocny na pamet.

Citovat příspěvek

 

Zjištění hlouky u stromových struktur?

Autor: kubanis

11:09:20 28.11.2010

Mám naimplementované abstraktní datové struktury pro 2D strom (2D Tree), Quad strom (Quad Tree), Priorití vyhledávací strom (Priority search tree) a Intervalový strom (Range Tree).

Ale teď potřebuji dodělat sledování maximální hlouby pro jednotlivé struktury, aby bylo možné je porovnat i na základě hloubky. Implementačně nejjednoduší by jistě bylo provést prohlídku a při vstupu do potomka zvyšovat nějakou proměnou a tu porovnávat s proměnou globální, kam se uložila maximální dosažená výška při prohlídce...

Ale vzhledem k tomu, že ve struktuře budou tisíce GPS souřadnic a navíc požadavkem sledovat hlouku stále (po každé operaci nad strukturou), moc efektivní by to nebylo.

Jaké byste nevrhovali řešení? Samozřejmě může být řešení pro každou strukturu jiné, pokud by to bylo výhodné. Ale spíš předpokládám, že to bude na stejném principu...

Citovat příspěvek

 

 

 

Přihlášení k mému účtu

Uživatelské jméno:

Heslo: