Rappresentano una possibile implementazione per l'algebra eterogenea "Parti di A ordinato"

Definizione (BST): un albero binario di ricerca per un insieme U è un albero binario tale che:

• ogni nodo v contiene un elemento $u \in U$
• se x è un nodo del sotto albero sx di $v$, e $x$ contiene $s$, allora $s<u$
• se y è un nodo del sottoablero dx di $v$, e $y$ contiene $t$, allora $t>u$

Ogni ragionevole implementazione si basa sull'uso di nodi e riferimenti (puntatori) a nodi. Un nodo contiene:

• un elemento di U
• un riferimento al (nodo) figlio sinistro
• un riferimento al (nodo) figlio destro

Visitando in ordine simmetrico un BST otteniamo la sequenza ordinata dei valori nell'albero

Nota: la costruzione di un BST con n nodi ha un costo $\Omega(n \log n)$

Esempi:

40) Alberi binari di ricerca 2.pdf_Alberi_binari_di_ricerca_2.pdf)

Alberi binari di ricerca: sequenze di inserimento

Dato un albero binario con n nodi, quante sono le sequenze di inserimento di n valori che possono crearlo?

Fatto: