Come calcolare l'altezza di un albero binario -Parte 1: utilizzo dell'iterazione dell'array in Ruby

Le strutture dati e gli algoritmi sono il cuore e l'anima dell'informatica e del software. Non si può imparare la programmazione senza capire come i dati sono organizzati in codice e come manipolarli.

Una tale struttura di dati è un albero binario:

Foto di Jeremy Bishop su Unsplash

Oh no, non quel tipo di albero, intendo questo:

Figura 1: albero binario semplice

In termini semplici, un albero è una rete di "nodi". Un nodo è un oggetto le cui proprietà includono i dati stessi e i puntatori ai suoi "figli". Per un albero binario, il numero massimo di figli che ogni nodo può avere è 2. Un albero binario avrà un nodo radice e al massimo due figli. Ogni bambino è solo un puntatore a un altro oggetto albero o può essere nullo. Usando un hash, questo può essere visualizzato come:

albero = {
 : data => 1,
 : left_child => [another_tree] || nil,
 : right_child => [another_tree_again] || zero
}

Prima di passare ai calcoli in altezza, dobbiamo prima trovare alcuni usi per gli alberi binari.

Se osservi le directory o la struttura dei file nel tuo computer, segue una struttura ad albero (sebbene più generale). Ogni cartella può contenere file (i dati) e un numero di altre directory (che non sono necessariamente dati in se stessi ma piuttosto solo indirizzi di tali dati contenuti all'interno di quelle sottodirectory). Esistono altri casi d'uso per alberi binari discussi meglio da altri articoli:

A Quora

Stack Overflow

Gli alberi binari sono un argomento vasto e ci sono così tante cose che posso scrivere su di loro (come i diversi modi di cercarli, forse un articolo futuro?). Tuttavia, qui sarò molto specifico: calcolare l'altezza di un albero binario.

La prima cosa da capire in relazione a ciò è che possiamo rappresentare un albero binario usando un array. Ma anche se ciò è possibile, esistono diversi modi per stabilire ciascun nodo e associarli (come elemento in un array) ai rispettivi figli sinistro e destro.

Per semplicità useremo il metodo "breadth-first" per appiattire l'albero. In "breadth-first" inseriamo i dati contenuti in ciascun nodo a partire dalla radice. Quindi passiamo al livello inferiore successivo, stabilendo i dati di ciascun nodo da sinistra a destra. Passiamo attraverso tutti i livelli fino a quello più basso.

Se un albero secondario non ha figli sinistro o destro, tale figlio può essere rappresentato come 0, purché l'albero secondario non sia al livello più basso dell'albero binario.

Figura 2: albero binario modificato dalla figura 1.
albero = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] (T0)
* rappresentazione in serie di Figure2

Numericamente, possiamo calcolare le posizioni dei figli sinistro e destro di ciascun nodo:

il figlio sinistro dell'albero [i] è all'indice 2 * i + 1 (T1)
il figlio destro dell'albero [i] è all'indice 2 * i + 2 (T2)

Come possiamo vedere dalla figura 2, possiamo dire quanto è alto un albero - cioè dobbiamo solo contare quanti nodi ci sono dalla radice all'elemento più basso (compresi la radice e l'elemento più basso) lungo il ramo più lungo. Ma quando è già in forma di array, come facciamo a sapere quanto è alto?

Innanzitutto dobbiamo avere una formula generale per l'altezza di qualsiasi albero:

altezza = 1 + max di (left_child_height, right_child_height) (T3)

Per gli alberi multilivello allora possiamo concludere che per calcolare l'altezza di qualsiasi sottoalbero (e l'albero stesso) dobbiamo prima calcolare le altezze dei bambini sinistro e destro e quindi trovare il più alto tra i due. Nel calcolare le altezze di questi due bambini dobbiamo calcolare le altezze dei loro rispettivi figli e così via.

