Jaka jest optymalna struktura danych dla drzewa map.

9

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.

phreeza
źródło
więc każdy węzeł reprezentuje mapę, która uściśla mapę przechowywaną w obiekcie nadrzędnym?
Suresh Venkat
czy masz na myśli mapę w sensie matematycznym czy kartograficznym?
Suresh Venkat
Mam na myśli mapę w sensie matematycznym / CS. Na przykład mapa w STL.
phreeza
@Suresh: Wygląda na to, że nie jest to wyrafinowanie. Jeśli dobrze rozumiem, węzeł potomny dodaje nowe elementy do mapy swojego węzła macierzystego.
Jukka Suomela,
i aby odpowiedzieć na pierwsze pytanie, każdy węzeł udoskonala mapę w tym sensie, że dodaje się więcej par klucz / wartość.
phreeza

Odpowiedzi:

10

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ą2mn 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.

Jelani Nelson
źródło
5
Ale ten przykład nie pokazuje, że musisz przechowywać zbędne informacje (tj. Że musisz zduplikować wpisy węzła głównego również w każdym dziecku)!
Jukka Suomela,
Jestem zmieszany. W drzewie głębokości1 z n węzły jasne jest, że nie można przechowywać m wiązania w o(m)przestrzeń. Czy twój przykład pokazuje coś więcej?
Radu GRIGore,
15

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 gdziexpojawia 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 vdź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.

Mihai
źródło