ABR Definizioni

ALBERI BINARI DI RICERCA - TEORIA

//Creazione nuovo nodo
MK-TREE-ELEM(k) //passo un valore k al nuovo nodo da creare.
	x.p = x.right = x.left = null;
	x.key = k;
	return x;

INSERISCI(t,k){
	if(t.root == NULL)
		t = MK-TREE-ELEM(k); //Questa operazione mi stavo dimenticando di farla, attento
		return t;
	else
		return BST-INSERISCI(t.root, k)
}

BST-INSERISCI(x, k){
	output = FALSE;
	if(x.key>k)
		if(x.left ==NULL){
			x.left = MK-TREE-ELEM(k);
			x.left.p = x;
			output = TRUE;
		}
		else{
			BST-INSERISCI(x.left);
	if(x.key<k){
		if(x.right==NULL)
			x.right = MK-TREE-ELEM(k);
			x.right.p = x;
			output = TRUE;
		}
		else{
			BST-INSERISCI(x.right);
return output;
------------------------------------------------------------------------------------------------
//Minimo, Massimo - Versione MIA
MINIMO(x){
if(x.left ==NULL)
	return x;
else
	return MINIMO(x.left);

//Il massimo è la stessa cosa del Minimo, fai tu.

//Cancellazione di un nodo in un albero.....	QUESTO PROPRIO NON MI ENTRA IN TESTA, STUDIALO CON VARI ALBERI E CASI.
TREE-DELETE(t, x){
	if(x.left != NULL) && (x.right!=NULL){
		y = MINIMO(x.right);
		x.key = y.key;
	else
		y = x;
	TREE-BYPASS(t, y);
}
//La complessità di Tree-Delete è Teta(h). Penso poichè La complessita di Minimo è Teta(h);
TREE-BYPASS(t, y){
	if(y.right !=NULL){
		figlio = y.right;
	else
		figlio = y.left;
	if(FIGLIO!=NULL){
		figlio.p = X.P;
	if(x == x.p.left){
		x.p.left = FIGLIO;
	else
		x.p.right = FIGLIO;
La complessità di TREE-BYPASS è Teta(1)
------------------------------------------------------------------------------------------------------------
//Ricerca di un elem
RICERCA-ITERATIVA(x,k)
	while(x!=null or x.key !=k)
		if(x.key>k)
			x = x.left;
		else
			x = x.right;
	return x;

RICERCA-RICORSIVA(x,k)
	if(x== null or x.key == k)
		return x;
	else
		if(x.key>k)
			return RICERCA-RICORSIVA(x.left, k);
		else
			return RICERCA-RICORSIVA(x.right, k);


--------------------------------------------------------------------------------------------

TREE-TO-ARRAY(A, x, i){
	if(x==NULL)
		return i;
	i = TREE-TO-ARRAY(A,x.left, i);
	A[i] = x.key;
	i = TREE-TO-ARRAY(A, x.right, i+1);
	return i;