Detto questo, possiamo ora iniziare a delineare un algoritmo per calcolare l'altezza degli alberi binari multilivello. Esistono due metodi che possiamo adottare, uno utilizza iterazioni o loop e l'altro, a causa della natura ripetitiva dei passaggi (paragrafo precedente), utilizza la ricorsione. Seguirò questo articolo con una discussione su come usare la ricorsione per farlo. Tuttavia, sarebbe troppo facile. Quindi impariamo prima nel modo più duro: lo faremo usando l'iterazione.

Metodo Iterativo

Useremo l'array di alberi T0 sopra per illustrare questo processo

Passaggio 0: dichiarare un array di altezze che memorizzerà le altezze di ciascun albero secondario.

altezze = [] (S0.1)

Passaggio 1: scorrere attraverso l'array: poiché è necessario calcolare prima le altezze dei discendenti, si esegue l'iterazione dall'ultimo elemento. E invece di utilizzare ogni metodo direttamente nella matrice dell'albero, lo useremo per gli indici di ciascun elemento.

(tree.length - 1) .downto (0) do | i | (S1.1)

Passaggio 2: per ogni elemento, trova l'altezza iniziale: se l'elemento è zero (significa che in realtà è un nodo zero), l'altezza iniziale è 0, altrimenti è 1.

initial_height = tree [i] == 0? 0: 1 (S2.1)

Passaggio 3: trova l'altezza del figlio sinistro - all'interno della matrice delle altezze, se l'elemento ha un figlio sinistro, l'altezza di questo figlio è uguale a:

left_child_height = heights [left_child_index] (S3.1)

In quanto sopra, il left_child_index può essere calcolato come segue:

left_child_index = heights.length - i - 1 (S3.2)

Ho escogitato S3.2 attraverso un piccolo tentativo ed errore. Nella simulazione che seguirà queste serie di passaggi, ne farò menzione.

Per riassumere, inizialmente, avevo intenzione di spostare le altezze di ogni discendente in altezza in modo che le altezze di ciascun elemento avessero gli stessi indici dell'elemento stesso sugli alberi. Ma come farò in seguito a notare, l'utilizzo di unshift per questo comporterà la tassazione delle risorse per input di array di grandi dimensioni.

Quindi ho deciso di usare push. Ogni altezza verrà quindi ordinata al contrario rispetto all'ordine degli elementi corrispondenti nella struttura ad albero. In modo che l'altezza, diciamo dell'albero [0] alla fine si troverà nelle altezze [-1].

Se l'elemento in questione non ha figli di sinistra, left_child_index dovrebbe essere nullo. Per assicurarci di cogliere questo scenario:

left_child_index = nil if tree [2 * i + 1] .nil? (S3.3)

Mettere insieme S3.2 e S3.3 usando un ternario:

left_child_index = tree [2 * i + 1] .nil? ? zero: heights.length - i -1 (S3.4)

Pertanto, l'altezza del bambino sinistro dovrà essere 0 se il bambino sinistro è zero. La formula completa per left_child_height è quindi:

left_child_height = left_child_index.nil? ? 0: heights [left_child_index] (S3.5)

Passaggio 4: trova l'altezza del figlio destro: trovare l'altezza del figlio destro di un sottoalbero segue la stessa logica del passaggio 3. Poiché stiamo riempiendo la matrice di altezze da sinistra a destra (usando push) e stiamo ripetendo l'albero da destra a sinistra, l'altezza del figlio destro di ogni sottoalbero verrà sempre spinta prima in altezza. Pertanto, il figlio sinistro di qualsiasi elemento sarà nella posizione left_child_index -1 all'interno delle altezze (se il figlio destro non è nullo nell'albero). Prendendo in considerazione questi e seguendo la logica del passaggio 3:

right_child_index = tree [2 * i + 2] .nil? zero: left_child_index - 1 (S4.1)
right_child_height = right_child_index.nil? ? 0: heights [right_child_index] (S4.2)

Passaggio 5: trova l'altezza totale dell'elemento - Dopo aver trovato le altezze dei figli sinistro e destro dell'elemento in questione (all'indice i in Ltree), ora possiamo trovare l'altezza totale di quell'elemento:

total_height = initial_height + [left_child_height, right_child_height] .max (S5.1)

