Definizione di albero bilanciato

Question

Mi chiedo solo se qualcuno potrebbe essere in grado di chiarire la definizione di un albero equilibrato per me. Ho che "un albero è equilibrato di ogni sottoalbero è bilanciato e l'altezza dei due sotto-alberi differisce di al più uno

Mi scuso se questa è una domanda stupida, ma questa definizione si applica ad ogni nodo fino alle foglie di un albero o solo ai sottoalberi sinistro e destro immediatamente al di fuori della radice? Suppongo che un altro modo di chiedere questo sarebbe chiedere se è possibile che i nodi interni di un albero siano sbilanciati e tutto l'albero rimane bilanciato?

Answer 1

non c'è alcuna differenza tra queste due cose. Pensateci.

Diamo una definizione più semplice, "un numero positivo è anche se è zero o quel numero meno due è ancora ". Questo dice 8 è anche se 6 è pari? O questo dice che 8 è anche se 6, 4, 2 e 0 sono pari?

Non c'è differenza. Se dice 8 è anche se 6 è pari, dice anche 6 è anche se 4 è pari. E quindi dice anche che 4 è anche se 2 è pari. E quindi dice che 2 è anche se 0 è pari. Quindi se dice 8 è anche se 6 è pari, esso (indirettamente) dice 8 è anche se 6, 4, 2 e 0 sono pari.

È la stessa cosa qui. Qualsiasi sotto-albero indiretto può essere trovato da una catena di sotto-alberi diretti. Quindi, anche se si applica solo direttamente ai sotto-alberi diretti, si applica ancora indirettamente a tutti i sotto-alberi (e quindi a tutti i nodi).

Answer 2

Il vincolo viene generalmente applicato in modo ricorsivo a ogni sottostruttura. Cioè, l'albero è bilanciato solo se:

1. altezze sottoalberi sinistro e destro differiscono al massimo di uno, e
2. Il sottoalbero sinistro è equilibrato, E
3. Il sottoalbero destro è equilibrato

In base a questo, l'albero successivo è equilibrata:

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

il prossimo è non bilanciato perché sottoalberi di C differiscono di 2 nella loro altezza:

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

Ciò detto, il vincolo specifico del primo punto dipende dal tipo di albero. Quello sopra elencato è il tipico per AVL trees.

Red-black trees, ad esempio, imporre un vincolo più morbido.

Answer 3

Ci sono diversi modi per definire "Balanced". L'obiettivo principale è mantenere le profondità di tutti i nodi da O(log(n)).

Mi sembra che la condizione di equilibrio di cui si parla sia per l'albero .
Ecco la definizione formale della condizione di equilibrio del AVL albero:

Per ogni nodo AVL, l'altezza del suo sottoalbero sinistro differisce di al massimo 1 dall'alto del suo sottoalbero destro.

Domanda successiva, cos'è "altezza"?

Il "altezza" di un nodo in un albero binario è la lunghezza del percorso più lungo da quel nodo a una foglia.

C'è un strano ma comune caso:

persone definiscono l'altezza di un albero vuoto per essere (-1).

Per esempio, figlio sinistro della radice è null:

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

Altri due esempi per determinare:

Sì, A Balanced Albero Esempio:

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

No, Non un albero equilibrato Esempio:

 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)  

Answer 4

Albero bilanciato è un albero la cui altezza è dell'ordine del registro (numero di elementi nell'albero).

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 

La definizione "un albero è bilanciato di ogni sotto-albero è bilanciato e l'altezza dei due sotto-alberi differiscono al massimo di uno" è seguita da alberi AVL.

Poiché gli alberi AVL sono bilanciati ma non tutti gli alberi bilanciati sono alberi AVL, gli alberi bilanciati non mantengono questa definizione e i nodi interni possono essere sbilanciati. Tuttavia, gli alberi AVL richiedono che tutti i nodi interni siano bilanciati.

Answer 5

lo scopo dell'albero equilibrato è di raggiungere la foglia in un minimo di traversal (altezza minima). Il grado dell'albero è il numero di rami meno 1. Un albero bilanciato potrebbe non essere binario.