TreeLinkedList

Dziś kilka słów o mojej prostej strukturze TreeLinkedList.

Jest to prosta drzewiasta struktura, jak sama nazwa wskazuje można ją sobie wyobrazić jako skrzyżowanie drzewa z listą, a dokładniej to hierarchiczne powiązanie drzewem kilku list, gdzie każda gałąź jest listą elementów, które są kolejnymi gałęziami.

Twór ten jest bardzo zbliżony do B-tree, aczkolwiek nie posiada wszystkich cech tego typu drzew, jedynie strukturalne podobieństwo.

Najprościej byłoby przedstawić ideę graficznie, ale niestety moje predyspozycje graficzne oraz chęci są nikłe.

Struktura ta wykorzystywana jest w projekcie xime, w implementacji listy kontaktów, wszystkie elementy listy przechowywanej są w takim drzewie. Sekcje są dziećmi korzenia i zawarte w liście, dalej każda sekcja jest ojcem listy grup, które następnie przechowują już poszczególne kontakty lub multikontakty, czyli jakby mini grupy kontaktów.

Ze względów optymalizacyjnych użyto list jednokierunkowych, ma to swoją małą wadę. Nie można w prosty sposób dostać się do dowolnego dziecka danej gałęzi. Każda gałąź zawiera tylko wskaźnik do rodzica, następnego elementu na danym poziomie oraz pierwszego swojego dziecka. Nie jest to zbyt wielkim problemem.

Kod może okazać się przydatny dla kogoś, wiec tak samo jak to było w przypadku ostatnich klas vectora wskaźników i tablicy dwuwymiarowej, TreeLinkedList dostępne jest na projects.malcom.pl, oczywiście na licencji MIT.

Będę uszczęśliwiony, jeśli komuś kod okaże się przydatny i wykorzysta go w swoim projekcie.

Może już czas, aby uruchomić labs.malcom.pl na jakimś *wiki, tam prezentować i publikować wszelkie kody źródłowe, eksperymenty programistyczne oraz elektroniczne, które mogą być przydatne nie tylko mi, a do “prawdziwych” projektów im jeszcze daleko.