Definicja zrównoważonego drzewa

Zastanawiam się tylko, czy ktoś mógłby wyjaśnić mi definicję zrównoważonego drzewa. Mam, że „drzewo jest zrównoważone, jeśli każde poddrzewo jest zrównoważone, a wysokość dwóch poddrzew różni się co najwyżej o jeden.

Przepraszam, jeśli jest to głupie pytanie, ale czy ta definicja odnosi się do każdego węzła aż do liści drzewa, czy tylko do lewego i prawego poddrzewa bezpośrednio od korzenia? Myślę, że innym sposobem ujęcia tego byłoby, czy możliwe jest, aby wewnętrzne węzły drzewa były niezrównoważone, a całe drzewo pozostało zrównoważone?

Ograniczenie jest zwykle stosowane rekurencyjnie do każdego poddrzewa. Oznacza to, że drzewo jest zrównoważone tylko wtedy, gdy:

1. Wysokości lewego i prawego poddrzewa różnią się co najwyżej o jeden ORAZ
2. Lewe poddrzewo jest zrównoważone AND
3. Odpowiednie poddrzewo jest zrównoważone

Zgodnie z tym, następne drzewo jest zrównoważone:

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

Następną jest nie zrównoważony, ponieważ poddrzew C różnią się w swojej wysokości 2:

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G  

To powiedziawszy, określone ograniczenie pierwszego punktu zależy od rodzaju drzewa. Ten wymieniony powyżej jest typowy dla drzew AVL .

Na przykład czerwono-czarne drzewa nakładają łagodniejsze ograniczenia.

Istnieje kilka sposobów zdefiniowania „Zrównoważonego”. Głównym celem jest zachowanie głębokości wszystkich węzłów O(log(n)).

Wydaje mi się, że stan równowagi, o którym mówiłeś, dotyczy drzewa AVL .
Oto formalna definicja stanu równowagi drzewa AVL :

Dla dowolnego węzła w AVL wysokość jego lewego poddrzewa różni się co najwyżej o 1 od wysokości jego prawego poddrzewa.

Następne pytanie, czym jest „ wysokość ”?

„ Wysokość ” węzła w drzewie binarnym to długość najdłuższej ścieżki od tego węzła do liścia.

Jest jeden dziwny, ale powszechny przypadek:

Ludzie określają wysokość pustego drzewa (-1).

Na przykład lewe dziecko roota to null:

              A  (Height = 2)
           /     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
                    \
                     C (Height = 0)

Jeszcze dwa przykłady do ustalenia:

Tak, przykład zrównoważonego drzewa :

        A (h=3)
     /     \
 B(h=1)     C (h=2)        
/          /   \
D (h=0)  E(h=0)  F (h=1)
               /
              G (h=0)

Nie, przykład nie jest zrównoważonym drzewem :

        A (h=3)
     /     \
 B(h=0)     C (h=2)        <-- Unbalanced: 2-0 =2 > 1
           /   \
        E(h=1)  F (h=0)
        /     \
      H (h=0)   G (h=0)      

Nie ma różnicy między tymi dwoma rzeczami. Pomyśl o tym.

Przyjrzyjmy się prostszej definicji: „Liczba dodatnia jest nawet wtedy, gdy wynosi zero lub ta liczba minus dwa jest parzysta”. Czy to mówi, że 8 jest nawet jeśli 6 jest parzyste? Czy to mówi, że 8 jest nawet jeśli 6, 4, 2 i 0 są parzyste?

Nie ma różnicy. Jeśli mówi, że 8 jest nawet, jeśli 6 jest parzyste, mówi również, że 6 jest nawet, jeśli 4 jest parzyste. I tak też mówi, że 4 jest nawet jeśli 2 jest parzyste. I tak mówi, że 2 jest nawet jeśli 0 jest parzyste. Więc jeśli mówi, że 8 jest nawet jeśli 6 jest parzyste, to (pośrednio) mówi, że 8 jest nawet, jeśli 6, 4, 2 i 0 są parzyste.

Tutaj jest to samo. Każde pośrednie poddrzewo można znaleźć w łańcuchu bezpośrednich poddrzew. Więc nawet jeśli ma zastosowanie tylko bezpośrednio do bezpośrednich poddrzew, nadal ma zastosowanie pośrednio do wszystkich poddrzew (a tym samym do wszystkich węzłów).

Drzewo zrównoważone to drzewo, którego wysokość jest rzędu kłody (liczba elementów w drzewie).

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

Po definicji „drzewo jest zrównoważone, każde poddrzewo jest zrównoważone, a wysokość dwóch poddrzew różni się co najwyżej o jeden”, po której następują drzewa AVL.

Ponieważ drzewa AVL są zrównoważone, ale nie wszystkie drzewa zrównoważone są drzewami AVL, drzewa zrównoważone nie mają tej definicji, a węzły wewnętrzne mogą być w nich niezrównoważone. Jednak drzewa AVL wymagają zrównoważenia wszystkich węzłów wewnętrznych.

Celem wyważonego drzewa jest dosięgnięcie liścia w minimalnym przejściu (minimalna wysokość). Stopień drzewa to liczba gałęzi minus 1. Zrównoważone drzewo może nie być binarne.

1. Wysokość węzła w drzewie to długość najdłuższej ścieżki od tego węzła w dół do liścia, licząca zarówno początkowy, jak i końcowy wierzchołek ścieżki.
2. Węzeł w drzewie jest zrównoważony wysokością, jeśli wysokość jego poddrzew różni się nie więcej niż o 1.
3. Drzewo jest zrównoważone wysokością, jeśli wszystkie jego węzły są zrównoważone wysokością.