INDICE
- Albero di ricerca binario
- Creare un nodo
- Il nodo radice
- Costruzione del primo livello
- Generalizzare l'albero
- Implementazione della ricerca
Albero di ricerca binario
Nella programmazione, gli alberi sono una struttura di dati che si presenta sorprendentemente spesso. Hanno una serie di utilizzi diversi, che vanno dall'archiviazione efficiente dei dati alla rappresentazione di una gerarchia di file.
In particolare, in questo post esamineremo l'albero di ricerca binaria. Il suo nome può sembrare intimidatorio, ma in realtà è molto semplice!
Concetti
Gli alberi iniziano con un nodo radice che si dirama verso i nodi sottostanti (i suoi figli). La parola binario indica che ogni nodo ha al massimo 2 figli. Si chiama albero di ricerca perché l'ordine dei nodi è ordinato in base al valore dei dati. Vediamo un esempio:
Ogni figlio che si trova a sinistra del suo genitore è più piccolo. Ogni figlio che si trova a destra del suo genitore è maggiore. Per esempio, la radice 5 ha due figli 3 e 7. Poiché 3 è minore di 5, è alla sinistra di 5.
Sapendo che i dati sono in quest'ordine, ci vorrà meno tempo per trovare un particolare nodo. Ad esempio, cerchiamo il 4.
Partendo dalla radice, sappiamo che è minore di 5 e quindi andiamo a sinistra. Poi incontriamo 3 e sappiamo che 4 è maggiore di 3, quindi andiamo a destra. E qui troviamo il 4.
In media questo metodo sarà più veloce di una ricerca casuale. Il risparmio di tempo diventa tanto maggiore quanto più grande è l'albero.
Ora proviamo a costruire il nostro albero di ricerca binaria scrivendo un po' di codice, che non fa mai male :)
Creare un nodo
Creiamo innanzitutto la classe Node, dalla quale creeremo ogni elemento del nostro albero:
Il nodo deve contenere dei dati, che inseriremo successivamente. Deve inoltre contenere i riferimenti al figlio sinistro (left) e al figlio destro (right).
Completiamo il metodo costruttore e la funzione costruttore sul nodo. Successivamente, memorizziamo i dati in una proprietà data dell'istanza.
Infine, memorizziamo null, left e right nelle proprietà utilizzando this.
Esempio di utilizzo:
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
module.exports = Node;
Il nodo radice
Ora è il momento di creare il nostro albero.
Un albero terrà traccia di una proprietà specifica: il riferimento al nodo radice.
Radice
Completiamo la funzione costruttore della classe Tree nel nuovo file Tree.js.
Tutto ciò che occorre fare per ora è memorizzare null nella proprietà root.
class Tree {
constructor() {
this.root = null;
}
}
module.exports = Tree;
Aggiunta di una radice
In questa fase creeremo un nuovo metodo per aggiungere nodi al nostro albero. È un compito difficile da generalizzare, quindi lo affronteremo pezzo per pezzo :)
Per prima cosa iniziamo ad aggiungere una radice a un albero vuoto.
Creiamo un nuovo metodo addNode sulla classe Tree che prenda un nuovo nodo e lo aggiunga all'albero.
Si supponga che l'albero sia vuoto per questa fase. È sufficiente impostare la radice come il nodo passato nel metodo.
addNode(newNode) {
this.root = newNode;
}
Costruzione del primo livello
Ora è il momento di concentrarsi sull'aggiunta del primo strato di nodi sotto la nostra radice! :)
Ogni nodo che non presenta archi uscenti è detto foglia (leaf node) e in ogni albero finito, cioè con un numero finito di nodi, si trova almeno un nodo foglia. Ovviamente, un nodo può essere contemporaneamente padre (se ha archi uscenti) e figlio (se ha un arco entrante, ovvero se è diverso dalla radice).
Manteniamo il codice utilizzato per superare l'ultima fase e aggiungiamo un'altra casistica per quando esiste già una radice:
Quando la radice esiste già, dobbiamo decidere da che parte aggiungere il nuovo nodo foglia.
Se i dati del nuovo nodo sono inferiori a quelli della radice, lo aggiungeremo a sinistra.
Al contrario, se i dati sono maggiori, lo aggiungeremo a destra.
Modifichiamo ora la funzione addNode per gestire anche l'aggiunta dei primi figli della radice:
// Nuovo metodo: se la root esiste, e se il dato del nuovo nodo e' minore, aggiungiamo il nodo a sinistra. Viceversa, a destra.
addNode(newNode) {
if (this.root) {
if (newNode.data < this.root.data) {
this.root.left = newNode;
} else {
this.root.right = newNode;
}
// Se non dovesse esistere una gia' una radice..
} else {
this.root = newNode;
}
}
Generalizzare l'albero
Ora è il momento di far funzionare la funzione addNode per generali livelli dell'albero.
Completiamo la funzione addNode in modo che possa gestire l'aggiunta di nodi indipendentemente dalle dimensioni dell'albero.
Possiamo farlo in modo iterativo o ricorsivo!
Soluzione ricorsiva
Abbiamo già scritto il codice per aggiungere un nodo sotto un altro nodo. Tutto ciò che dobbiamo fare è applicarlo in modo ricorsivo.
Un buon modo per iniziare la soluzione ricorsiva è scrivere una nuova funzione su Albero che prenda due argomenti: un genitore e un figlio. Questa funzione deve aggiungere il figlio sotto il nodo genitore.
Caso 1
Se i dati del figlio sono inferiori a quelli del genitore, sceglieremo di andare a sinistra.
- Se il genitore ha già un nodo sinistro, chiameremo questa nuova funzione ricorsivamente con quel nodo sinistro come genitore;
- Se il genitore non ha un nodo sinistro, impostiamo il nuovo nodo come nuovo nodo sinistro;
Caso 2
Se i dati del figlio sono maggiori di quelli del genitore, sceglieremo di andare a destra.
- Se il genitore ha già un nodo destro, chiameremo questa nuova funzione ricorsivamente con quel nodo destro come genitore;
- Se il genitore non ha un nodo destro, impostiamo il nuovo nodo come nuovo nodo destro;
Ora è possibile invocare questo metodo da addNode se esiste una radice. Inizialmente la radice sarà il genitore, che si espanderà man mano che verranno aggiunti altri nodi.
constructor() {
this.root = null;
}
// Soluzione ricorsiva
insertNode(root, newNode) {
if (newNode.data < root.data) {
if (root.left) {
this.insertNode(root.left, newNode);
} else {
root.left = newNode;
return;
}
} else {
if (root.right) {
this.insertNode(root.right, newNode);
} else {
root.right = newNode;
return;
}
}
}
addNode(newNode) {
if (this.root) {
this.insertNode(this.root, newNode);
} else {
this.root = newNode;
}
Implementazione della ricerca
È il momento di raccogliere i frutti della creazione del nostro albero di ricerca binario. E' il momento della ricerca :)
Il nostro obiettivo: costruire il metodo hasNode.
Il metodo hasNode prende come input un numero e cerca nel nostro albero un nodo che abbia quel numero all'interno della sua proprietà dati.
Se esiste un nodo con il numero, restituisce true. In caso contrario, restituisce false.
Utilizziamo l'ordine di ordinamento per trovare i nodi dell'albero. Ad esempio, se cercassimo il nodo 4, potremmo usare l'ordine di ordinamento per trovare i nodi nell'albero:
1) Partiamo dalla radice 5, riconosciamo che 4 è minore di 5 e ci spostiamo a sinistra.
2) Troviamo 3, riconosciamo che 4 è maggiore di 3 e ci spostiamo a destra.
3) Troviamo 4, riconosciamo che è quello che stiamo cercando e restituiamo true.
Se cerchiamo un nodo mancante, restituiamo false.
Ad esempio, se cercassimo 7 in questo albero:
Ci accorgeremmo che 7 è maggiore di 5, e spostandoci a destra non troveremo nessun nodo destro! Restituiamo quindi false.
Come implementiamo lato codice tutto questo bel ragionare?
hasNode(data) {
return this.findNode(this.root, data);
}
findNode(root, data) {
// Caso base ricorsivo
if (!root) {
return false; // Se la root non viene trovata, restituiamo false
} else if (root.data === data) {
return true;
// Chiamata ricorsiva a sinistra
} else if (root.data > data) {
return this.findNode(root.left, data);
// Chiamata ricorsiva a destra
} else if (root.data < data) {
return this.findNode(root.right, data);
}
}
const tree = new Tree();
const node1 = new Node(4);
Nel prossimo approfondimento analizzeremo gli alberi di Merkle, la loro struttura e il loro funzionamento, il tutto condito con del sano codice JS :)
Grazie per la lettura ed il tempo dedicato!
Top comments (0)