Własności implikujące zbalansowanie BST

Hej, mam za zadanie sprawdzić które z poniższych własności implikują zbalansowanie drzewa.

1. Każdy węzeł ma dwóch synów lub jest liściem.
2. Rozmiar każdego poddrzewa można zapisać jako 2k - 1, gdzie k jest liczbą naturalną (oczywiście dla każdego poddrzewa k może być inne).
3. Istnieje C > 0 takie, że dla każdego wierzchołka x jego większe poddrzewo ma co najwyżej C razy więcej wierzchołków od jego mniejszego poddrzewa.
4. Istnieje c >0 takie, że dla każdego wierzchołka x wysokość jego poddrzew różni się najwyżej o c.

Dla 1. i 2. znalazłem kontrprzykład:

Dla 3. nie mam pomysłu, a 4. wydaje mi się że będzie implikować zbalansowanie, ale nie wiem jak to udowodnić.
Z góry dzięki za pomoc :)

Twój graf jest jednocześnie kontrprzykładem dla 3. i 4. — istnieją dla tego drzewa takie C czy c, równe miliard (mniejsze też istnieją, ale to Cię nieszczególnie obchodzi), a samo drzewo jest niezbalansowane.

A jaka jest twoja definicja zbalansowania? Dla AVL przyjmuje się zwykle że poddrzewa nie mogą się różnić o więcej niż 1. W przypadku dowolnego c>0 możesz ustalić to c dowolnie duże.

Shalom napisał(a):

A jaka jest twoja definicja zbalansowania? Dla AVL przyjmuje się zwykle że poddrzewa nie mogą się różnić o więcej niż 1. W przypadku dowolnego c>0 możesz ustalić to c dowolnie duże.

W zadaniu jest podana taka definicja:
Drzewo jest zbalansowane, jeśli ma wysokość logarytmiczną względem liczby wierzchołków.

EDIT:
Czy przy takiej definicji też wystarczy ustalić odpowiednio duże c/C ?

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.

1. 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.

@Shalom Przecież ta definicja zbalansowania to jest z czapy. Nie jest nawet wyspecyfikowana podstawa logarytmu. Moim zdaniem jedyna sensowna interpretacja tego pojęcia, to sup(wysokość(d) : d jest drzewem o n wierzchołkach) = O(log n), wtedy można łatwo pokazać, że punkty 3 i 4 są spełnione.

enedil napisał(a):

@Shalom Przecież ta definicja zbalansowania to jest z czapy. Nie jest nawet wyspecyfikowana podstawa logarytmu.

W notacji dużego O i jej podobnych podstawa logarytmu ginie w stałym współczynniku, więc taka definicja jest jak najbardziej ok.