Dal punto di vista numerico, se l'elemento è 0 e capita di avere un bambino (ren) all'interno dell'albero, tale figlio (ren) sarà anche 0. Quindi, il suo total_height sarà anche 0. Questo è il caso dell'elemento i = 5 in T0 sopra:

                                         sinistra destra
                                         bambino figlio
albero = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0]
                      i = 5 i = 11 i = 12
                  elemento in questione
(T0 qui ripetuto)
total_height = 0 + [0,0] .max = 0 (S5.2)

Ma per l'elemento in i = 4, l'altezza è:

                                    sinistra destra
                                    bambino figlio
albero = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0]
                   i = 4 i = 9 i = 10
                  elemento
                 in questione
total_height = 1 + [1,1] .max = 2 (S5.3)

In S5.3 e S5.4 sopra abbiamo appena usato l'ispezione visiva per calcolare le altezze dei figli destro e sinistro dell'elemento in questione. Ma questo illustra come funziona il nostro algoritmo. Ora, dopo il calcolo per total_height, semplicemente:

Passaggio 6: spingere total_height in altezza - Come ho notato prima, l'utilizzo del metodo push è più efficiente, specialmente per array di grandi dimensioni.

heights.push (total_height) (S6.1)

Una volta passati in rassegna tutti gli elementi dell'array dell'albero, avremo un'altezza dell'array composta dalle altezze di ciascun sottoalbero dell'albero binario. Dovrebbe sembrare come questo:

