Pytania otagowane jako search-trees

Pytania dotyczące drzew wyszukiwania, klasy struktur danych używanych do przechowywania posortowanych danych w celu zapewnienia wydajnego dostępu.

4
Dlaczego drzewa czerwono-czarne są tak popularne?
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, przeglądania kilku książek i przeglądania go trochę): Drzewa …
1
Wyobraź sobie czerwono-czarne drzewo. Czy zawsze istnieje sekwencja wstawiania i usuwania, która ją tworzy?
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 czarny. Ścieżka od korzenia do dowolnego liścia NIL zawiera …
2
Nie wszystkie drzewa czerwono-czarne są zrównoważone?
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 wysokościowo iw tym sensie są zrównoważone. Załóżmy, …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
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 określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
1
Dlaczego algorytm rotacji drzewa splay uwzględnia zarówno węzeł nadrzędny, jak i dziadek?
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 do lewego lub prawego poddrzewa. Jeśli wstawimy w lewo, …
1
Drzewa AVL nie są zrównoważone pod względem masy?
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ś takie, że wszystkie wystarczająco duże drzewa AVL są zrównoważone …
1
Bezblokowe, stałe struktury drzew współbieżnych w czasie aktualizacji?
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 przy wdrażaniu struktur danych bez blokowania zastosowano jedną z tych najgorszych technik aktualizacji czasu ?O(1)O(1)\mathcal{O}(1) Pytam, ponieważ; …
2
Pokoloruj drzewo binarne, aby było czerwono-czarnym drzewem
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ęzłami NULL), czy istnieje „szybki” algorytm, który może określić, czy możemy pokolorować (i …
3
Zapamiętywanie bez tablicy
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ą wartość wskazującą, że wpis musi jeszcze zostać wypełniony. Gdy podproblem zostanie napotkany po …
2
Liczba możliwych ścieżek wyszukiwania podczas wyszukiwania w BST
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. Ile jest możliwych różnych zamówień, w których …
2
Mieszanie za pomocą drzew wyszukiwania zamiast list
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 operacji insert, find i delete jest wart. średni przypadek. Czy poprawiają …
3
Jaka struktura danych skutecznie przechowuje zakresy liczb całkowitych?
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 całkowita Moje dane mają tę właściwość, że często zawierają ciągi …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.