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.
źródło
Odpowiedzi:
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)m n 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.
źródło
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 wyszukiwanieO(logN) ", 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Θ( wyszukiwanie poprzedników), np O(lglgN) za pomocą van Emde Boasa. Jest to optymalne, jeśli rozmiar słowa toΘ(lgn) ; 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 kluczax , znamy węzły, w których się pojawia. Rozważ przemierzanie drzewa w kolejności. Węzły gdziex pojawia się zdefiniuj interwały w tej kolejności. Aby ustalić, czyx 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.
źródło