Altri tipi

Tra gli alberi binari di ricerca ci sono anche altri tipi come:

• Alberi AVL

  Sono alberi bilanciati i cui nodi contengono un fattore di bilanciamento che è minore o uguale ad $1$ per ogni nodo, e rappresenta la differenza dell'altezza del sottoalbero sinistro con quella del destro.

  L'inserimento e cancellazione sono più complesse dato che bisogna mantenere l'albero bilanciato.

• B-Alberi

  Sono alberi bilanciati che hanno almeno due figli, dove:

  • Tutte le foglie hanno la stessa profondità
  • Ogni nodo $v$ (radice esclusa) contiene $\mathrm{grado}(v)-1\le K(v)\le 2\mathrm{grado}(v)-1$ chiavi ordinate
  • La radice $r$ contiene $1\le K(r)\le 2\mathrm{grado}(r)-1$ chiavi ordinate
  • Ogni nodo interno $v$ ha $K(v)+1$ figli
  • Le chiavi separano gli intervalli delle chiavi nei sottoalberi

  Per esempio,

  

• Alberi rossi e neri

  Contengono oltre alla chiave il colore del nodo, che può essere rosso o nero.

  L'albero viene vincolato in base al colore in un modo che garantisce che l'albero sia bilanciato.