I gdzie tu jest szybkość drzewa binarnego?

0

Witam! Zastanawiam się gdzie tu jest szybkość drzew binarnych. Drzewa te podobno działają tak, że podczas przechodzenia przez nie, skraca się je o połowę. Ale co w przypadku haseł? Załóżmy, że mam sobie jakieś tam drzewo z rozszerzeniami plików (jest ich w 3.) i wartością jest rozszerzenie a wewnętrzną wartością (?) jest opis rozszerzenia. I gdzie tu teraz jest szybkość drzewa binarnego? Skoro są to łańcuchy (te rozszerzenia), to nie można ich jakoś po numerować jako id, a podczas porównywania stringów nie można tego jakoś skracać o połowę... Wie ktoś może jak takie coś rozwiązać? Czy byłoby tu przydatne np. zrobić tablicę stringów z tymi rozszerzeniami i index odpowiada id. I na podstawie ID szukać w drzewie binarnym? Jak by to można było rozwiązać, bo potrzebuję...

0

Drzewa te podobno działają tak, że podczas przechodzenia przez nie, skraca się je o połowę.

Kę?

W zrównoważonym drzewie poszukiwań binarnych poddrzewa mają rozmiar tego samego rzędu (czyli np różnica w rozmiarze wynosi poniżej 2x). Przechodząc o jeden poziom w dół zmniejszamy obszar poszukiwań mniej więcej o połowę.

Typowa TreeMapa jest zaimplementowana jako: https://pl.wikipedia.org/wiki/Drzewo_czerwono-czarne

0

Akurat w celu przechowywania / szybkiego dostępu do stringów lepiej sprawdzają się drzewa w stylu https://pl.wikipedia.org/wiki/Skompresowane_drzewo_trie

Skoro są to łańcuchy (te rozszerzenia), to nie można ich jakoś po numerować jako id

Ano można - nazywa się to https://pl.wikipedia.org/wiki/Tablica_mieszaj%C4%85ca, natomiast to inny temat niż drzewa binarne :-)

1 użytkowników online, w tym zalogowanych: 0, gości: 1