altezze (dopo l'iterazione completa) = [0, 1, 0, 0, 1, 1, 1, 1, 2, 0, 2, 2, 3, 3, 4] (S6.2)

Step 7: Restituisci l'altezza dell'albero binario - Se il nostro obiettivo è solo scoprire l'altezza dell'albero madre (che significa dalla radice fino al nodo più in basso a destra), allora semplicemente:

return heights [-1] (S7.1)
* Nota se questa è l'ultima riga del metodo, la parola chiave 'return' è ridondante (almeno in Ruby)

Tuttavia, molte volte potremmo essere interessati a calcolare le altezze di qualsiasi sottoalbero. In tal caso, restituiamo semplicemente l'array heights stesso e quindi chiunque utilizzi il programma può semplicemente includere qualsiasi indice per trovare l'altezza di un ramo specifico nella struttura.

Il metodo completo di seguito:

Testiamo questo algoritmo.

Supponiamo di eseguire binary_tree_height (albero). Il calcolo per le altezze dell'albero [14] fino all'albero [7] è piuttosto semplice (saranno 0 o 1 poiché sono tutti al livello più basso dell'albero), quindi non li simuleremo più qui. Supponiamo che siamo già in quella parte dell'iterazione quando sarò uguale a 6. Pertanto, in questo frangente:

i = 6 (F1)
albero [6] = 9 (F2)
heights = [0, 1, 0, 0, 1, 1, 1, 1] (heights.length a questo punto è 8) (F3)

Ora possiamo vedere che l'albero [6] è uguale a 9 (e non a 0). Perciò:

valore_iniziale = 1 (F4)

Come promesso, ecco come mi è venuta in mente la formula per gli indici dei bambini sinistro e destro.

Quindi ho iniziato con un array di altezze già riempito con le altezze degli elementi più bassi, come mostrato in F3. Poiché ora sto lavorando con l'albero [6] (che è 9), i suoi figli sinistro e destro sono albero [13] e albero [14]; le cui altezze corrispondenti sono rispettivamente in altezze [1] e altezze [0]. Se ciò non è abbastanza chiaro, sappiamo che spingiamo a partire dall'albero [14] - questo diventerà altezze [0]. Quindi calcoliamo e spingiamo l'altezza dell'albero [13] - questo sarà altezze [1]. Relativi agli indici:

indice del bambino sinistro sugli alberi = 13
indice dell'altezza del bambino sinistro in altezza = LEFT_INDEX = 1
indice del bambino giusto sugli alberi = 14
indice dell'altezza del bambino destro in altezza = RIGHT_INDEX = 0
indice corrente dell'elemento in questione = MOTHER_INDEX = 6
lunghezza attuale delle altezze array = LENGTH = 8
LEFT_INDEX = 1 = 8 - 6 - 1 = LENGTH - MOTHER_INDEX - 1
RIGHT_INDEX = 0 = 8 - 6 - 2 = LENGTH - MOTHER_INDEX - 2
(o semplicemente LEFT_INDEX -1) (F5)

Ora possiamo applicare questa logica a tutti gli elementi, quindi nel codice calcoliamo l'altezza dell'albero [6] come segue:

Calcolo dell'altezza del bambino sinistro dell'albero [6]:
dal codice a S3.4:
left_child_index = tree [2 * i + 1] .nil? ? zero: heights.length - i - 1
Poiché l'albero [2 * 6 + 1] = albero [13] = 4 non è zero allora:
left_child_index = 8 - 6 - 1 = 1
dal codice a S3.5:
left_child_height = left_child_index.nil? ? 0: heights [left_child_index]
Allora:
left_child_height = heights [1] = 1

Seguendo lo stesso per l'altezza del bambino giusto dell'albero [6]:

dal codice a S4.1:
right_child_index = tree [2 * i + 2] .nil? zero: left_child_index - 1
Poiché l'albero [2 * 6 + 2] = albero [14] = 4 e non è nullo:
right_child_index = left_child_index -1 = 1 -1 = 0 ->! nil?
e dal codice in S4.2:
right_child_height = right_child_index.nil? ? 0: heights [right_child_index]
Pertanto: right_child_height = heights [0] = 0

Ora possiamo trovare l'altezza totale dell'albero [6]:

total_height (albero [6]) = 1 + [1,0] .max = 1 + 1 = 2

Possiamo quindi spingere questo total_height in altezza:

heights.push (2), in modo tale che:
altezze = [0, 1, 0, 0, 1, 1, 1, 1, 2]

E la stessa cosa continua finché non lavoriamo su tree [0] e l'array delle altezze finali dovrebbe essere:

altezze = [0, 1, 0, 0, 1, 1, 1, 1, 2, 0, 2, 2, 3, 3, 4]

E restituendo heights [-1] (o heights [heights.length -1], qualunque preferiamo), determiniamo che l'altezza dell'albero è 4. Possiamo verificarlo visivamente in entrambe le figure 1 e 2 sopra.

Ci sono voluti 7 passaggi per trovare la risposta. Con questa dimensione di array di alberi l'operazione ha richiesto circa 0,024 millisecondi per terminare. Ci vuole metà del tempo (solo 0,012 millisecondi) per ottenere la stessa cosa usando la ricorsione.

Come anteprima su come farlo in modo ricorsivo, possiamo semplicemente fare qualcosa del tipo:

def tree_height_recursive (albero_array, indice = 0)
  restituisce 0 se tree_array [indice] .nil? o tree_array [indice] == 0
  left_child_height = recursive_tree_height (albero_array, 2 * indice + 1)
  right_child_height = recursive_tree_height (albero_array, 2 * indice +2)
  total_height = 1 + [left_child_height, right_child_height] .max
fine

Vediamo che la ricorsione probabilmente richiederà solo 4 passaggi al massimo per fare lo stesso compito. E ci fa risparmiare la metà del tempo e meno risorse utilizzate.

Un segreto per l'apprendimento degli algoritmi è il duro lavoro e la pratica. Aiuta anche se lavori in collaborazione con altri. In realtà ho fatto quanto sopra non solo, ma con il mio partner di programmazione. In precedenza ho scritto di come l'apprendimento in questo modo sia molto più produttivo ed efficace.

Ecco il mio repository sulle diverse strutture di dati e algoritmi su cui ho lavorato. E infine, non essendo un laureato in Informatica (io sono un ingegnere meccanico), non avrei imparato quello che ho appena scritto e altro se non per una fantastica scuola di programmazione remota chiamata Microverse. Curriculum a parte, ciò che amo di più del suo sistema è l'esercito di mentori e avere un compagno / compagno di programmazione con te ogni singolo giorno.

Seguimi su Twitter | Github