No to widać że 3 i 4 nijak nie implikują tej twojej własnosci.
3. Załóżmy że to prawda, mamy więc pewne c
takie że wysokość jednego poddrzewa jest c
razy większa niż drugiego. Rozważmy dwa przypadki
a) drzewo pełne -> wiemy że takie drzewo będzie miało 2^h
wierzchołków, więc nasze drzewo ma węzłów 2^h+2^(h*c)
. Już samo log2(2^(h*c)) = h*c
, więc jeśli dodamy tam jeszcze cokolwiek to ten logarytm będzie większy niż h*c
, więc faktycznie własność byłaby spełniona, chociaż tak ledwo co i nie trudno zauważyć że w miarę zmniejszania liczby węzłów, będzie gorzej.
b) drzewo gdzie każdy poziom ma tylko jedno dziecko -> wiemy, że teraz jedno poddrzewo ma h
wierzchołków a drugie h*c
, w sumie mamy h*(c+1)
węzłów. Nie trzeba złożonej matematyki żeby widzieć, że log2(h*(c+2)) < h*c
więc nasze drzewo zbalansowane nie jest.
- Załóżmy znów że to prawda, mamy wiec pewne
c
takie ze wysokość jednego poddrzewa jest o c
większa niż drugiego. Znów weźmy dwa skrajne przypadki:
a) drzewo pełne -> wiemy że takie drzewo będzie miało 2^h
wierzchołków, więc nasze drzewo ma węzłów 2^h + 2^(h+c) = 2^h(1+2^c)
. Weźmy z tego logarytm log2(2^h(1+2^c)) = log2(2^h) + log2(1+2^c) > h + c
, a wysokość naszego drzewa to h+c
więc własność jest spełniona, chociaż tak ledwo co i znów widać że jak liczba wierzchołków spadnie, to zaraz sie popsuje.
b) drzewo gdzie każdy poziom ma tylko jedno dziecko -> wiemy, że teraz jedno poddrzewo ma h
wierzchołków a drugie h+c
, w sumie mamy 2h+c
węzłów. Znowu bierzemy log2(2*h+c) < log2(2*(h+c)) < log2(2) + log2(h+c) < h+c
więc nasze drzewo zbalansowane nie jest.