Najlepszy samobalansujący BST do szybkiego wkładania dużej liczby węzłów

głosy
8

Byłem w stanie znaleźć szczegółowe informacje na temat kilku samobalansującego BSTs przez kilka źródeł, ale nie znaleziono żadnych dobre opisy detali, które z nich jest najlepszy do wykorzystania w różnych sytuacjach (lub jeśli to naprawdę nie ma znaczenia).

Chcę BSTto optymalna do przechowywania ponad dziesięć milionów węzłów. Kolejność wstawiania węzłów jest w zasadzie przypadkowy, i nigdy nie będzie konieczne usunięcie węzłów, więc czas wstawiania jest jedyną rzeczą, która musiałaby być zoptymalizowane.

Mam zamiar używać go do przechowywania wcześniej odwiedzonych stanów gry w grze logicznej, tak, że można szybko sprawdzić, czy został już napotkał poprzedniej konfiguracji.

Utwórz 05/08/2008 o 16:40
źródło użytkownik
W innych językach...                            


4 odpowiedzi

głosy
3

Dlaczego używać BSTw ogóle? Z opisem słownik będzie działać równie dobrze, jeśli nie lepiej.

Jedynym powodem, dla użyciem BSTbyłoby gdybyś chciał wymienić całą zawartość pojemnika w celu klucza. To na pewno nie wygląda tak, jak chcesz to zrobić w takim przypadku przejść do tabeli mieszania. O(1)wstawiania i wyszukiwania, bez obawy o usunięcie, co może być lepiej?

Odpowiedział 29/08/2008 o 01:10
źródło użytkownik

głosy
3

Czerwono-czarny jest lepszy niż AVL do zastosowań wstawiania ciężkie. Jeśli przewidują stosunkowo równomierne przeglądowej, następnie Czerwono-czarny jest do zrobienia. Jeśli przewidują stosunkowo niezrównoważony przeglądowej gdzie ostatnio oglądane elementy są bardziej prawdopodobne, aby być oglądane znowu chcesz korzystać drzew splay .

Odpowiedział 05/08/2008 o 16:59
źródło użytkownik

głosy
0

Dwa samobalansujący BSTs jestem najbardziej znane są czerwono-czarno AVL, więc nie mogę powiedzieć na pewno, czy jakieś inne rozwiązania są lepsze, ale o ile pamiętam, czerwono-czarny ma szybsze wprowadzanie i wolniej w porównaniu do pobierania AVL.

Więc jeśli wstawka jest wyższy priorytet niż pobieranie, czerwono-czarny może być lepszym rozwiązaniem.

Odpowiedział 05/08/2008 o 16:50
źródło użytkownik

głosy
-2

[Tablica mieszania mają] O (1) do wprowadzania i przeszukiwanie

Myślę, że to jest złe.

Przede wszystkim, jeśli ograniczyć KEYSPACE być skończona, można przechowywać elementy w tablicy i zrobić O (1) skanowania liniowego. Albo można shufflesort tablicę, a następnie zrobić liniowego skanowania w czasie O (1) przewidywanego czasu. Gdy materiał jest skończony, materiał jest łatwo O (1).

Więc powiedzmy, że tabela hash będzie przechowywać dowolną bitowy ciąg; to nie tyle sprawa, tak długo jak istnieje nieskończona zestaw kluczy, z których każdy jest skończony. Następnie trzeba przeczytać wszystkie bity dowolnego wejścia zapytań i wstawiania innego wstawić y0 w pustym hash i zapytania na Y1, gdzie y0 i y1 różnią się w jednej pozycji bitu, który nie patrzeć.

Ale powiedzmy, że kluczowe odcinki nie są parametrem. Jeśli wstawiania i wyszukiwania wziąć O (1), w szczególności mieszaja zajmuje O (1) czasu, co oznacza, że tylko patrzeć skończonej ilości wyjściu z funkcji skrótu (od którego istnieje prawdopodobieństwo być tylko wyjście skończony, udzielonego ).

Oznacza to, że z skończenie wiele wiader, musi być nieskończony zbiór ciągów, które wszystkie mają taką samą wartość skrótu. Załóżmy, że mam włożyć dużo, czyli ω (1), od tych, i rozpocząć tworzenie kwerend. Oznacza to, że tabela hash musi spaść z powrotem na innej O (1) mechanizm wstawiania / wyszukiwania, aby odpowiedzieć na moje pytania. Który z nich i dlaczego nie wystarczy użyć bezpośrednio?

Odpowiedział 01/02/2009 o 13:49
źródło użytkownik

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more