Pytania dotyczące drzew wyszukiwania, klasy struktur danych używanych do przechowywania posortowanych danych w celu zapewnienia wydajnego dostępu.
Wygląda na to, że gdziekolwiek spojrzę, struktury danych są wdrażane przy użyciu czerwono-czarnych drzew ( std::setw C ++, SortedDictionaryw C # itp.) Właśnie omawiając (a, b), czerwono-czarne i drzewa AVL w mojej klasie algorytmów, oto co wyciągnąłem (również z pytania po profesorach,...
Załóżmy następującą definicję drzewa czerwono-czarnego: Jest to drzewo wyszukiwania binarnego. Każdy węzeł ma kolor czerwony lub czarny. Korzeń jest czarny. Dwa węzły połączone krawędzią nie mogą być jednocześnie czerwone. Oto dobra definicja liścia NIL, jak na wiki. Liść NIL ma kolor...
Intuicyjnie „zrównoważone drzewa” powinny być drzewami, w których lewe i prawe podgrzewa w każdym węźle muszą mieć „w przybliżeniu taką samą” liczbę węzłów. Oczywiście, gdy mówimy o zrównoważeniu czerwono-czarnych drzew * (patrz definicja na końcu), faktycznie mamy na myśli, że są one zrównoważone...
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void...
Nie do końca rozumiem, dlaczego rotacja w strukturze danych drzewa splay uwzględnia nie tylko element nadrzędny węzła oceniającego, ale także dziadka (operacja zygzak i zig-zig). Dlaczego następujące elementy nie działają: Gdy wstawiamy na przykład nowy węzeł do drzewa, sprawdzamy, czy wstawiamy...
W poprzednim pytaniu była definicja drzew zrównoważonych pod względem masy i pytanie dotyczące drzew czerwono-czarnych. To pytanie dotyczy tego samego pytania, ale dotyczy drzew AVL . Pytanie brzmi, biorąc pod uwagę definicję drzew zrównoważonych jak w drugim pytaniu,μμ\mu Czy jest jakieś...
Mam zadanie, w którym muszę skorzystać z drzewa wyszukiwania binarnego i zmienić je, aby samo uporządkować się tak, aby elementy, do których najczęściej uzyskiwano dostęp (mają wyższy priorytet), znajdowały się na szczycie drzewa, przy czym węzeł główny był najczęściej dostępnym węzłem . Profesor...
Ostatnio czytałem trochę literatury i znalazłem dość interesujące struktury danych. Badałem różne metody skrócenia czasów aktualizacji do najgorszego przypadku [1-7].O(1)O(1)\mathcal{O}(1) Ostatnio zacząłem szukać struktur danych bez blokowania, aby wspierać efektywny równoczesny dostęp. Czy...
Częstym pytaniem w rozmowie kwalifikacyjnej jest podanie algorytmu określającego, czy dane drzewo binarne ma zrównoważoną wysokość (definicja drzewa AVL). Zastanawiałem się, czy możemy zrobić coś podobnego z czerwono-czarnymi drzewami. Biorąc pod uwagę dowolne bezbarwne drzewo binarne (z...
W Cormen et al .'s Wprowadzenie do algorytmów , sekcja 15.3 Elementy programowania dynamicznego wyjaśniają zapamiętywanie w następujący sposób: Zapamiętany algorytm rekurencyjny zachowuje pozycję w tabeli dla rozwiązania każdego podproblemu. Każdy wpis w tabeli początkowo zawiera specjalną...
Mam następujące pytanie, ale nie mam na to odpowiedzi. Byłbym wdzięczny, jeśli moja metoda jest poprawna: P: Podczas wyszukiwania wartości klucza 60 w drzewie wyszukiwania binarnego węzły zawierające wartości klucza 10, 20, 40, 50, 70, 80, 90 są przemieszczane, niekoniecznie w podanej kolejności....
Walczę z haszowaniem i materiałem do wyszukiwania binarnego. Przeczytałem, że zamiast używać list do przechowywania wpisów z tymi samymi wartościami skrótu, możliwe jest również użycie drzew wyszukiwania binarnego. I staram się zrozumieć, jaki jest najgorszy i średni przypadek wykonania...
To pytanie w zasadzie wyjaśnia, że mogą, ale nie pokazuje żadnych przykładów istnienia dwóch różnych drzew z tym samym przejściem w przedsprzedaży. Wspomniano również, że przechodzenie w kolejności dwóch różnych drzew może być takie samo, chociaż są one strukturalnie różne. Czy jest na to...
Muszę przechowywać kolekcję liczb całkowitych z zakresu od 0 do 65535, aby móc szybko wykonać następujące czynności: Wstaw nową liczbę całkowitą Wstaw zakres ciągłych liczb całkowitych Usuń liczbę całkowitą Usuń wszystkie liczby całkowite poniżej liczby całkowitej Sprawdź, czy występuje liczba...
Próbuję zrozumieć, w jaki sposób drzewa indeksowane binarnie (drzewa fenwick) można modyfikować w celu obsługi zapytań o zakres i aktualizacji zakresu. Znalazłem następujące źródła: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
Rozumiem, że drzewa segmentów można wykorzystać do znalezienia sumy podgrupy ZAAA. I to można zrobić wO (logn )O(logn)\mathcal{O}(\log n)czas zgodnie z tutorialem tutaj . Jednak nie jestem w stanie udowodnić, że czas na zapytanie jest rzeczywiście O (logn )O(logn)\mathcal{O}(\log n). Ten link (i...
Jak udowodnić, że oczekiwana wysokość losowo zbudowanego drzewa wyszukiwania binarnego z węzłami wynosi ? Istnieje dowód we CLRS Wstęp do algorytmów (rozdział 12.4), ale ja go nie rozumiem.nnnO(logn)O(logn)O(\log
SkipList zapewnia to samo O(logn)O(logn)O(\log n)ogranicza wyszukiwanie jako drzewo zrównoważone z tą zaletą, że ponowne zbalansowanie nie jest konieczne. Ponieważ SkipList jest konstruowany przy użyciu losowych rzutów monetą, granice te obowiązują tylko tak długo, jak długo struktura SkipList...
Czy w rzeczywistych aplikacjach jest konkretna korzyść z używania algorytmów zamiast algorytmów ?O (log( log( n ) )O(log(log(n))\mathcal{O}(\log(\log(n))O (log( n ) )O(log(n))\mathcal{O}(\log(n)) Dzieje się tak, gdy na przykład używa się drzew van Emde Boasa zamiast bardziej tradycyjnych...