ARBOL BINARIO DE BUSQUEDA

Vista previa del material en texto

ÁRBOL BINARIO DE BÚSQUEDA
ÁRBOL BINARIO DE BÚSQUEDA
Los árboles binarios se adaptan muy bien para buscar elementos de forma eficiente.
Para ello, todos los elementos se almacenan en el árbol ordenados:
- Todos los descendientes izquierdos de un nodo (subárbol izquierdo) son menores que él
- Todos los descendientes derechos de un nodo (subárbol derecho) son mayores que él
La búsqueda es O(log n) en el caso promedio, si el árbol está equilibrado y si las hojas están aproximadamente a la misma profundidad
Los árboles de búsqueda tienen un campo clave en cada nodo, las búsquedas se realizan comparando los valores de las claves en lugar de los valores del dato.
Si buscamos una clave, se ve en qué mitad del árbol se encuentra comparando solamente con el nodo raíz. 
La clave de los nodos de un árbol binario de búsqueda se enumeran en orden creciente siguiendo un recorrido en orden simétrico.
ÁRBOL BINARIO DE BÚSQUEDA
Dado un nodo, las claves de todos los nodos de su subárbol izquierdo son menores que la clave de ese nodo, mientras que las claves de todos los nodos de su subárbol derecho son mayores.
ÁRBOL BINARIO DE BÚSQUEDA
// Clase Nodo:
ÁRBOL BINARIO DE BÚSQUEDA
class Nodo{
Nodo hizq, hder;
int clave;
int dato;
// Constructor por defecto
public Nodo()
{hizq=null; hder=null;
 clave=0; dato=0;}
// Constructor ordinario
public Nodo(int vc, int vd)
{hizq=null; hder=null;
 clave=vc; dato=vd; }
}
	hizq	clave	dato	hder
		10	x	
raiz
ÁRBOL BINARIO DE BÚSQUEDA
	hizq	clave	dato	hder
				
30
4
200
400
null
55
100
null
75
300
null
41
500
null
null
85
600
null
null
CLASE ÁRBOL
	Arbol
	raiz
	Constructor por defecto
inicializar()
arbolVacio()
insertar(c,d)
CLASE ÁRBOL
public class arbol 
{ // Campos
 Nodo raiz;
// Constructor por defecto
public arbol() 
{raíz = null; }
// Inicializar
public void inicializar() 
{raíz = null; }
// Verificar si el árbol está vacío
public boolean arbolVacio() 
 { return raiz == null; }
ÁRBOL VACÍO
 raiz
null
CLASE ÁRBOL
// Insertar, como nodo hoja
public void insertar(int c, int d) 
{ // Crear el nuevo nodo
Nodo nuevo=new Nodo(c, d);
// Conectar el nuevo nodo al árbol
if(arbolVacio()) {	raiz=nuevo; }
else { // Árbol no vacío
 Nodo p=raiz, q=null;
 while(p!=null) { q=p;
	 if(p.clave>c) { p=p.hizq; }
	 else {p=p.hder; }
			}
if(q.clave>c) { q.hizq=nuevo; }
else { q.hder=nuevo; }
}
}
ÁRBOL VACÍO
 raiz
null
	hizq	clave	dato	hder
	null	35	d	null
nuevo
raiz
INSERTAR COMO NODO HOJA
	hizq	clave	dato	hder
	null	35	d	null
30
4
200
400
null
55
100
null
75
300
null
41
500
null
null
85
600
null
null
null
nuevo
q
p
q
CLASE OPERACIONES
	Operaciones
	
	insertarN(A)
preorden(p)
simetrico(p)
posorden(p)
buscar(A,cb)
CLASE Operaciones
public class Operaciones { 
// Insertar N nodos
public arbol insertarN(arbol a) 
{ System.out.println("No de nodos=");
 int nn=Leer.datoInt();
 for(int i=1;i<=nn;++i) {
 System.out.println("Nodo"+i+":");
 System.out.println("clave");
 int c=Leer.datoInt();
 System.out.println("Dato");
 int d=Leer.dato();
 a.insertar(c,d);
 }
 return a;
}
CLASE Operaciones
// Recorrido en orden previo
public void preorden( Nodo p)
{ if(p!=null) { // Visitar el nodo raíz
		 System.out.println(p.clave+”,”+p.dato);
		 // Visitar el subárbol izquierdo
		 preorden(p.hizq);
		 // Visitar el subárbol derecho
		 preorden(p.hder);
 }
 }
CLASE Operaciones
// Recorrido en orden simétrico
public void simetrico( Nodo p)
{ if(p!=null) { // Visitar el subárbol izquierdo
		 simetrico(p.hizq);
		 // Visitar el nodo raíz
		 System.out.println(p.clave+”,”+p.dato);
		 // Visitar el subárbol derecho
		 simetrico(p.hder);
 }
 }
CLASE Operaciones
// Recorrido en orden posterior
public void posorden( Nodo p)
{ if(p!=null) { // Visitar el subárbol izquierdo
		 posorden(p.hizq);
		 // Visitar el subárbol derecho
		 posorden(p.hder);
		 // Visitar el nodo raíz
 System.out.println(p.clave+”,”+p.dato);
 }
 }
CLASE Operaciones
// Buscar un nodo, dada su clave
public void buscar(arbol a,int cb)
{ Nodo p=a.raiz;
 while((p!=null)&&(p.clave!=cb)) {
 if(p.clave>cb) { p=p.hizq; }
 else { p=p.hder; }
 }
 if(p==null) { System.out.println("NO LOCALIZADO");}
 else { System.out.println(p.dato); }
 }
}
CLASE Principal
public class Principal {
public static void main(String[] args)
{	Operaciones op=new Operaciones();
	Arbol A=new Arbol();
	A= op.insertarN(A);
	System.out.println("PRE-ORDEN");
	op.preorden(A.raiz);
	System.out.println("SIMETRICO");
	op.simetrico(A.raiz);
	System.out.println("POS-ORDEN");
	op.posorden(A.raiz);
	System.out.println("BUSCAR CLAVE");
	System.out.println("ingrese clave");
	int cb=Leer.datoInt();
	op.buscar(A, cb);
	}
}
GRACIAS