<aside> ℹ️

Un albero binario di ricerca è un particolare tipo di albero binario

Ogni nodo $u$ è un oggetto costituito da diversi campi: key (più eventuali dati satellite) un campo left, right e parent che puntano rispettivamente al figlio sinistro, al figlio destro e al padre $u$

Le chiavi sono sempre memorizzate in modo che sia verificata la proprietà dell’albero binario di ricerca:

Sia $x$ un nodo di un albero binario di ricerca; allora:

• se $y$ è un nodo del sottoalbero sinistro di $x$ allora key[y]<=key[x]
• se $y$ è un nodo del sottoalbero destro di $x$ allora key[y]>=key[x] </aside>

Visita in ordine simmetrico

Inorder-Tree-Walk(x){
	if x != NIL{
		Inorder-Tree-Walk(left[x])
		stampa key[x]
		Inorder-Tree-Walk(right[x])
	}
}

Inorder-Tree-Walk(root)
5,6,8,9,15,16,17,18

Elenca tutte le chiavi di un BST in modo ordinato

• Esercizio

Operazioni su Alberi Binari di Ricerca

<aside> ℹ️

I BST sono strutture dati sulle quali vengono realizzate molte delle operazioni definite su insiemi dinamici, tra le quali:

Search, Insert, Delete, Minimum, Maximum, Precedessor, Successor

</aside>

Ricerca di un elemento

Su ogni nodo usa la proprietà dell’albero binario di ricerca per decidere se proseguire a destra o a sinistra

Tree-Search(x,k){
	if x == NIL || k == key[x]
		return x;
	if k < key[x]
		return Tree-Search(left[x],k)
	else
		return Tree-Search(right[x],k)	
}

Iterative-Tree-Search(x,k){
	while x != NIL || k != key[x]
	if k < key[x]
		x = left[x]
	else 
		x = right[x]
	return x;
}

Minimo e Massimo

Seguiamo i puntatori left (per Tree-Minimum) e right (per Tree-Maximum) dalla radice fin quando non si insontra NIL

Tree-Minimum(x){
	while left[x] != NIL
		x = left[x]
	return x;
}

Tree-Maximum(x){
	while tight[x] != NIL
		x = right[x]
	return x;
}

Successore e Predecessore

Tree-Successor(x){
	if right[x] != NIL
		return Tree-Minimum(right[x])
	
	y = p[x]
	while x != NIL && x == right[y]
		x = y
		y = p[y]
	return y;
}