igor santos grueiro. muchos objetos tienen clave
TRANSCRIPT
ÁRBOLES BINARIOS DE
BÚSQUEDA (BST)
Igor Santos Grueiro
Muchos objetos tienen
CLAVE
Cuando un objeto dispone de clave,
EL ACCESOnormalmente se realiza por ésta
¿Qué estructura de datos
CONOCEMOSque tenga acceso por una clave?
?
Ninguna
Para eso están los
ÁRBOLES
Un ÁRBOL BINARIO es una estructura de datos
formada por NODOS
2 enlacesClave menorClave mayor
Un nodo de un BST tiene un HIJO IZQUIERDO y un HIJO DERECHO
izquierdo derecho
Un nodo tiene un ELEMENTO Y una CLAVE que permite el acceso
CLAVE
ELEMENTO
LA CLAVE TIENE QUE
SER COMPARABLE
public class Clave implements Comparable
recordemos
“Implements” se utiliza para decir que una clase tiene cierto comportamiento:
UNA INTERFAZ
1
UNA INTERFAZ es como una clase abstracta, pero
Sin atributos
2
Las clases que
implementen una interfaz tienen
que definir sus métodos
3
public class Clave implements Comparable
“Comparable” tiene el método
“Compareto”
public int compareTo(Object c){
}
“Compareto” puede devolver
>0 si “this” es mayor al objeto que se compara
<0 si “this” es Menor al objeto que se compara
0 si “this” es igual al objeto que se compara
Vamos a implementar la Clase estudiante
Un estudiante tiene:
Dni de tipo “int”
Nombre de tipo “string”
nota de tipo “double”
Un estudiante es
“Comparable” por su número de
dni
Un estudiante tiene implementado el método
“tostring”
5 minutos de trabajo personal
EStudiante
¿de qué tipo serán la
clave y el
elemento del nodo de un BST?
?
Nodo nodo
comparable
Object
public class NodoBST{ private Comparable clave; private Object elemento; private NodoBST izquierdo; private NodoBST derecho;// . . . . . . . }
nodoBst
Un BST tiene
un nodo raíz3
1
2
6
5
Raíz
public class BST{
private NodoBST raiz; // . . . . . . . }
Bst: Constructor
¿cúales son las
Operaciones que se pueden
hacer con un BST?
?
Inserción de un elemento
Elementos a insertar: 2,5,3,1,6Elemento a
insertar 253
3
1
1
26
6
5
Bst: insertar
búsquedaDe elemento
UN
3
1
2
6
5
Elemento a Buscar 3
Devolvemos el objeto con clave 3
Bst: get
Eliminarun
Para eliminar un objeto con
cierta clave
Se busca elemento1EL
Se elimina El elemento2
Existen3 posibilidades
0No tiene hijos
3
1
2
6
5
Elemento a eliminar 3
Eliminamos el objeto con clave 3
1tiene un hijo
1
2
6
5
Elemento a eliminar 5
Eliminamos el objeto con clave 5 y el hijo ocupa su lugar
2tiene Los dos hijos
1
2
6
5
Elemento a eliminar 2
Eliminamos el objeto con clave 2
Se remplaza o por el mayor de su izquierda
O por el menor de su derecha
3
Bst: Borrar
Recorrer Un BST
Recorrido Pre-orden
3
1
2
6
5
public void preOrden (NodoBST ac){ if (ac != null){ // Proceso: P.ej., escribir
System.out.println(ac.getElemento());
preOrden (ac.getIzquierdo()); preOrden (ac.getDerecho()); }}
Recorrido Pre-ORDER
Recorrido en Post-orden
3
1
2
6
5
public void postOrden(NodoBST ac){ if (ac != null){ postOrden(ac.getIzquierdo()); postOrden(ac.getDerecho()); // Proceso: P.ej., escribir
System.out.println(ac.getElemento());
}}
Recorrido POST-ORDER
RecorridoIN-orden
3
1
2
6
5
public void inOrder(NodoBST ac){ if (ac != null){ inOrder(ac.getIzquierdo());// Proceso: P.ej., escribir
System.out.println(ac.getElemento());
inOrder(ac.getDerecho()); }}
Recorrido IN-ORDER
Si los elementos
tienen clave
Y queremos tener acceso indexado
Podemos usar
árboles
Y, Así, ser muy
Rápid0s