Perché è importante che un albero binario essere equilibrato?

Question

Perché è importante che un albero binario essere bilanciato

Answer 1

Il saldo di un albero binario è regolata dalla proprietà denominata asimmetria. Se un albero è più inclinata e la complessità temporale per accedere a un elemento di una i binari aumenta albero. Dire un albero

   1 
      /\ 
       2 3 
       \ \ 
       7 4 
        \ 
         5 
         \ 
         6 

Quanto sopra è anche un albero binario, ma proprio distorta. Ha 7 elementi, quindi un albero binario ideale richiede O (log 7) = 3 ricerche. Ma nel caso peggiore devi andare a un livello più profondo = 4 ricerche. Quindi l'asimmetria qui è una costante 1. Ma considera se l'albero ha migliaia di nodi. In questo caso, l'asimmetria sarà ancora più considerevole. Quindi è importante mantenere l'albero binario bilanciato.

Ma ancora una volta l'asimmetria è l'argomento del dibattito poiché l'analisi probabilistica di un albero binario casuale mostra che la profondità media di un random binary tree with n elements is 4.3 log n. Quindi è davvero questione di bilanciamento rispetto all'asimmetria.

più Una cosa interessante, gli informatici hanno anche trovato un vantaggio nella asimmetria e ha proposto un datastructure distorta chiamato skew heap

Answer 2

Immaginate un albero che assomiglia a questo:

A 
    \ 
    B 
    \ 
     C 
     \ 
     D 
     \ 
      E 

Questo è un albero binario valida, ma ora la maggior parte delle operazioni sono O (n) invece di O (lg n).

Answer 3

per garantire un tempo di log (n) di ricerca, è necessario dividere il numero totale di nodi di livello inferiore da 2 a ogni ramo. Ad esempio, se si dispone di un albero lineare, mai ramificazione dalla radice al nodo foglia, allora il tempo di ricerca sarà lineare come in una lista collegata.

Answer 4

Un albero estremamente sbilanciato, ad esempio un albero in cui tutti i nodi sono collegati a sinistra, significa che si continua a cercare in ogni singolo nodo prima di trovare l'ultimo, che non è affatto il punto di un albero e non ha alcun vantaggio su una lista collegata. Bilanciamento l'albero rende migliori tempi di ricerca O (log (n)) al contrario di O (n).