Trees

Cos’è un Tree

Un tree è una struttura dati gerarchica composta da nodi collegati da puntatori. Ogni nodo può puntare a zero o più figli. Quando ciascun nodo ha al massimo due collegamenti, parliamo di binary tree.

Collegamento con le linked list:

• Una linked list è un caso particolare di tree in cui ogni nodo ha solo il puntatore next.
• Nei binary tree ogni nodo possiede due riferimenti: left e right.

1
// Nodo base di un tree binario
2
class Node {
3
  constructor(value) {
4
    // Valore memorizzato nel nodo corrente
5
    this.value = value;
6
    // Puntatore al sotto-albero sinistro (può rimanere null)
7
    this.left = null;
8
    // Puntatore al sotto-albero destro (può rimanere null)
9
    this.right = null;
10
  }
11
}

Terminologia fondamentale

• Root: nodo principale da cui parte l’albero.
• Parent / Child: relazione tra nodo e figli diretti.
• Siblings: figli che condividono lo stesso parent.
• Leaf: nodo senza figli (left e right null).
• Depth / Level: distanza del nodo dalla root.
• Subtree: tree completo con una root interna all’albero principale.

Tipi di binary tree

Osservazioni chiave:

• Un tree perfect è sempre full e complete.
• Aggiungere nodi fuori ordine può rompere la perfezione, ma non necessariamente la completezza.

Binary Search Tree (BST)

Un Binary Search Tree aggiunge la regola d’ordinamento:

• Ogni nodo rispetta left.value < node.value < right.value.
• La regola vale ricorsivamente per ogni sotto-albero.

Inserimento concettuale

1. Parti dalla root.
2. Confronta il nuovo valore con il nodo corrente.
3. Vai a sinistra se è minore, a destra se è maggiore.
4. Ripeti finché trovi uno slot vuoto e inserisci.
5. I duplicati non sono ammessi (in alternativa si può usare un contatore interno al nodo).

Ricerca (contains)

1. Parti dalla root.
2. Se il valore cercato è minore vai a sinistra, se è maggiore vai a destra.
3. Se trovi il valore ritorni true, se arrivi a null ritorni false.

Questo schema applica Divide & Conquer: a ogni passo si scarta metà dell’albero.

Complessità Big O dei BST

• Lookup/Remove sono più veloci su BST rispetto a linked list e array perché non richiedono scansione sequenziale.
• Insert in una linked list (push) rimane O(1): si rinuncia alla velocità di inserimento per ottenere ricerche veloci nei BST.

Confronto con altre strutture

Trade-off: i BST sacrificano la semplicità di inserimento lineare per abilitare ricerche e rimozioni drasticamente più veloci (quando bilanciati).

Implementazione BST

Costruttore dell’albero

1
// Binary Search Tree base: mantiene solo il riferimento alla root
2
class BinarySearchTree {
3
  constructor() {
4
    // Root inizialmente a null finché non inseriamo il primo nodo
5
    this.root = null;
6
  }
7
}

insert(value)

1
// Inserisce un nuovo valore rispettando la proprietà del BST
2
insert(value) {
3
  // 1. Crea il nodo da inserire
4
  const newNode = new Node(value);
5

6
  // 2. Se l'albero è vuoto il nuovo nodo diventa la root
7
  if (this.root === null) {
8
    this.root = newNode;
9
    return this; // Consente chaining
10
  }
11

12
  // 3. Temp funge da cursore per attraversare il tree
13
  let temp = this.root;
14

15
  // 4. Loop finché non troviamo una posizione libera
16
  while (true) {
17
    // Evitiamo duplicati
18
    if (newNode.value === temp.value) return undefined;
19

20
    // 4a. Il nuovo valore è minore → spostati a sinistra
21
    if (newNode.value < temp.value) {
22
      // Se la sinistra è libera inseriamo qui
23
      if (temp.left === null) {
24
        temp.left = newNode;
25
        return this;
26
      }
27
      // Altrimenti scendiamo di un livello
28
      temp = temp.left;
29
    } else {
30
      // 4b. Il nuovo valore è maggiore → spostati a destra
31
      if (temp.right === null) {
32
        temp.right = newNode;
33
        return this;
34
      }
35
      temp = temp.right;
36
    }
37
  }
38
}

Edge cases gestiti:

• Albero vuoto (root === null).
• Inserimento su catena lunga (continuiamo a scendere).
• Duplicati (ritorniamo undefined per evitare ambiguità).

contains(value)

1
// Verifica se un valore è presente nel BST
2
contains(value) {
3
  // 1. Albero vuoto → assenza garantita
4
  if (this.root === null) return false;
5

6
  // 2. Temp parte dalla root e scende seguendo i confronti
7
  let temp = this.root;
8

9
  // 3. Continuiamo finché troviamo un nodo valido
10
  while (temp) {
11
    // 3a. Valore minore → andare a sinistra
12
    if (value < temp.value) {
13
      temp = temp.left;
14
    }
15
    // 3b. Valore maggiore → andare a destra
16
    else if (value > temp.value) {
17
      temp = temp.right;
18
    }
19
    // 3c. Valore uguale → trovato!
20
    else {
21
      return true;
22
    }
23
  }
24

25
  // 4. Se usciamo dal while significa che abbiamo raggiunto un null
26
  return false;
27
}

Pattern: la logica di contains è identica a lookup in un array ordinato usando binary search, ma operiamo su nodi collegati.