Witam,
Chcialbym oprgoramować małą bazedanych. W bazie każdy rekord będzie posiadał swój unikalny nr ID z akresu od 0 do n, jednak numery nie będa nadawane "po kolei", tylko w sposob losowy.
Zastanawiam się jakiej struktury danych użyć aby to złożoność obliczeniowa dodania, usuniecia, odnalezienia rekordu była możliwie mała. Oto ewolucja mojego toku myślenia:
- Zrobic tablice poortowana względem ID, aby wyszukać rekord o danym ID, można zastosować przeszukiwanie binarne. Jednak aby wstawić/usunąć rekord tak aby tablica byla wciąż posortowana, w najabrdziej presymistyczny przypadku musimy przesunąć cała istniejąca tablice - dlatego takie rozwiązanie odpada.
- Natomiast w przypadku listy, dodawanie/usuwanie rekordu jest już mniej koszotwne, natomiast nie możemy zastosować przeszukiwania binarnego, tylko musimy przejsc cała listę - co daje kiepską efektywność.
- Domyślam się, że przy użyciu drzewa, można by zrobic jakoś fuzję obywdu powyższych rozwiązań i użyskać złożoność logarytmiczna dla każdej operacji, jedank moja wiedza na temat drzew jest zbyt mała by samemu to zaprojektować.
Był bym wdzięczny, za wskazówki jak rozwiązać ten problem,
Pozdrawiam.