Pytania otagowane jako binary-trees

drzewo, w którym każdy węzeł ma nie więcej niż dwoje dzieci

1
Tabele skrótów a drzewa binarne
Podczas implementacji słownika („Chcę wyszukiwać dane klientów według ich identyfikatorów klienta”), typowymi stosowanymi strukturami danych są tabele skrótów i drzewa wyszukiwania binarnego. Wiem na przykład, że biblioteka STL C ++ implementuje słowniki (nazywają je mapami) przy użyciu (zrównoważonych) drzew wyszukiwania binarnego, a platforma .NET używa tabel mieszania pod maską. Jakie …
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
Liczenie drzew binarnych
(Jestem studentem z pewnym doświadczeniem matematycznym i chciałbym wiedzieć, jak policzyć liczbę określonego rodzaju drzew binarnych). Patrząc na stronę Wikipedii dotyczącą drzew binarnych , zauważyłem to twierdzenie, że liczba zakorzenionych drzew binarnych o rozmiarze będzie katalońską : C_n = \ dfrac {1} {n + 1} {2n \ wybierz n}nnnCn=1n+1(2nn)Cn=1n+1(2nn)C_n = …
1
Dwie definicje zrównoważonych drzew binarnych
Widziałem dwie definicje zrównoważonych drzew binarnych, które wyglądają inaczej dla mnie. Drzewo binarne jest zrównoważone, jeśli dla każdego węzła utrzymuje, że liczba wewnętrznych węzłów w lewym poddrzewie i liczba wewnętrznych węzłów w prawym poddrzewie różnią się co najwyżej o 1. Drzewo binarne jest zrównoważone, jeśli dla dowolnych dwóch liści różnica …
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 …
5
Skuteczna kompresja nieoznakowanych drzew
Rozważ nieoznakowane, ukorzenione drzewa binarne. Możemy skompresować takich drzew: gdy istnieją wskaźniki do poddrzew i T ' z T = T ' (ustne = jak równość strukturalne), możemy zapisać (wlog) T i zastąpić wszystkie wskaźniki do T ' z wskazówki dla T . Zobacz odpowiedź uli na przykład.T.TTT.′T′T'T.= T′T=T′T = …
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 …
2
Udowodnienie, że plik binarny ma
Próbuję udowodnić, że sterty binarne z węzłami mają dokładnie liści, biorąc pod uwagę, że stertę buduje się w następujący sposób:nnn⌈n2⌉⌈n2⌉\left\lceil \frac{n}{2} \right\rceil Każdy nowy węzeł jest wstawiany przez przeskalowanie w górę . Oznacza to, że każdy nowy węzeł musi zostać utworzony przy następnym dostępnym podrzędnym. Rozumiem przez to, że dzieci …
2
Funkcja, która rozprowadza dane wejściowe
Chciałbym wiedzieć, czy istnieje funkcja od liczb n-bitowych do liczb n-bitowych, która ma następujące cechy:ffaf ffaf powinien być bijectywny Zarówno i powinny być obliczalne dość szybkoffaff−1f−1f^{-1} fff powinien zwrócić liczbę, która nie ma znaczącej korelacji z wprowadzonymi danymi. Uzasadnienie jest następujące: Chcę napisać program działający na danych. Niektóre informacje o …
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.