[Algoritmi] Verificare se l'albero binario è di ricerca

[absinth]

Ciao a tutti! Se qualcuno può aiutarmi con il problema mi fa un grande favore.
Per la verifica è richiesto un pseudo codice per un algoritmo con prestazioni temporali $O(n)$.
Io intanto l'ho fatto in java. Ho pensato di fare un attraversamento simmetrico (da me all'uni lo chiamiamo così, ma gli anglosassoni "inorder" insomma, quello degli alberi di ricerca). Mentre lo attraversa, scrive in ogni casella $i$ dell'array passato come parametro il contenuto del nodo (value) che dovrebbe essere comparable. $i$ viene restituito ogni volta incrementato. Mentre inserisco verifico anche la relazione d'ordine tra i vari elementi nell'array eventualmente restituendo il valore sentinella $-1$. Facendo alcuni test sembra che vada bene ma uso anche $\theta(n)$ di memoria. Forse c'è qualche soluzione migliore senza l'array?

public boolean isSearchTree(Tree u)
{
	Comparable[] r = new Comparable[u.size()];
	return isCount(u.root(), r, 0) != -1;
}

private static int isCountTree (Position v, Comparable[] a, int j)
{
	if(j==-1)
		return -1;
	int i=j;
	if(v.hasLeft())
		i=isCountTree(v.left(),a, i);
	a[i++]=v.value();
	if(v.hasRight())
		i=isCountTree(v.right(),a, i);
	if(i-1>0 && a[i-2].compareTo(a[i-1])>0)
		return i;
	return -1;
}

[absinth]

Mi è appena venuta in mente un'idea forse migliore che mi consente di risparmiare anche sullo spazio: uso $O(1)$ escluso lo stack usato dalla ricorsione. L'idea è questa: in un albero di ricerca per ogni nodo deve valere che il massimo nel suo sottoalbero sinistro è minore/uguale al valore contenuto nel nodo mentre il minimo del sottoalbero destro è maggiore del valore contenuto nel nodo. Quindi si può creare una ricorsione che ogni volta dà come ritorno il valore estremo nei figli (massimo/minimo a seconda) e segnalare se la proprietà appena detta non viene rispettata in un array booleano passato come parametro di dimensione 1. Forse si potrebbe evitare anche l'array e passare come sentinella un valore "null" (che io lo passo comunque) ma a livello di prestazioni in java non cambia nulla.

public static boolean isSearchTree(Tree t)
{
	boolean[] r = new boolean[1];
	r[0]=TRUE;
	getExtreme(t, t.root(), r);
	return s[0];
}

private static Comparable getExtreme(Tree t, Position v, boolean[] s)
{
	Comparable left,right; //sono gli estremi dell'albero sx (max) e albero dx (min)
	if(v.isExternal())
		return v.value();
	right=left=v.value(); //per i casi quando c'è un solo figlio, altrimenti gli if sovrascrivono
	if(v.hasLeft())
		left=getExtreme(t, v.left(), s);
	if(v.hasRight())
		right=getExtreme(t, v.right(), s);
	if(left.compareTo(v.value())<=0 && right.compareTo(v.value())>=0)
	{
		if(t.root()!=v)
			if(v.parent().left()==v)
				return right;
		return left;
	}
	s[0]=FALSE;
	return null;
}

[apatriarca]

Non ho letto il codice, ma se stai facendo una visita inorder è sufficiente verificare che la visita fornisca valori crescenti. Se salvi il valore precedente nella visita puoi semplicemente confrontare il valore corrente con questo valore e stabilire da quello che l'albero è effettivamente di ricerca.

[absinth]

Già buona idea forse la più semplice... allora basterebbe modificare il primo algoritmo che invece di incrementare ogni volta l'indice mantenga lo stesso array di dimensione 1 con dentro salvato il valore precedente... così rimane $O(1)$ lo spazio. Grazie!