Cześć. Chciałbym zaimplementować drzewo w którym będę przechowywał strumienie IP i korespondujący z nimi numer sesji. Każdy strumień jest dokładnie opisywany przez 4 parametry (początkowy i końcowy port i adres IP). Aby było to efektywne chciałem to zrealizować używając drzewa jednak nie wiem jak podejść do problemu drzewa, w którym kluczem są 4 wartości a nie jedna (chciałbym na podstawie portów i adresów znajdować numer sesji).
Wielkie dzięki za pomoc
0
0
Drzewo jest indeksem dla tablicy. Skoro chcesz mieć tablicę i 4 indeksy to stwórz 4 drzewa.
0
Czyli elementem jest dwuwymiarowy przedział (IP od...do oraz port od..do) i chcesz wyszukiwać wszystkie przedziały do których należy zadany punkt (zadane IP+port)?
Skoro tak to użyj drzewa przedziałowego (interval tree).
Jeśli przedziały IP nie będą się zbytnio zazębiać to można uprościć sytuację i użyć jednowymiarowego drzewa. Niech kluczem (przedziałem) będzie tylko IP. Wtedy wyszukasz w tym drzewie wszystkie przedziały IP zawierające zadany punkt i dla każdego z nich sprawdzisz, czy port również mieści się w przedziale. Możesz również wyszukiwać przedziały z pominięciem portu.
Sytuację można odwrócić - indeksować wyłącznie po numerze portu. Wtedy będziesz miał możliwość wyszukiwania po samym porcie z pomięciem IP.
Możesz też użyć dwuwymiarowego drzewa przedziałowego (k-d tree) aby przyspieszyć zarówno szukanie po samym IP jak i szukanie po samym numerze portu. Z tym, że implementacja będzie dość skomplikowana.
Co należy wybrać zależy od charakterystyki danych (jak bardzo przedziały będą się zazębiać i ile ich będzie) oraz od sposobu w jaki chcesz szukać dane (czy po pełnej parze IP+port, czy tez po samym IP, czy po samym numerze portu).