[Algorytmy] Drzewa AVL i RB - wysokosci

[BigPaws]

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)

[Afish]

A co to jest 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".

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]

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.

[Afish]

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.

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 naiwnie rand do testów, więc masz nierównomierny rozkład.

[BigPaws]

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.

[Afish]

Problem ten można rozwiązać na przykład przez przechowywanie w węzłach drzewa list zawierających elementy o identycznych kluczach.

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.

Jeżeli uwzględniłbyś liczby elementów lub tworzył unikalne klucze dla tych samych wartości, to wtedy dałoby się coś powiedzieć.