Introduzione agli alberi

Treeè una struttura discreta che rappresenta le relazioni gerarchiche tra singoli elementi o nodi. Un albero in cui un genitore non ha più di due figli è chiamato albero binario.

Albero e sue proprietà

Definition- Un albero è un grafo non orientato aciclico connesso. Esiste un percorso univoco tra ogni coppia di vertici in $ G $. Un albero con N numero di vertici contiene $ (N-1) $ numero di archi. Il vertice di 0 gradi è chiamato radice dell'albero. Il vertice che è di 1 grado è chiamato nodo foglia dell'albero e il grado di un nodo interno è almeno 2.

Example - Quello che segue è un esempio di albero -

Centri e bicentri di un albero

Il centro di un albero è un vertice con un'eccentricità minima. L'eccentricità di un vertice $ X $ in un albero $ G $ è la distanza massima tra il vertice $ X $ e qualsiasi altro vertice dell'albero. L'eccentricità massima è il diametro dell'albero. Se un albero ha un solo centro, si chiama Albero Centrale e se un albero ha solo più centri, si chiama Albero Bi-centrale. Ogni albero è centrale o bicentrale.

Algoritmo per trovare centri e bi-centri di un albero

Step 1 - Rimuovi tutti i vertici di grado 1 dall'albero dato e rimuovi anche i loro bordi incidenti.

Step 2- Ripetere il passaggio 1 fino a quando non viene lasciato un singolo vertice o due vertici uniti da un bordo. Se viene lasciato un singolo vertice, allora è il centro dell'albero e se due vertici uniti da un bordo vengono lasciati, allora è il bi-centro dell'albero.

Problem 1

Trova il centro / bi-centro del seguente albero -

Solution

All'inizio, rimuoveremo tutti i vertici di grado 1 e rimuoveremo anche i loro bordi incidenti e otterremo il seguente albero:

Ancora una volta, rimuoveremo tutti i vertici di grado 1 e rimuoveremo anche i loro bordi incidenti e otterremo il seguente albero:

Finalmente abbiamo un unico vertice 'c' e fermiamo l'algoritmo. Poiché esiste un singolo vertice, questo albero ha un centro "c" e l'albero è un albero centrale.

Problem 2

Trova il centro / bi-centro del seguente albero -

Solution

All'inizio, rimuoveremo tutti i vertici di grado 1 e rimuoveremo anche i loro bordi incidenti e otterremo il seguente albero:

Ancora una volta, rimuoveremo tutti i vertici di grado 1 e rimuoveremo anche i loro bordi incidenti e otterremo il seguente albero:

Infine, abbiamo due vertici "c" e "d" a sinistra, quindi interrompiamo l'algoritmo. Quando vengono lasciati due vertici uniti da un bordo, questo albero ha "cd" bi-centrale e l'albero è bicentrale.

Alberi etichettati

Definition- Un albero etichettato è un albero ai cui vertici sono assegnati numeri univoci da 1 a n. Possiamo contare a mano tali alberi per piccoli valori di n in modo da ipotizzare una formula generale. Il numero di alberi etichettati di n numero di vertici è $ n ^ {n-2} $. Due alberi etichettati sono isomorfi se i loro grafici sono isomorfi ei punti corrispondenti dei due alberi hanno le stesse etichette.

Esempio

Alberi senza etichetta

Definition- Un albero senza etichetta è un albero ai cui vertici non è assegnato alcun numero. Il numero di alberi etichettati di n numero di vertici è $ \ frac {(2n)!} {(N + 1)! N! } $ (n ° numero catalano)

Esempio

Albero radicato

Un albero con radice $ G $ è un grafo aciclico connesso con un nodo speciale che è chiamato radice dell'albero e ogni bordo ha origine direttamente o indirettamente dalla radice. Un albero con radici ordinate è un albero con radici in cui sono ordinati i figli di ciascun vertice interno. Se ogni vertice interno di un albero radicato non ha più di m figli, si chiama albero m-ary. Se ogni vertice interno di un albero radicato ha esattamente m figli, è chiamato albero pieno di m-ario. Se $ m = 2 $, l'albero radicato è chiamato albero binario.

Albero di ricerca binario

L'albero di ricerca binario è un albero binario che soddisfa la seguente proprietà:

  • $ X $ nel sottoalbero sinistro del vertice $ V, Value (X) \ le Value (V) $
  • $ Y $ nel sottoalbero destro del vertice $ V, Valore (Y) \ ge Valore (V) $

Quindi, il valore di tutti i vertici del sottoalbero sinistro di un nodo interno $ V $ è minore o uguale a $ V $ e il valore di tutti i vertici del sottoalbero destro del nodo interno $ V $ sono maggiori o uguali a $ V $. Il numero di collegamenti dal nodo radice al nodo più profondo è l'altezza dell'albero di ricerca binario.

Esempio

Algoritmo per cercare una chiave in BST

BST_Search(x, k) 
if ( x = NIL or k = Value[x] ) 
   return x; 
if ( k < Value[x]) 
   return BST_Search (left[x], k); 
else  
   return BST_Search (right[x], k)

Complessità dell'albero di ricerca binario

Case nella media Nel peggiore dei casi
Complessità spaziale Sopra) Sopra)
Cerca complessità O (log n) Sopra)
Complessità dell'inserimento O (log n) Sopra)
Complessità di eliminazione O (log n) Sopra)