Napisaem sobie programik do sprawdyania wysokości drzew AVL i RB. Prosiłbym o sprawdzenie (a raczej poinformowanie mnie) czy takie wyniki są możliwe i wszystko z moim kodem i rozumowaniem w porządku.
Pierwszy wykres to zawsze tablica wypełniona liczbami od 0 do rand(), zawierająca w sobie od 10 do 1000 elementów.
Drugi to zawsze te same ilości elementów w tablicy, jednakże tym razem losowane z zakresu 0-9.
W obu przypadkach zawsze dokonałem 5 prób i wyciągałem średnią długość drzew.
O ile w drzewie AVL jestem bardziej pewien odpowiedzi tak drzewo RB sprawiało mi zagwozdkę oraz duża losowość wyników nie pozwala mi wyciągnąć dobrych wniosków jak się mają długości z takimi tablicami do siebie. Można zauważyć, że całkowicie losowe elementy mają nieznacznie mniejszą długość.
W drzewie AVL można zauważyć, że długość zawsze wyniosła 4, ponieważ doszedłem do wniosku, że gdyby rodzic i dwoje dzieci miały tę samą liczbę to żadne kombinacje by tego drzewa poprawnie nie zbalansowały i drzewo złamałoby swoją regułę, dlatego duplikaty po prostu "napisywałem". Jeśli się mylę, prosze mi to wytknąć.
Oto zdjęcia wykresów:
(wstawiam w ten sposób, bo przepisowe embedowane 500 pikseli to za mało)
[Algorytmy] Drzewa AVL i RB - wysokosci
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Drzewa AVL i RB - wysokosci
A co to jest długość?
Nie zrozumiałem, co tu zrobiłeś, ale jakiekolwiek usuwanie duplikatów nie brzmi poprawnie, w końcu dlaczego drzewo nie mogłoby ich mieć? I jeżeli nie jest w stanie się zbalansować wtedy, to jest średnio użyteczne.BigPaws pisze:W drzewie AVL można zauważyć, że długość zawsze wyniosła 4, ponieważ doszedłem do wniosku, że gdyby rodzic i dwoje dzieci miały tę samą liczbę to żadne kombinacje by tego drzewa poprawnie nie zbalansowały i drzewo złamałoby swoją regułę, dlatego duplikaty po prostu "napisywałem".
-
- Użytkownik
- Posty: 75
- Rejestracja: 7 lis 2016, o 15:38
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 10 razy
Re: [Algorytmy] Drzewa AVL i RB - wysokosci
Długość - wysokość.
Duplikatów nie usunąłem, drzewo posiada dodatkową właściwość ile razy dana liczba się pojawiła. Jeśli rodzic i dzieci wszyscy założmy byliby liczbą 4, to złamałbym zasadą, że z lewej strony liczba jest mniejsza a z prawej większa, dlatego rozwiązałem to w ten sposób.
Duplikatów nie usunąłem, drzewo posiada dodatkową właściwość ile razy dana liczba się pojawiła. Jeśli rodzic i dzieci wszyscy założmy byliby liczbą 4, to złamałbym zasadą, że z lewej strony liczba jest mniejsza a z prawej większa, dlatego rozwiązałem to w ten sposób.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Re: [Algorytmy] Drzewa AVL i RB - wysokosci
Dość nietypowa zasada. Nie wiem, czy to przypadek, ale stosujesz inne słownictwo od powszechnie przyjętego, inną definicję drzewa BST, to i wyniki mogą być inne. Do tego używasz naiwnieBigPaws pisze:Jeśli rodzic i dzieci wszyscy założmy byliby liczbą 4, to złamałbym zasadą, że z lewej strony liczba jest mniejsza a z prawej większa, dlatego rozwiązałem to w ten sposób.
rand
do testów, więc masz nierównomierny rozkład.-
- Użytkownik
- Posty: 75
- Rejestracja: 7 lis 2016, o 15:38
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 10 razy
Re: [Algorytmy] Drzewa AVL i RB - wysokosci
Na terminologii czy składaniu zdań poległem wczoraj przez niewyspanie, jednak mój wniosek potwierdziła wikipedia jak teraz wznowiłem research. Zacytuję:
"Podobnie jak w BST, nie jest możliwe, by drzewo posiadało dwa równe elementy. Zazwyczaj oznacza to, iż elementy muszą posiadać unikatowy klucz identyfikacyjny; problem polega na tym, że drzewa z równymi elementami – nawet po zmodyfikowaniu porządku dzielącego elementy do lewych i prawych poddrzew – nie da się później zrównoważyć. Problem ten można rozwiązać na przykład przez przechowywanie w węzłach drzewa list zawierających elementy o identycznych kluczach."
Korzystam z rand, bo takie były wytyczne, sam bym wolał pracować ze stałymi liczbami, no ale nie ja podejmuje takie decyzje.
"Podobnie jak w BST, nie jest możliwe, by drzewo posiadało dwa równe elementy. Zazwyczaj oznacza to, iż elementy muszą posiadać unikatowy klucz identyfikacyjny; problem polega na tym, że drzewa z równymi elementami – nawet po zmodyfikowaniu porządku dzielącego elementy do lewych i prawych poddrzew – nie da się później zrównoważyć. Problem ten można rozwiązać na przykład przez przechowywanie w węzłach drzewa list zawierających elementy o identycznych kluczach."
Korzystam z rand, bo takie były wytyczne, sam bym wolał pracować ze stałymi liczbami, no ale nie ja podejmuje takie decyzje.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Re: [Algorytmy] Drzewa AVL i RB - wysokosci
Co jest zupełnie inne, niż „nadpisywanie” elementów. Jeżeli teraz masz liczby mniejsze do dziesięciu, to nie da się nic wywnioskować, bo praktycznie zawsze powinieneś otrzymać to samo drzewo.BigPaws pisze:Problem ten można rozwiązać na przykład przez przechowywanie w węzłach drzewa list zawierających elementy o identycznych kluczach.
Jeżeli uwzględniłbyś liczby elementów lub tworzył unikalne klucze dla tych samych wartości, to wtedy dałoby się coś powiedzieć.