Jaka jest optymalna struktura danych dla drzewa map.

Szukam struktury danych, która jest w zasadzie drzewem map, w których mapa w każdym węźle zawiera nowe elementy, a także elementy w mapie jego węzła nadrzędnego. Przez mapę rozumiem tutaj mapę programowania z kluczami i wartościami, taką jak mapa w STL lub dict w python.

Na przykład może istnieć węzeł główny:

root = {'car':1, 'boat':2}

i 2 dzieci, z których każde dodaje element do mapy nadrzędnej

child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}

Chciałbym, aby było to jak najbardziej efektywne pod względem przestrzeni, tj. Nie chcę przechowywać pełnej kopii wynikowej mapy w każdym węźle, ale idealnie byłoby to wyszukiwanie O (log N), gdzie N jest całkowitą liczbą elementy w węźle, a nie całe drzewo.

Pomyślałem, że może jest do tego inteligentna funkcja skrótu, ale nic nie mogłem wymyślić.

Naiwnym podejściem byłoby przechowywanie nowo dodanych wpisów na mapie w każdym węźle, a następnie przejście w górę drzewa, jeśli nic nie zostanie znalezione. Nie podoba mi się to, ponieważ zależy to od głębokości drzewa.

Nie powiedziałeś, jakie są zapytania, ale przyjmuję, że zapytanie () pobiera węzeł i klucz i chce powiązanej wartości (lub zerowej, jeśli taka wartość nie istnieje). W tym przypadku myślę, że ogólnie rzecz biorąc nie można zrobić nic lepszego niż przechowywanie oddzielnej mapy w każdym węźle. Rozważmy na przykład drzewo gąsienicy, w którym każdy węzeł ścieżki jest połączony z jednym węzłem, który jest rozwidlony (w sumie 2n węzłów). Zrootuj go na jednym końcu ścieżki. Załóżmy teraz, że rozmiar wszechświata dla kluczy wynosi m. Dla każdego rozwidlonego węzła v i każdego z m możliwych kluczy ten klucz może albo istnieć, albo nie istnieć w v, i oba byłyby zgodne z twoim ograniczeniem poddrzewa. Więc tutaj są$2^{mn}$ możliwości określania, czy każdy klucz istnieje w każdym węźle rozwidlenia, dlatego potrzebujesz wielu bitów miejsca tylko do przechowywania wymaganych informacji.

Przede wszystkim myślę, że to, co rozumiesz przez „mapę”, jest „słownikiem” w żargonie TCS. Po drugie, nie rozumiem wyrażenia „idealnie byłoby to wyszukiwanie$O(\log N)$", ponieważ w słowniku wyszukiwanie zajmuje O (1) przy różnych tabelach skrótów. Po trzecie, nie określiłeś, czy problem jest statyczny czy dynamiczny; zakładam, że jest statyczny.

Optymalna złożoność tego problemu to $\Theta($wyszukiwanie poprzedników), np $O(\lg\lg N)$za pomocą van Emde Boasa. Jest to optymalne, jeśli rozmiar słowa to$\Theta(\lg n)$; zobacz http://people.csail.mit.edu/mip/papers/pred/pred.pdf, aby uzyskać optymalne granice dla poprzedników.

Właściwym sposobem na zaatakowanie problemu jest zbudowanie jednej globalnej tabeli mieszającej i oddzielne zarządzanie hierarchią dla każdego klucza w tabeli. Dla jednego klucza$x$, znamy węzły, w których się pojawia. Rozważ przemierzanie drzewa w kolejności. Węzły gdzie$x$pojawia się zdefiniuj interwały w tej kolejności. Aby ustalić, czy$x$ znajduje się w tabeli skrótów jakiegoś węzła $v$, musisz zapytać, czy $v$dźgnie dowolny segment, jak zdefiniowano powyżej. Można to łatwo zrobić za pomocą wyszukiwania poprzedników, w którym budujemy tabelę poprzedników dla wszystkich punktów końcowych przedziału.

Jeśli chodzi o dolną granicę, zwróć uwagę, że nawet jedno pytanie kłute jest tak samo trudne jak poprzednik (patrz redukcje z kolorowego wyszukiwania poprzednika). Ponieważ powyższe odniesienia do papieru pokazują optymalne zachowanie sumy bezpośredniej dla wyszukiwania poprzedników, oznacza to, że algorytm opisany powyżej jest optymalny dla dowolnej proporcji między liczbą węzłów a całkowitą liczbą kluczy.